svineet's blog

By svineet, history, 8 years ago, In English

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

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?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You are correct. Can't able to figure out your mistake