So one thing led to another and now I'm here to share my results.
Codeforces Round 889 (Div. 1)
As of writting this blog that's the most recent codeforces round and there was some controversy about some problems in it. I'm here to talk about a funny thing that happened involving its div1E.
This story starts during the contest.
Revisiting E after solving the other problems, I thought "maybe using a bunch of ones and high numbers to build the number of ways greedily by adding up values in a row of the pascal triangle might be enough" and tried submitting that. It got WA as the gods of AC weren't on my side at that point. Then something clicked and I remembered a past problem that I deemed to be similar and had one idea that I remembered as something like "why the fuck would I think of doing something like this". In my mind at that point there were 3 pieces of info: "the related problem had some idea of trying all possibilites of -+1 -+2 -+3", "I think that antontrygubO_o had something to do with that problem, not sure if he was on my team or if he set the problem or we just discussed about the problem" and "I think it was in some open cup". As the time was running and I didn't even remember the year that the contest took place, I just trusted my memory and tried the following solution:
For each multiset of values 1 and 2 with sum less than 60, greedily build the number of ways that the problem asks for.
So I made some random tests that confirmed that the first idea was bad, adapted the code for the new idea, tested it for some random cases and got AC. Submission
I'm not here to discuss about the controversy surrouding that problem in particular, the funny part starts from here.
Identifying the problem
After the contest, I chatted a bit in Um_nik's discord server lightly complaining while hoping for my solution to not FST about how I solved the problem with these exact words:
solving today's E by "I remember that there was a problem in some opencup that wanted number of subsets with sum 0 and the intended solution was using -+1, -+2, -+3, 0 and some big numbers or some shit, I hope the same works for this one" makes me feel dirty
Then anton himself showed up confirming that it was his problem. Fast forward from a few days ago to today, it turned into a chat about the problems being similar or not. That enticed my curiosity a bit, as my memory of the solution to that problem was a bit fuzzy. By googling "antontrygub opencup codeforces" I found this blog. I checked the codeforces gym to check if that contest was there and it was. Then, as reading every statement until finding the problem was too much work, I opened the editorial and looked for it in there, as I remembered the thing about -+1, -+2, -+3. Bingo! Browsing through it I found {−3, −2, −1, 1, 2, 3} in there, so it must be that problem. The problem is problem K and it seems to have been set almost 2 years ago. In fact, the link between me and the problem is that I took part in the Petrozavodsk camp that featured that contest.
The similarity between the two problems
Let's start this by first stating what both problems ask for
1854E
Output a sequence of size at most 60 of positive integers such that there are 1 <= K <= 1e10 subsequences with values that sum up to exactly 60.
K-onstruction
Output a sequence of size at most 30 of integers such that there are 1 <= K <= 1e6 subsequences with values that sum up to exactly 0.
From now on I'll call them "Problem 1" and "Problem 2". We can see from this that the problems indeed are very similar. Upon further inspection of the editorial, the intended solution for Problem 2 was some weird construction that expands values to be higher and higher along with a dp that links the ways of summing 0 and the transition is considering some sets with values +-1 +-2 +-3. That's quite different, since in Problem 1 we can't use negative numbers.
That lead me to the question of "how similar are these 2 problems?". I then found the following construction:
"Almost reducing" Problem 2 into Problem 1
If we're able to solve an instance of Problem 1 under some different constraints, then we can solve Problem 2. The constraints are: Output a sequence of size at most 29 of positive integers such that there are 1 <= K <= 1e6 subsequences with values that sum up to exactly 60. Let's call that Problem 3. We can solve Problem 1 for K by solving Problem 3 for K-1 and then appending -60 into the sequence. This is "almost reducing" since that idea by itself can't guarantee that a solution existing for Problem 2 implies a solution existing in Problem 3.
After finding that idea, I was very interested by this, since it might work and give me a chance of passing both problems using the same solution!
One stone two birds
I copied my solution to problem 1 and editted it to those constraints. After testing with some random values, I couldn't solve it with the same code because I used only numbers 1 and 2, so I added the possibility of taking 3s as well. After pressing up arrow + enter about 30 times, it seemed to be working so I changed the code in order to validate that it'd solve every value. It took about 20 minutes but my asserts weren't triggered, now our reduction is complete by exhaustion! Then it was just a matter of adapting the code in order to accept the input of both problems at the same time. I also did some constant optimization by memoizing the number of ways to sum each value up to 60 for every choice of 1s, 2s and 3s. This is the result and it indeed ACs both problems.
Conclusion
- If you have good memory, you can solve div1Es by just remembering past problems.
- Trust your instinct of "I remember seeing a related problem", it might lead you into guessing solutions.
- Proof by AC and guessing is optimal for codeforces, as confirming that the solution worked for 1e6 took 20 minutes.
- [notorious coincidence] Even if you're closely related to a problem you might not remember it, and that's how repeated problems usually happen. This is evidenced by antontrygubO_o not realizing that he set a problem that's almost the same thing to that div1E. Had he realized it, dario2994 most likely would've rejected the problem, as anton was a tester of that div1 round and he couldn't solve it during testing.
- I see nobody mentioning that problem other than me and that problem was set 2 years ago, so maybe repeated problems aren't all that bad for most people? [unconfirmed] I think that we've had problems that were related to IMO problems, why would that kind of problem be acceptable and not problems that were related to ICPC problems?
I wrote this in one go so I'm sorry if there are any grammatical mistakes. Those usually happen when I backtrack and add something to a sentence without checking if everything's connected properly.
