IvayloS's blog

Find original(harder) version of a problem?
By IvayloS, 10 years ago, In English

While browsing through some old problems I noticed this problem. For it there is a note at the top:

This is simplified version of the problem used on the original contest. The original problem seems to have too difficult solution. The constraints for input data have been reduced.

Statement of the sort "have too difficult solution" sounds like a challenge to me and so I decided I am up to it. I began to wonder is it possible to find the original statement. The problem is I can't seem to find it anywhere on the site. Is it possible to find the original statement somewhere?

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

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

I understood the announcement of that contest as "we had a solution, but didn't realize that our proof for it was incomplete, so it was wrong; we reduced the constraints so that there would be a working solution". The original statement is probably identical, just the constraints are larger.

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

    Yes I also think that the only difference was in the constraints and so I was searching for the original ones. But if I understand you correctly the problem was not that the original solution was too difficult, but that it was wrong in some cases.

    I have seen this happening on a few SRMs in top coder too — the author overlooks some cases where the solution will not work and in fact it is impossible to solve the original problem.

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

      There's no need to search for the original constraints (which were probably just set so that the wrong author's solution would work on them), you can just try to find as good of an algorithm as possible :D

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

Here's some claims about original problem statement:

http://codeforces.com/blog/entry/220?locale=en#comment-2429

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

    Great! Just what I was looking for. Thank you!

    → Reply