Gerald's blog

Codeforces Round #118: Problem С (Div1), E (Div2)
By Gerald, 13 years ago, translation, In English

Good Morning, Codeforces!

Analyzing the task C (Div1), E (div2) I came to the conclusion that the author's solution is wrong, so I bring to you all a huge apology.

However it turned out all pretests were correct and there are only a few number of incorrect hacks (only 3). After discussing the situation with MikeMirzayanov we made ​​this decision:

  • Problem E almost do not effect on contest results for Div2 participants (there are only a few number of submits and no hacks), so the contest will be rated for Div2 participants.

  • The contest will be rated for Div1 participants, only if this problem have right and fast solution. I wasted all todays night (or morning) finding this solution. Therefore I propose to solve this problem by the community (if it's possible). If during the day, i.e. 24 hours after publishing this post, one cannot find solution, Div1 competition will be considered unrated.

Once again I bring you my apologies for this mistake. I hope that we will be able to master this problem together. Feel free to write all your ideas in this post, even some wrong idea may hint at the right solution. We would be very grateful to everyone who will take part in solving of that problem.

Note that this problem appeared in problemset. All tests are correct and you may try to solve it.

UPD: 24 hours have passed. Unfortunately, no one has written the correct solution, or close to it. Div1 round is declared unrated. Many thanks to all those who put their efforts and tried to solve this problem.

Best regards, Gerald Agapov.

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

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

Just curious: Is searching + cut-case, or a probabilistic solution be considered an acceptable solution?

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

I think they should consider the number of correct hacks too. It can be incorrect actually.

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

Did 1663307 solved the problem?

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

    Oh, no. This code have wrong "if" in the end of program. (if n != 20 print something)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it -17 Vote: I do not like it

      Why don't you add a test to make this solution fail? Or else this solution seems to be right :)

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Cause it's "if war". You can add all tests in archive to your solution.

        → Reply
»
13 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Well, that's not so bad. It will be OK whether this round is rated or not. Personally I think the main point in involving programing contests is to enjoy the process of solving not the result whether you solved it or not. Maybe it will be easy to solve if you change the original problem a little? Hope you find the solution soon!

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

I wonder how it is possible so many coders came up with the same, wrong solution ;). I was upset after the contest, because I had no idea for C and so many participants submitted it.

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

    The situation is somewhat similar to the one after the SRM 539 at TopCoder. Model solution for 500 points problem was wrong, although 112 submissions passed system test with wrong test data.

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

    As for me, I just sat down and wrote it because I had seen how many coders solved it and the first idea exatly fitted into TL. Also, I had a thought that it is entirely wrong but it was quicker to code and sumbit rather to think. It passed and it was enough.

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

    I agree with DamianS comment. How is it possible that the people who usually do very well in codeforces wrote the same expected "wrong" solution all of them? I think the solution was clearly wrong. Thus, seeing so many very smart people doing the same simple mistake is surprising.

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

      I think it's the ability to get solutions accepted. Actually it is common practice to get OK on an unproven program, with only some speculations on correctness. To get a high succes rate with such strategy, I guess one has to have extraordinary intuition. Besides, there are also hints on the scoreboard: how fast the problem was solved by the majority, how much time and memory did other solution take, and so on. Just some Jedi tricks...

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

The same thing happened in a TopCoder SRM a few weeks ago. The community couldn't find a solution in 24 hours so Div I was unrated.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Oh... I did participate that very contest!

    I solved no problems there and they supposed that my rating would be subtracted by about 200 points. Then, it turned to be unrated and I was saved!

    To make sure: You mean this contest, don't you?

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

      yeap; I think # people solved demonstrates the difficulty of the problem; since many coders' solution passed the system test, probably people on the top of the rankings thought that probably the solution is correct.

      when I looked at this problem, I immediately thought that it's reducible to one of the NP problem, upon which I figured that the constraint is too large to tackle -- I thought about it for > 1 hr during the contest, to see if there could be feasible solution otherwise, but wasn't sure till the end if efficient solution exists. I am just glad that it is actually hard problem, as my intuition served me correctly :P

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

        "I immediately thought that it’s reducible to one of the NP problem"

        What NP problem do you mean?

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

        Just wanted to say, a lot of problems, including easy ones are reducible to NP-complete problems. For example, you can use SAT to solve 2-SAT, that does not mean 2-SAT does not have a polynomial solution.

        In order to show that a problem is NP-complete, you also need to show that it is NP-hard — We need to reduce a NP-complete problem to problem C. If we can use problem C to solve a NP problem, then C is NP-hard.

        Whilst reducing problem C to a NP-complete problem shows that it is NP-easy , which means it is at most as hard as NP-complete

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

          I must have thought about this in the opposite direction during the competition; thanks for the correct (it is correct, right?) clarification :)

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

I think it's been 24hours

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

I think there should be a notice that warning no correct solutions found in the problem statement.

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

all problems are very interesting

→ Reply