Hello CodeForces!

Recently, I am thinking about the **resubmission strategy** in CodeForces. Last week I participated in CodeForces Round #905 (Div.1), and I successfully solved first 4 problem with ~10 minutes remaining. However, after that, I saw the pretest result again and I noticed that execution time of problem C was 2979/3000ms.

Then I decided to speed up the solution of problem C and finally resubmitted just a few seconds before the contest ends. The execution time in pretest was shortened to 2464ms, and all of my solution passed in system test.

But the biggest blunder in this contest was resubmission — the number of testcases in pretest and system test was almost the same, and even my solution before resubmission passed (I confirmed after the contest). Since the score is mainly determined by submission time, my final rank in the contest dropped from ~60th to ~100th, and this made a difference between rating ~~increase~~ almost increase (UPD: miscalculated) and decrease.

So now I would like to ask everyone about resubmission strategy. There are some cases which may require resubmission in CodeForces, like as follows:

- My initial solution was not proved yet, and I found another proved solution
- I found a counter-example of my solution
- My solution is very close to time limit

But when will you decide the resubmission? I am very appreciate for sharing your opinion.

Thank you for reading this blog.

For the TLE case, I would prefer not resubmitting unless I have a clear counterexample that makes the solution definitely TLE. This is because codeforces rechecks the solution up to 3 times when the verdict is TLE, to check if the cause is really the solution or just a noise in the measurement. You can

~~abuse~~utilize this to your advantage however you want.I'd say, figure out the reason why it's taking so long to run and take a decision based on that. And the multiple execution doesn't always help. Sharing a

funexperience. Spoilered since it's kinda long.Fun ExperienceProblem: 1799D1 - Hot Start Up (easy version)

Solution 1: 195168481

I had a $$$dp[pos][cpu][last]$$$ solution, where $$$pos=n=5000$$$, $$$cpu=k=5000$$$ and $$$last=2$$$. (Realized after the contest that the $$$last$$$ was unnecessary.) The solution got a TLE on pretest 4.

Solution 2: 195177519

$$$5000*5000*2$$$ should pass in 1s. I figured, putting $$$[last]$$$ to the front would be a good solution since there would be fewer cache misses.

So, I changed it to $$$dp[pos][last][cpu]$$$ (notice the $$$[last]$$$ at the middle) and it passed the pretests, pretest 4 taking ~930ms to pass. I was pretty confident that this would pass since it would be executed multiple times if it TLE's. So I didn't think much of it. This solution TLE'd on test 8 during the system test.

Solution 3: 221636417

Much later (> 6 months), while talking to someone about array cache, I realized that my solution had $$$[last]$$$ in the middle. So I submitted the correct one, $$$dp[last][pos][cpu]$$$. This solution comfortably passes, at 826 ms.

Takeaway: If I figured out during the contest that I made the mistake, I'd submit it again.

---deleted since the typo was fixed and Noone like my little joke--

Or I might be bad at math lol. Fixed, thanks!

In my opinion, it is only necessary to resubmit if you are sure that your solution is wrong (there exists a counter-example). Contest problems have to be very strict with their testcases, and generally the pretests should account for extreme cases (large input size) and tricky edge cases.

For the issue of slow solutions, I think if you are worried about TLE in main tests then that's something you should watch for immediately after your submission when you can quickly optimize your code, but it's not really worth it if it's been a long time since your submission.

I don't think solutions being unproven is something to worry about, oftentimes the proof might be difficult and a waste time to find, and if you think your solution might not be correct then quickly think for possible counter examples then move on.

I remember doing the same things as what you described. I considered it as a mistake and decided to never do the same again.

Anyway, for the cases you mentioned, I guess I will resubmit for #1 and #3 only if I have a very cheap fix, and resubmit for #2 if I know how to fix it.

We can use a simple mathematical model to help answer this question. Assume that your objective is to maximize your expected rating. I'm going to assume for simplicity that all aspects of the contest results are known except whether your original submission and updated submission will pass systests. Let $$$p_1$$$ and $$$p_2$$$ be the probabilities that your old and new submissions, respectively, get AC.

Consider three cases.

1: You don't resubmit your C. In this case, by my calculations your score would have been 2760 if you got AC and 2082 otherwise. According to cfviz, this would have led to -7 if you got AC and -58 otherwise. Thus, your expected delta is $$$-7p_1 - 58 (1 - p_1) = 51p_1 - 58.$$$

2: You resubmit your C after solving D (this is what you did in contest). In this case, your delta would be -58 as before if you FST and -35 (what you received in-contest) with AC. Thus, your expected delta is $$$-35p_2 - 58(1-p_2) = 23 p_2 - 58.$$$

3: You resubmit C before solving D. This option is a bit less attractive in practice because in practice it might stop you from solving D. In this case, assuming resubmitting C takes you 12 minutes (the amount of time it took after D), you would have solved C at 1:20 with two penalties, so the value of C would have been about 580. You would have solved D at 1:59, for a score of about 655. This would give you a total score of 2602 with an AC and 2022 with an FST on C. Your resulting delta would have been -29 with an AC and -68 with an FST, for an expected delta of $$$-29 p_2 - 68 (1 - p_2) = 39p_2 - 68.$$$

First, let's figure out when (2) is preferable to (3). This holds when $$$23 p_2 - 58 \ge 39 p_2 - 68$$$, i.e., $$$10 \ge 16 p_2$$$, i.e., $$$p_2 \le \frac{5}{8}.$$$ Thus, if your new submission has at least a $$$5/8$$$ chance of AC, you should resubmit immediately, while otherwise you should resubmit after solving D.

To compare (1) and (2) we have $$$23 p_2 - 58 \ge 51 p_1 - 58$$$ when $$$p_2 \ge \frac{51}{23} p_1 \approx 2.52 p_1.$$$ Thus, resubmitting after solving D is only optimal if it multiplies your probability of AC by at least $$$2.5$$$, but the resulting AC probability is at most $$$5/8.$$$

To compare (1) and (3), we have $$$39 p_2 - 68 \ge 51 p_1 - 58$$$ when $$$39 p_2 \ge 51 p_1 + 10,$$$ i.e., $$$p_2 \ge 1.31 p_1 + 0.32$$$. If this condition holds and $$$p_2 \ge 5/8$$$, then resubmitting C immediately after solving is optimal. As a simple example, if $$$p_2 = 1$$$, then this is optimal if $$$p_1 \le 0.52.$$$

My intuitive assessment of this situation is that (2) is unlikely to be preferable to (3) unless there's a high probability that resubmitting costs you the opportunity to solve another problem. The decision to resubmit or not immediately after solving C is closer and depends largely on your assessment of whether pretests are likely to be strong or if systests are likely to have a test on which your solution slows down substantially.

Just never resubmit and write a comment complaining about tight TL if you FST

this works