This was an interesting SRM. I solved both easy and medium lightening fast, and moved on to solve the hard one. I understood the hard problem, but just couldn’t come up with a generic solution. So mid way into the problem, I decided to look back at the medium problem to confirm I didn’t miss any corner case. I tested it with a tricky case that I came up with while I was devising the algorithm, but hadn’t tested my solution on after I passed example test cases. Guess what!? It failed!! Bummer. I quickly looked through my solution to cater for this tricky case and resubmitted. That reduced my score for the problem to half of my first submission. But it did save me from a completely failed solution. ;)

If there are any two people in the kingdom that aren’t connected either directly or through some friends, answer is -1. Reason is, there aren’t any limitations imposed between the difference of these two people, and their difference can be arbitrarily large or small.

In the other case, every citizen is connected to every other citizen either directly or through other friends. In such a case, we need to find the maximum friendship distance between any two people, and multiply that with “d”, as that will be the maximum possible difference between their wealth.

We can use Floyd-Warshall algorithm for finding out minimum distance between any two citizens, and then chose the maximum out of these minimum. If maximum is equal to infinity, it means there are two people not connected, so return -1. Otherwise return maximum*d.

A corner case to check for though is that we must not consider a connection to self. If there is a loop in the graph, this loop can have the maximum distance, but we are looking for maximum wealth difference between two different people. This is the case my first implementation missed. Though I did use it in the challenge phase to get +75 points. :)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#define INF 1000000000 class Egalitarianism { public: int maxDifference(vector <string> iF, int d) { int N = (int)iF.size(); vector<vector<int> > vv(N, vector<int>(N, INF)); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(iF[i][j] == 'Y') { vv[i][j] = 1; } } } for(int k=0;k<N;k++) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { vv[i][j] = min(vv[i][j], vv[i][k]+vv[k][j]); } } } int mx = INT_MIN; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(i==j) continue; mx = max(mx, vv[i][j]); } } if(mx>=INF) return -1; return mx*d; } }; |

We can easily generate all possible handles as the constraints are low, and figure out the count of unique ones.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class TopFox { public: int possibleHandles(string f, string g) { set<string> s; for(int i=1;i<=f.size();i++) { string p1 = f.substr(0, i); for(int j=1;j<=g.size();j++) { string p2 = g.substr(0, j); string pp = p1+p2; s.insert(pp); } } return s.size(); } }; |

**Conclusion:**

I am back to division 1. Cool!

can I say your blog is bit depressing? :P

and it needs a quicker algorithm for processing comments … it took ages. Really!

@Asma Haha. How is it depressing? Plus I have another blog at http://theotherme.bytehood.com. It is less depressing, I guess. :P