The 2024 CCPC Jinan Contest ended on Oct 27. While this report was initially a requirement by our team coach, I think it may be valuable to repost it to Codeforces in English.

Preparation

The week before contest contained 2 team training sessions: 2022 China Collegiate Programming Contest (CCPC) Guilin Site and The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG), and we got 1 problem above the gold medal line in both, which enhanced our confidence. Our three teams, along with our coach (part of the contest committee), reached Jinan via high-speed railway a day prior to team registration.

During the dress rehearsal, a flaw on the contest floor(literal) immediately drew our attention: there was a narrow drain hole beneath one of my teammates' chair and a chair leg might get caught up causing him to fall over, and later we found we were not alone. We called staff over and they fixed it with cardboard taped to the ground. But the bigger problem was the keyboard: the \ and Enter almost switched place(compared to usual keyboard layouts), so when typing \n an actual carriage return plus an n appeared instead! To make things worse, it took a smash to press down the right SHIFT and Backspace. The committee promised to replace keyboards in following contests.

Problems in the rehearsal were simple and one of them was from one of the two trainings above. We AKed (i.e. solved all) the 5 problems within 1h, and spent the remaining hour measuring the judgement server. At the preparation meeting that evening, teams shared their testing results including the speeds of:

• * and / on double-precision FPs
• % operation on 64-bit integers
• __gcd()
• Insertion and queries on set map priority_queue
• cout with and without stream desyncing
• NTT

The meeting was truncated because several contestants (including I) registered rated for ABC377 for a final warm-up.

Contest Day

I had a bad night's sleep, as air in Jinan is much drier than in Shanghai and the ventilation was not quite good. Luckily, it didn't affect much of my early-game performance.

Early Game

[0:00] We split the problemset by modulo 3 and Icedpiggy found the "Registration problem" A immediately.

[0:08] AC on A. I made marks on seemingly viable problems like B, C, I, L and M(which proved to be a trap eventually). Several green lights for J showed up on the scoreboard and Icedpiggy went to work. In the meantime, A-Quark found an $$$O(1)$$$ solution for B and explained it for me and I spent time confirming.

[0:32] AC on J. I coded B while A-Quark and Icedpiggy found the critical idea for problem I and later the correct approach for F.

[0:57] AC on B. Now Icedpiggy has 2 problems in his hand and coded them sequentially. The scoreboard was a bit messy now: we didn't know which should be the 6th problem and left observations on the printed problemset.

[1:20] AC on F. A-Quark and I started to form an idea for problem E, which was almost pure implementation and included big integer operations(which hampers C++). I am the only Python user in our team so it's up to me.

Midgame

[1:44] AC on I. I began to code E but I struggled with Python's input scheme and eventually gave up using map and wrote 6 separate int(str)s instead.

[2:08] Coding on E ended but the result of sample tests were ridiculous. A-Quark formed an idea for problem H (DP by digit) and fed it to Icedpiggy.

[2:31] WA on E. Icedpiggy coded his first draft of H but couldn't pass samples. Meanwhile A-Quark pointed out a crucial missing case in E.

[3:10] WA on E. We switched places and debugging for H continued. I asked A-Quark to leave observations on C(construction) and went on digging my head for the bug.

At this moment, I felt something was wrong: each of us is working on a separate problem.

[3:27] I found that I applied missing crucial case to only one of the major cases: it should apply to all. Icedpiggy kept failing samples on H and considered refactoring.

[3:39] WA on E for the 3rd time. I determined that it would be pointless to manually debug and quickly wrote a brute force and a data generator. The first round of STing produced exactly one error and I printed the test case. Icedpiggy completed refactoring under the assistance of A-Quark.

Last Moments

[4:00] Scoreboard frozen. I located the bug and fixed it immediately.

[4:07] RE on E. A second round of ST showed that the culprit was a useless floating point division that existed since the initial draft!

[4:19] AC on E finally! But I don't think 6 problems can earn us gold, and commanded A-Quark to continue assisting Icedpiggy and turned to C alone.

[4:40] I found the key construction structure for problem C but was still a step away from full solution. Problem H seems far from getting back onto the right track.

[4:50] I had the complete solution for C and preempted the keyboard for a final desperate sprint.

[4:59] WA on C.

Final result: 6 solve, 621 penalty, Rank 39, Silver

Aftermath

[5:06] I debugged till the code for C runs correctly on manual tests. The computer did not lock up so we plugged in a flash drive to take away the contest code.

