Блог пользователя pr3pony

Автор pr3pony, история, 4 года назад, По-английски

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
  • Проголосовать: нравится
  • +69
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I did the problems in this contest as well and came up with the same test case. There were so many things wrong with the contest:

  • The default input-reading code is very often wrong (I program in Java)
  • The test case input format for Q1 did not match the description
  • There was a problem with the test case checker in Q3 (not sure what happened: could not AC in Java but rewrote in C++ and AC'd)
  • The discussions tab was not working, which really exacerbated the problem with Q2.

The contest quality was embarrassing to say the least. Not sure what happened with hackerrank...

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    I thought a lot about the problem and a working solution seems quite involved. Regarding your code, I haven't looked into what it does/dissected it at all, but I just tried running it on the test case

    6 6
    1 3
    3 4
    4 5
    5 2
    4 6
    6 2

    and your code outputs 6, although I believe the answer should be 5 (only edge (1, 3) can have weight 1).

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

I mean... I just read the statement and I noticed that the sample is wrong. You see the graph with the weights on it, and the array d is just different than reality.

Edit: I tried to say that you didn't even need to run any codr to see there was something wrong.

»
4 года назад, # |
  Проголосовать: нравится +135 Проголосовать: не нравится

Guys, there’s an easier way to handle issues about Hacker.* contests than to complain about them:

Spoiler
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +76 Проголосовать: не нравится

    I think such blogs are necessary, otherwise people don't know to avoid them.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      Why should they stop using it. Many people start to learn cp from these Platform. People cannot directly jump to CodeForces. HackerEarth HackerRank and CodeChef all these has main purpose to teach you cp. You can learn there if you are a beginner where as you can not learn anything in CodeForces. Why are you misguiding people. I request every one to go to any platform you like and learn cp. These people are red that does not mean their opinion is correct.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

        Opinions by definition can't be correct or incorrect.

        Anyway the arguments in your comment have almost nothing to do with why we avoid these sites.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -19 Проголосовать: не нравится

          So what do you recommend sir. Where should new people go to learn cp tell me some better place to learn. Opinion can be proved wrong. you can say earth is flat but it can be proved wrong easily. also do recommend me something i asked you for. don't just ask people to stop using a platform. It surely might not be good for experienced programmers but it is good for people who want to start. so in that case your opinion is wrong sir.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +12 Проголосовать: не нравится

            I learned the first principles from train.usaco.org. And AtCoder beginner contests have a lot of educational problems. And CSES has versions of many "classical" problems.

            And the issue here was not beginner-friendliness but poorly prepared problems.

            And stop with all this experienced vs beginner stuff. Every red has been a beginner once, the converse doesn't hold. I have had to learn all this stuff too. It's not as if I don't know what it's like to be a beginner.

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Hello,

I am Darshan, I manage the Content Team at HackerRank. We would like to apologize for the issues in this challenge in our recent contest.

For the complete correctness of the challenge, our author's greedy solution does not suffice, as indicated correctly by you.

We benchmark our challenges through multiple coders, and with this specific challenge, a corner case was not discovered by us which resulted in providing an incorrect challenge. We are carefully evaluating our internal practices in order to avoid such issues in the future.

The Greedy Solution provided as part of the Problem Setters solution missed on this key test case, we will be updating the solution here soon.

We are really sorry for the inconvenience caused and as a result, we have decided to not consider this challenge in the contest to calibrate the results and will update the leaderboard accordingly. We are working on making our problems more robust every day. Your feedback is much appreciated and will help us improve our challenge quality.

Hope to see you again in future contests! Thank you.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    Of course people make mistakes, it's more about standards and procedures we have to prevent such mistakes.

    Do you stress test your official solution against a simple brute force? I did that to your solution and there are tons of counterexamples. I wouldn't call it a "corner case". (Full disclosure: I only got such results after I added permuting of vertices to the generator. So it's possible you did this but rushed it. Still bad, but a lot better.)

    My code, saved as a.cpp
    Generator, saved as ag.cpp
    Shell script
    Output

    Even more importantly, do you ask authors to prove their solutions? The editorial doesn't say anything about why this greedy solution should even work. Do you have a proof and it is just flawed?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Will you also update Problem 1 so that the test cases are formatted correctly (as indicated in the problem statement and the sample test cases) and update the leaderboard accordingly?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Hi Darshan, you responded to my other comment about the errors in problem 1 with the private message "We have checked all other questions, and they are correct. The issue was with only the graph problem as I mentioned in my post."

    That's incorrect. If you look at problem 1, the problem statement clearly states "The first line contains two space separated integers M and N." Indeed, the Sample Input 0 has M and N on the first line, and the test case (case 0) only passes when M and N are treated as being on the same line. However, the real cases all have M and N on separate lines, and there was no way to know that this was the case.

    As a result, every user's CORRECT submission was rejected. In my case, I believe if the question was NOT broken, my placement would have been 2nd place for $250 rather than 3rd place for $100, so I would ask that you correct this issue as well.

    Thanks for taking our feedback here!