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";
}

rexwulf
October 16, 2018 Simply use a KD tree using long and lang as 2 dimensions of each node and build a KD tree based on long, lat of all cabs and search the position of user in the KD 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 KD tree.
n>current number of cabs.
A more refined solution will be to create a grid for the location by maintaining a KD 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.
}

rexwulf
October 01, 2018 Open Chat in New Window
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.