200 out of the 500 qualified participants seem to be cheaters. Depending on how gpt-proof the problems are, getting a top-200 t-shirt will either be very easy, or impossible for me.

Please postpone this and remove cheaters, I want to go to Round3 after 4 years :_

183 indians in top 500,the youngsters from my country sure seem to be genuises.

The wrong solutions of B passed due to weak tc. I will miss the T-shirt this year as well.

I wonder what all changed for cheaters when LLMs became decent. There have always been public groups (Telegram channels, etc) where solutions were shared openly. It's not like LLMs can spit out vastly different solutions to the same problem.

So, is it that they can be prompted to make custom modifications, like using the participants template and naming style, etc? But, this only makes the process of saving your submission from plagiarism checkers convenient. Was plag-proofing always the main bottleneck that demotivated participants from cheating?

"CheaterCup"

U also did not do anything/not even talking abt R2-B problem till now . This is so bad SecondThread

wtf is A

Rajneesh Chaudhary is cheating at its peak. He isn’t even a Master on Codeforces, yet he’s beating legendary Grandmasters with the help of AI. Shame on you—what a loser. You’re destroying the hard work of many problem setters and ruining the rankings of genuine contestants who actually grind and earn their skills. You’re not a pro coder—you’re just a cheater.

His linkedin Id-->

https://www.linkedin.com/in/rajneesh-chaudhary-37632a1b7/

Look this matter seriously SecondThread

$$$O(N^3)$$$ passed in B :skull:

Does anyone have a different solution to D than virtual tree + inclusion exclusion on the values at the end?

can someone explain the solution to A? everyone's code seems to be insanely convoluted

So many FSTs in B :<

I wonder if the "Top-200" badge rule will hold when all participants with 0 score (currently ranked 202) get a rank <= 200 :p

• B: I like this very much, thanks.
• C: My FFT fit in time, I couldn't get the point of this problem. Also I was almost running out of time for fixing my code for invalid input... (For those who struggles, check if $$$|C_i| \gt 2000$$$.)
• D: I felt this was too standard for its position.

These are todays cheaters without doubt. Kindly review and remove them.

Rajneesh Chaudhary (Raj)
Soumen Kumar (punisher2919)
Anukrati Chaturvedi (anukraticodes)
Shivansh Rana (ShivanshCoding)
Shivam Singh
Ramharsh Dandekar (Ramharsh-aidev)
Saurabh Bansal (Saurabh52bnsl)
Shivam Aryan (ultraaryan10)
Bunty Dgeneration (Bhupendra Gehlot)
Tarandeep Singh Juneja (tsj2003)
Pratik Suryawanshi (Pratik2912)
Mrunal Tarwatkar
Lokendra Mundele
Tanishq Gupta

For anybody who is stressed about cheaters, it's okay, I have a nice calming song about competitive programming. Helps me solve and got me LGM.

Screencast

What a weird score distribution. Handling all the cases in A is insane, while D is literally harmonic sum + virtual tree with 0 thinking. I'm assuming there are people who could copy something from their lib and add 20 lines.

Thanks for the round! Overall, I enjoyed the round more than the last few Round 3s. A few thoughts:

It seems like the authors had a pretty hard time anticipating the difficulty distribution--my personal difficulty ordering was B, D, C (with the FFT solution), A, E, C (with the bitset solution), though I'd consider swapping A/E. This looks at least roughly consistent with the scoreboard--it seems like B and D were clearly the two easiest problems, with the other three having solve counts around similar orders of magnitude.

The result of this was that a substantial determinant of finals qualification was realizing which problems actually matter--assuming A was one of the easier problems, if not the easiest problem, would cause a contestant to spend lots of time on a problem that ultimately turned out to be inconsequential. This also came up in Round 2--D turned out to be easily the hardest problem of the round, and B was arguably harder than C but was worth far fewer points. It might make sense to recruit a larger testing force, possibly drawing from strong Codeforces users who have conflicts on the day of the actual competition, to get a more accurate sense of the difficulty of the problems.

Specific thoughts on the problems:

A: Nice problem, though far too hard for its position (based on my personal experience and the scoreboard). If I was setting the round, I would have guaranteed $$$K \geq 3$$$: this contest is already pretty detail/implementation-heavy, and I don't think dealing with $$$K = 2$$$ was an interesting part of the problem.

B: Good problem, nice little DP.

C: I wasn't a huge fan of this problem. I know of two solutions: a boring FFT approach and a bitset approach that relies on a pretty nice observation. The problem is that especially in the MHC format, it seems close to impossible to reject FFT (especially on a setup that e.g. uses AWS to run all test cases in parallel) but accept the bitset solution without multithreading. In this case, it looks like it was possible to push the FFT solution through with basic multithreading (this was surprising to me given the constraints--maybe the test data is weak?). This was disappointing to me since it rewards e.g. making assumptions about the strength of the test data, having a stronger PC, spending time on setup optimization, etc.

