MadNick's blog

Wait, TooDifficult's solution is incorrect?

By MadNick, history, 8 years ago, In English

Slightly weak tests on this problem:

Input:
4 6 4
1 2
1 3
1 4
3 1 4 2 1 1 
2 2 2
1 3 1 3
1 2 1 1
1 2 1 1

Output:
3 1 2 5
1 6
1 4

P.S. I am not blaming anyone. Sometimes this kind of thing inevitably happens. I just wanted to let others know that their solution might be incorrect.

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

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

From the statement: As a result he picks at most k best girls he still have not invited from junctions on his way and invites them to his house to test if one of them is his dream girl. If there are less than k not invited girls on his path, he invites all of them.

At the time of the first query of type 1, he still hasn't invited any girl, so he invites girls #1, #2, #5. Then those are already invited, girl #6 has less weight than girl #4, so he now invites her, and afterwards he invites girl #4. The output seems correct to me..

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What output did you expect? since my solution gives the same as thr one written on your post

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yeah, I meant this was a correct output, but some "accepted" solutions crash on this test. For example, look at this code.

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

Actually, The testcases of problems sometimes are incomplete. I remember that one of my program can pass the test in Codeforces, but in another OJ it failed to pass because of some boundary testdatas.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Thanks for pointing out my mistake. And here is my new submission 20498917.

→ Reply