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.
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.