Posted: April 1, 2018

Folklore

ZQFMGB12 needs to walk along the V1 path every day to get to his classes. One time, he noticed that the Canada geese have arrived very early. Geese were even present in February, when snow was still around.

One observation that ZQFMGB12 made about geese was that they always seemed to be in pairs. Upon further research, he discovered that Canada geese mate for life (unlike some other species of animals, like humans).

Unfortunately, the TLE '17 March contest was coming up and he had no problem ideas, not even for P1. Problem setting was becoming a chore for him and it didn't help that certain others always told him his problems were bad. He was happy, though, that his problem setting ordeal would almost be over, as only one more TLE was planned for April.

Even more unfortunately, ZQFMGB12 trapped himself early in the year by forcing Willson-themed problems that tied to the life of a real Canada goose. It was very difficult for the TLE team to come up with good problems regarding Canada geese, so most of those problems weren't well received by participants.

While walking on the V1 path, ZQFMGB12 thought about geese again. Why not ask a question about the geese in pairs? He came up with a slight variation of the problem asked on the contest, but it turned out to be NP-hard (or maybe not? We don't know for sure). So he modified the problem slightly to get the current version.

Unfortunately, when he presented the problem to d, he immediately said

This problem is literally min cost max flow. Everyone will get it instantly.

So ZQFMGB12 was disappointed that his idea turned out to be a template problem, so the TLE team decided not to use it. d came up with a pretty good replacement.

However, only hours before the start of the contest, d discovered that he had made a crucial error that he could not fix in time. Without much time left for a replacement and delaying by a day no longer an option, the team was forced to use the current version. After all, min cost max flow hasn't appeared on a DMOJ contest, and how many Canadian high school students would know min cost max flow in the first place? (Answer: not a lot, apparently. Time to teach it, bruce.)

When setting the problem, ZQFMGB12 had to determine bounds. He asked d the runtime of the min cost max flow algorithm, just to be sure. It's ~\mathcal{O}(N^3)~.

Also, being a CCO preparation contest, the team felt obliged to add subtasks. So we added an ~\mathcal{O}(N!)~ brute force subtask and an ~\mathcal{O}(2^N)~ bitmask subtask.

While the contest ran, everything seemed to run well until somebody using an alt entered the contest. He got to this problem, coded a brute force, and failed. He resubmitted several times, and determining that his code was ~100\%~ correct, he blamed us for incorrect data. Even d believed it, and said that ZQFMGB12's data was incorrect and that he should check the code. Then, ZQFMGB12 asked d what the minimum total distance that d's brute force was printing. Then d said

nvm

i added dist^2

That was a pretty big mistake. It's pretty obvious that ~\sqrt{a_1^2-b_1^2} + \sqrt{a_2^2-b_2^2} + \dots + \sqrt{a_k^2-b_k^2}~ and ~(a_1^2-b_1^2) + (a_2^2-b_2^2) + \dots + (a_k^2-b_k^2)~ do not have the same maximum/minimum properties for all ~a_1,b_1,\dots,a_k,b_k \in \mathbb{R}~.

Relieved that ZQFMGB12's data was more correct, he looked back at the alt's code. There was no sqrt anywhere in the code. That was pretty hilarious. The alt was blasting into the DMOJ Discord how he was correct and how we were wrong and that the contest was bad. The alt never ended up fixing that bug. As of now, an apology has been given.

Anyways, the moral of this story is: "Problem setting is hard, and good luck to the HS kiddies next year on CCC/CCO heh heh heh."