jupanul's blog

VERY Wrong Solution passed today'c div1 C
By jupanul, history, 8 years ago, In English

I'm on the phone right now and have no laptop, so sorry for the low quality post. But I wanted to say that my solution for problem C was to set a random food for each boy and then randomly change a boy's food until the second restriction was met. Surprisingly, this passed the system tests! Can anyone relate? Did anyone else have a wrong solution that passed? Weak testcases, or what happened?

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

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

That seems believable, depending on your implementation.

One solution I saw was to simply force 2i+1 and 2i+2 (for i = 0 to n-1) to be different resulting in a bipartite graph. If you implemented it in a certain way I can see your solution passing because it was accidentally like this. Otherwise, maybe the test cases are weak :)

Either way, your honesty is valuable to CF community.

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

This is definitely not "VERY wrong". For me, it was highly likely that such solution will pass (I thought about exactly the same), but came up with a real solution, but if I hadn't have right idea I would have coded that local search.

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

And why exactly is this solution (very) wrong?

→ Reply