HackerRank Hack the Interview VI (Asia Pacific) "0-1 Graph" author's solution is wrong

Revision en1, by pr3pony, 2020-08-05 08:01:12

HackerRank Hack the Interview VI (Asia Pacific) is a contest with Amazon gift cards worth up to $500 as prizes for top 3. I found one of its problems' official solution wrong. I sent message to its author a day ago but I haven't got a reply yet. Therefore I make this post to get some attention from the community.

Problem , Editorial

Problem Setter's code :

The setter's solution is wrong. Consider the following test case:

4 3
1 3
3 4
4 2

The setter's solution outputs 4 with the following d[].

d: 0 1 1 2

But it's not possible to have such d[]. If d[4] = 2, then d[2] >= 2. Since d[3] <= 1, it's impossible. The answer should be 3 with the following d[].

d: 0 1 1 1

My submission during contest can pass the above test case. I am not sure whether it's correct or not, please help me verify.

My code
Tags hackerrank

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pr3pony 2020-08-05 12:35:16 4 fix grammar
en1 English pr3pony 2020-08-05 08:01:12 5230 Initial revision (published)