After returning to my own computer, C was upsolved after one Wrong Answer on test 10 within 10 minutes. So it can be derived that I would solve C for certain if I had 30 minutes on keyboard, and 20 minutes would give me a good chance. 10 minutes was just not enough to get anything correct.

Looking back, we decided that it was the long keyboard time consumed on E that denied the possibility of solving C: it seems I should have started stress testing earlier when the 2nd WA came out, because it would be a waste of time to debug on paper without a test case that fails the buggy code when we were completely unsure if it's a missing edge case or an implementation bug. Unfamiliarity with Python also accounted for the slow E.

After the contest, many other contestants blamed the problemsetters for a problem that is unfriendly for C++, and some of them had to implement a big integer class. (In Chinese OI, C++ is currently the only supported language, and Python has never been one.) My opinion is that, while the problemset is fair for everyone, if you try to prepare a problem which may upset a large portion of contestants due to non-skill-issue obstacles, it's better to expect being criticized.

The next day Icedpiggy found the error in problem H with the help from another contestant's stress tests and upsolved H. It turned out that the idea was almost correct but there were implementation problems on A-Quark's idea sheet, and we never confirmed it again, nor stress-tested. In this case, a common solution is to call the third teammate(in this case, me) over, but I was imprisoned by E and couldn't help until AC on E.

So was it better to help my teammates instead of giving C a shot during the last hour? We eventually reached a consensus that my decision was optimal in that case, because the construction problem C would be lightweight in implementation, and the code for H has bloated and we were not passing the samples after at least 40min of debugging.

(This blog did not rely on GPT or similar tools.)

I implemented the solution described in the editorial, with KMP instead of Z-function, but all my submissions ended up TLE41 (261016696) and I couldn't get the log^2 solution right.

By dividing the submission into $$$>\sqrt{n}$$$ and $$$\le\sqrt{n}$$$ parts I found my solution would finish in 3.2 seconds and I tried my best to squeeze in but still couldn't.

Could anyone help me optimize the constant factor further, or is KMP unable to pass?

Hello Codeforces!

Solving 5 problems in Educational Codeforces Round 164 (Rated for Div. 2) gave me an unexpected +125 and I leaped across *1800 right into the lower bounds of purple. This means I am finally touching the eligibility to take part in contests with many of the brightest competitive programmers!

Within the 3 months after registering my account, I have learned many new techniques, with the most representative being modular inverse, segment tree with lazy propagation, fenwick tree and Tarjan's algorithm. I really believe segment tree is something like "Welcome to the realms of div.1!" However, my rating revolved around 1790 and was incredibly stable and I doubted if I was improving. But in several training sessions and VPs I managed to do well. Never mind, CM has come, and I finally start to believe I can go on in CP and reach for my goal in an ICPC regional. The next step is to defend CM, and I'm planning to learn:

• More STL
• KMP and AC automaton
• Decomposition and Mo's algorithm
• Maxflow and Mincut: Dinic's algorithm
• Euler's sieve
• Matching on a bipartite?
• Suffix array of a string?
• Fast Fourier Transformation?
• Heuristic searching and pruning techniques?
• More ad-hoc constructive problems
• More ad-hoc dp problems

Fun fact: Div 1+2s finish at 1:35AM in China, so I did not register for CodeTON 8 because I would get up early to enjoy cherry blossoms the next day, but when upsolving I solved ABC1C2, skipped D and took down E within 90 minutes and the trip cost me 2 TON...

Problem:

Given a directed graph and $$$q$$$ queries. For each query, you need to answer whether a path exists from point $$$x$$$ to point $$$y$$$. Each query needs to be processed within $$$O(1)$$$.

A BF solution is, we can do $$$V$$$ DFSs from every vertex and set the bits in the answer matrix for each visited vertex, and the complexity of preprocessing is $$$O(V^2)$$$. You can do some optimizations to reduce the steps taken in the traversal by a lot, but as long as you store the answer in a matrix, $$$O(V^2)$$$ space complexity leads to an inevitable $$$O(V^2)$$$ time complexity.

Now the question is: is it possible to do the preprocessing within less than $$$O(V^2)$$$ time, or at least, less than $$$O(V^2)$$$ space? At least, if queries are to be processed online, it seems highly improbable.

I wrote DAG in the title, because we can run Tarjan's to find out SCCs and if $$$x$$$ and $$$y$$$ belong to the same SCC it's a clear YES.

UPD: There seems to be some paper on this: Paper