Problem: RANKFRAUD
The problem can be framed as a graph problem, to find hamiltonian path in the graph. As the graph is a tournament graph, the path can be found in polynomial time.
My solution uses the algorithm described here, but it gives me a WA for four cases. I am not able to figure out why my implementation is wrong.
When I inserted the asserts I got a SIGABRT, meaning the portion with the got variable is failing somehow. Shouldn't there always be a vertex j such that path[j]->i and i->path[j+1]?
Let's assume there is not such a vertex and that path[path.size()-1] does not connect to i and i does not connect to path[0]. If it does the other two ifs should handle that in the code. Then we have a case where path[0] defeats i and i defeats path[path.size()-1]. If we assumed that no element j in path exists such that path[j] defeats i and i defeats path[j+1], then for all j the case must be either that path[j] and path[j+1] both are defeated by i OR path[j] and path[j+1] both defeat i. In the first cases, all indices 1..path.size()-1 must get defeated by i, but we know that path[0] defeats i so we have found a place to insert i. A similar argument goes the other way for the last element in path.
What is wrong with my reasoning?
