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

Правка en2, от pr3pony, 2020-08-05 12:35:16

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
Теги hackerrank

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский pr3pony 2020-08-05 12:35:16 4 fix grammar
en1 Английский pr3pony 2020-08-05 08:01:12 5230 Initial revision (published)