D: Fine problem, though most of the individual steps felt fairly standard.

E: Nice problem--for a while it seemed like the solution would involve lots of messy casework, but the implementation turns out not to be that bad after you write the $$$n = 6$$$ brute force.

In case it's of interest, my progress through the round looked like:

• Spent 20 minutes on A before moving on to B
• Solved B in 12m
• Looked at scoreboard and moved to D, solved in 24m
• Saw C had a solve and spent 45m thinking about it, came up with the bitset solution after the first 30m or so but convinced myself it was unintended/would TLE
• Switched to E and worked on it for the remainder of the contest; I got fairly close, but ended up making too many mistakes along the way to finish in time. (In retrospect, I was more reluctant than I should have been to use the brute force as a subroutine, even though I had already written it to confirm that a solution always exists.)

Not realizing that my solution to C was fast enough was fairly sad, though it's not obvious that implementing C and then solving A in the last 90m of the round would have been much easier than solving E in the last 75m.

My solution sketches:

A: The problem is trivial when K = 1. When K = 2, color the cells in a checkerboard pattern; the answer is bounded from below by the number of cells of the more common color, and we can achieve this bound e.g. by tiling each row with horizontal dominos.

Now assume K > 2. A general strategy is to move down the pyramid from top to bottom, alternating between left-to-right and right-to-left. When we move down from level $$$i$$$ to level $$$i+1$$$ on the right side, we don't need to do anything special as long as our current component has at least two cells remaining, but if we have only one cell remaining, coloring the rightmost cell on level $$$i+1$$$ won't be connected to our existing component on level $$$i$$$. If this happens, shift this component to the right by one cell, then fill in the gap when we're traversing right to left on the next level.

B: Let dp[i] be the minimum cost to satisfy the constraints on lightbulbs 1..i. To transition from dp[i] to dp[j], we need to include a string of consecutive bulbs that will satisfy all conditions from i+1 to j. Each condition requires our string to have at least some fixed length and to start before some fixed point. Using prefix sums, we can precompute the minimum cost of a string of a given length starting at or before a given point in the array, allowing us to do each transition in O(1) for a total complexity of O(n^2).

C: Imagine we're building our string iteratively. We start with $$$W_1$$$, then, for each $$$i \gt 1$$$, we need to add on a suffix of $$$W_{i}$$$ such that the prefix of $$$W_i$$$ occurring when you drop this suffix matches the same-length suffix of $$$W_{i-1}$$$. This condition gives us several possible suffix lengths we can add on in step $$$i$$$, and we need to determine which total lengths can be achieved by choosing one suffix length for each $$$i$$$.

The key insight is that the set of suffix lengths we can choose in step $$$i$$$ consists of an arithmetic progression plus at most $$$O(\log |W_i|)$$$ extra lengths. To prove this, suppose that the prefix lengths of $$$W_i$$$ that match suffixes of $$$W_{i-1}$$$ are $$$p_1, p_2, ..., p_k$$$ in descending order. Because these prefixes of $$$W_i$$$ match the corresponding suffixes of $$$W_{i-1}$$$, we can think of $$$p_j$$$ as the longest shared prefix/suffix in the prefix of $$$W_i$$$ with length $$$p_{j-1}.$$$

The insight here is that we can break the sequence $$$p$$$ into $$$O(\log |W_i|)$$$ contiguous subsequences, each of which is an arithmetic progression. The idea is that if $$$p_j \geq \frac{p_{j-1}}{2}$$$, then the period of the first $$$p_{j-1}$$$ characters of $$$W_i$$$ must be $$$p_{j-1} - p_j$$$. Moreover, this must also be the period of the first $$$p_j$$$ characters (this can be proven by contradiction using the fact that $$$p_j \geq p_{j-1} - p_j$$$), which implies $$$p_{j+1} - p_j = p_j - p_{j-1}.$$$ This is enough to show that if we split the sequence $$$p$$$ wherever $$$p_j \lt \frac{p_{j-1}}{2}$$$, each subarray is an arithmetic progression, so $$$p$$$ can be written as the concatenation of $$$O(\log |W_i|)$$$ arithmetic progressions. (Credit to Golovanov399 for catching an incorrect assertion that used to be in this section; any remaining errors in this explanation are my own.)

Now, maintain a bitset representing the values we can reach using the first $$$i$$$ words. To insert word $$$i+1$$$, we need to construct the values we can reach by using each of our arithmetic progressions.

