cry's blog

The Worst Case of Notorious Coincidence in Problemsetting History
By cry, 8 hours 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
  • +105
  • Vote: I do not like it

»
8 hours ago, # |
  Vote: I like it +72 Vote: I do not like it

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

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

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

I was made aware by IceKnight1093.

→ Reply
»
7 hours ago, # |
  Vote: I like it +19 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
»
6 hours ago, # |
  Vote: I like it +77 Vote: I do not like it

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

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For this reason, will the contest be unrated?

→ Reply
»
34 minutes ago, # |
  Vote: I like it 0 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
  • »
    »
    23 minutes 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