rexwulf
BAN USERFOR MULTIPLES WITH ANY NUMBER OF DIGITS:
struct node{
string s;
int rem;
node(string t, int x){
this->s = t;
this->rem = x;
}
};
string smallestMultiple(int n) {
queue<node> q;
q.push(node("1",1%n));
vector<int> seen(n,0);
while(q.size()){
node x = q.front(); q.pop();
if(x.rem == 0)
return x.s;
int rem0 = (10*x.rem)%n, rem1 = (10*x.rem +1)%n;
string s0 = x.s+"0", s1= x.s+"1";
if(!seen[rem0]) q.push(node(s0,rem0)), seen[rem0]=1;
if(!seen[rem1]) q.push(node(s1,rem1)), seen[rem1]=1;
}
return "-1";
}
Simply use a K-D tree using long and lang as 2 dimensions of each node and build a K-D tree based on long, lat of all cabs and search the position of user in the K-D tree and while searching check if euclid dist(user,cab) <=R.
Updation: O(logn)/ O(d)
Search: O(logn)/ O(d)
d->max depth of K-D tree.
n->current number of cabs.
A more refined solution will be to create a grid for the location by maintaining a K-D tree with a threshold depth and group cabs according to criteria then simply search with user's location and assign valid groups.
In order to find the cell (x,y) to toggle so that we get the shortest path, let the source be (sx,sy) and destination be (dx,dy):
1. calculate dp1 from (sx,sy) to every cell (x,y) storing the shortest path.
2. calculate dp2 from (dx,dy) to every cell(x,y) storing the shortest path.
3. create a variable shortest_path = INF.
4. Traverse through the matrix and if for that cell, dp1+dp2 < shortest_path, update shortest_path.
Simple implementation in C++: (assuming cID and vID to be int)
1. create a set<pair<int,int>> S and an unordered_map<int,bool> visited.
2. If current cID present in S then update count by erasing the entry and inserting again with count+1. Otherwise insert with count 1.
3. Mark vID as visited.
4. Query for top 5 candidates.
}
Why this will work?
- rexwulf October 27, 2018Let's consider the fixing of one such cycle.
To fix one cycle, swap one of the numbers in cycle with 0 if 0 is not already present then simply swap each element with 0 to bring each element to its correct position.
The first extra swap is the reason for extra 1 in contribution of each cycle.