Fix one of our arithmetic progressions and start by adding the first term of the progression. Then, if there are $$$k$$$ terms in our progression and the common difference is $$$d$$$, we need to consider adding each of $$$0, d, \cdots, (k-1) \cdot d$$$ to our length. This can be handled using a trick similar to one often used to optimize subset sum DP: consider adding any subset of $$$d, 2d, 4d, \cdots$$$ until you get to the largest $$$2^q d$$$ with $$$2^q \leq k-1$$$, then add an optional $$$(k-1)d$$$ to cover the remaining values. This takes another $$$O(\log_2 |W_{i+1}|)$$$ bitset operations per arithmetic progression.

This bounds our complexity as $$$O \left( n |W_i| + \frac{K}{64} \cdot n \log^2 |W_i| \right)$$$, though in a comment below, dorijanlendvaj proves a stronger bound that eliminates a log from the second term. Even with one log, this seems a little tight, though the other comments suggest that the tests are weak enough that this should pass comfortably.

D: Apply Mobius inversion so that we need the sum of distances over all pairs $$$(u, v)$$$ where $$$u$$$ and $$$v$$$ are multiples of $$$k$$$, for $$$k$$$ from $$$1$$$ to $$$n$$$. Let $$$v_1, v_2, \cdots, v_m$$$ be the vertices that are multiples of $$$k$$$. Then, the sum of the distances is

The former sum can be computed with a simple DFS, iterating over the factors of each vertex. The latter can be computed using small to large merging. For each vertex, we'll build a map from $$$k$$$ to the number of vertices in the subtree of $$$v$$$ that are multiples of $$$k$$$. When we merge two sets, we can count the number of pairs with LCA $$$v$$$ and update our sum accordingly.

The total number of elements in each of our base sets is $$$\frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} = O(n \log n)$$$. Implementing small-to-large merging using a map gives a complexity of $$$O(n \log^3 n )$$$, though with a good constant factor since we only keep one of any two terms with the same $$$k$$$ when we merge. Alternatively, we can omit the map, which makes the implementation slightly messier but gives an $$$O(n \log^2 n)$$$ complexity (thanks to arvindf232 for pointing this out).

E: We'll iteratively try to move two 0's to the left of the string. As we do so, we'll use the fact that using a brute force, we can permute any six consecutive elements arbitrarily using at most 11 operations. For simplicity, I'll assume that there are no pairs of 0's at the start of the string; if this isn't the case, just pair the 0's at the start of the string with each other. The algorithm is as follows:

• While there are fewer than two 0's in the first four positions, perform an operation where we greedily try to assign all 0's to one group and all 1's to another.
  • We can prove that the first iteration of this is guaranteed to put at least two 0's in the first $$$n/2$$$ positions. Then, the second iteration is guaranteed to put at least two 0's in the first four positions.
• If there are at least six positions remaining, use the brute force to move 0's to the first two positions. Otherwise, we can apply the brute force to the last six positions (noting $$$n \geq 3$$$) to achieve the desired configuration.

If there's one 0 left to place after this, we can move it to the first position in one operation.

This may be extremely unrealistic, but I really do hope onsite finals could happen.

I am still very sad that the exact year I am capable to get into finals is the (almost) exact year onsite finals got discontinued. Getting into finals feels a bit without substance now...

Dear SecondThread, Please Design a proper Mail Eco-system to inform contestants about changes(date,time) & result.

After the Rank improvement of participants, they are not even aware that they have Qualified for the next Round. I have seen a lot of Posts about this on Twitter. Most of the participants faced this issue and uncertainly they missed their next Round. I Hope next year it will be Better

Thank You!

I didn't participate in the round (even though I qualified), but when I went to check the standings today, I saw that I had gotten rank 198, enough for me to get a special T-shirt!

Jokes aside, literally everyone who qualified to round 3 is top 200, as there are only 197 participants with a positive score. What will be done about the T-shirts? I'm not sure if it is already specified somewhere that you need to have a positive score to get a T-shirt, but in case it isn't, the most reasonable thing to do, in my opinion, is to just give the special T-shirt to those 197.

I wrote problem A. While waiting for the public editorial to be available, you can check my solution here (this is a copy of the original doc that I shared with other Meta folks as a problem submission)

Excuse me, I see that there were 197 persons have positive score

So all the zero — score would be placed at 198th

So are they counted in top 200 ?

Is it true that the participants in the AI track confused it for a format where they can submit solutions generated by public LLMs? Curiously, out of 25 participants in round 3, 22 are from India, 1 is from Bangladesh, and 3 have unspecified country but are probably from India or BD.

Is anyone still hoping to get a T-Shirt? Seems like we are being scammed this year too :(

When we can expect T-shirt claim option ? and for remaining people in top 200... will they select based on Round 2 rankings ?

Any update about the T-shirts?

Not a good management this year.. funny thing is that my round 2 rank is still improving somehow lol, it became 3-4 ranks better.

what if someone who was just more than 500 ,say 505-520 , till beginning of round 3 and wasn't qualified for round 3 , now after plag checks they come<=500 , then ,just curious ??