cry's blog

The Worst Case of Notorious Coincidence in Problemsetting History
By cry, 5 months ago, In English

I accidentally copied a CodeChef problem.

I was just made aware by satyam343 that 1996A - Legs somehow COINCIDES EXACTLY with FARMLEGS.

I had zero idea this problem even existed before right now. I even thought satyam343 was trolling and thought this problem was only published after my contest. It wasn't until I looked at submission dates that I noticed the problem was created more than three months ago... My problem was based on a mixture of middle-school word problems and me casually thinking of USACO cows.

Regarding how even the constraints are exactly the same: The constraints were initially $$$t \leq 10^5$$$ and $$$n \leq 2 \cdot 10^5$$$, but a tester did $$$O(tn)$$$ and still passed all test cases. Obviously, this is hackable, so we have to either decide to add a third test case with all tests being $$$2 \cdot 10^5$$$ or make $$$O(tn)$$$ comfortably pass. We didn't want to blow up queue even more, so we resorted to the latter option.

Anyways, this is way too funny, so I have to make a blog. This is also even more ironic since I advertised a CodeChef contest in the comments :skull:

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

»
5 months ago, # |
  Vote: I like it +80 Vote: I do not like it

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

    I have like 2 total solves on codechef cut me some slack

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

I was made aware by IceKnight1093.

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

Actually G also appear in past TopCoder round https://community.topcoder.com/stat?c=problem_statement&pm=17083

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

Actually, (probably) the only problem in your round that didn't appear anywhere before is D.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For this reason, will the contest be unrated?

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

Not a huge deal but I think at least $$$\mathcal{O}(tn^2)$$$ solutions could be blocked. There are too many such solutions in C++ but harder to pass with bad constant and slower languages. $$$n \le 10^4$$$, or even larger $$$n$$$ with fewer test cases wouldn't have made anything worse (also why 2-second TL?)

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

    Also, I don't see why keeping the initial $$$t \le 10^5$$$ couldn't be an option. You could simply increase the upper limit of $$$n$$$ to something like $$$10^6$$$ so that you can put enough large cases in test 2 without duplicates. It's not like you need to put every possible case to test correctness.

    To be honest, I think just $$$t \le 1000$$$ and $$$n \le 10^9$$$ can't be any weak or something and it prevents $$$\mathcal{O}(tn)$$$ perfectly.

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

      To answer the latter, coordinator wanted me to make $$$n$$$ small enough so every value of $$$n$$$ could be tested.

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

        Well, I find it quite unnecessary but anyways I kinda feel sad to see it's on a vague boundary of allowing some quadratic solutions now.

        → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When I read that problem I was like I have solved this before on codechef

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

I can't wait for the cry expose blog.

→ Reply