Блог пользователя cry

Автор cry, 3 месяца назад, По-английски

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:

  • Проголосовать: нравится
  • +187
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +55 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

I was made aware by IceKnight1093.

»
3 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +148 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For this reason, will the contest be unrated?

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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?)

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

I can't wait for the cry expose blog.