Leftist_G's blog

Codeforces Round 1083 (Div. 2)
By Leftist_G, 2 months ago, In English

你好, Codeforces!

We (DBOI Team) are very glad to invite you to participate in Codeforces Round 1083 (Div. 2), starting at Feb/26/2026 17:35 (Moscow time).

There will be 7 problems for you to solve in 2 hours and 30 minutes. All problems were authored and prepared by cool_milo, StayAlone and me. This round will be rated for all participants with rating below 2100.

I would like to thank the following list of very strong individuals for making this round possible:

Picture of authors (and there are also some testers off-screen who are shy to show their faces):

(Guess which handle belongs to each author!)

Score distribution: $$$500 - 750 - 1250 - 1750 - 2500 - 2750 - 3250$$$.

Good Luck & Have Fun!

UPD: Editorial is out.

  • Vote: I like it
  • +377
  • Vote: I do not like it

»
2 months ago, hide # |
← Rev. 4  
Vote: I like it +20 Vote: I do not like it

Good luck on Div 2!! Special support to Leftist_G, StayAlone, and cool_milo! Show some high performance today, guys. May the force of competitive programming be with you! But unfortunately i cant participate in round...

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +62 Vote: I do not like it

As a tester, fake_banana (a.k.a. wdnmdwrnmmp) will win IOI 2026!

→ Reply
»
2 months ago, hide # |
← Rev. 2  
Vote: I like it +12 Vote: I do not like it

你好，Codeforces!

it is really unusual to see Chinese in codeforces announcement.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

As a ?, good luck & have fun!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +54 Vote: I do not like it

Hello, codeforces! I am cool_milo, as we diligently prepared the problem for months, the quality of the round is definitely qualified. Hope you positive rating delta & have fun! :P

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

GLHF!!!

→ Reply
»
2 months ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

This photo is really amazing cool_milo, StayAlone and Leftist_G

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

As the author's classmate, I believe this round will be quite wonderful. By the way, hope this round goes successfully!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Congratulations on the preparation of the round! I organized local competitions for my classmates, in the CodeForces format, and I understand that it is difficult to organize a competition even for a small group. I'm still a beginner and I solve A and B consistently, but every round I set myself the task of solving C. Tomorrow at 17:35 Moscow time I will be at your round and I will try to solve as many problems as possible

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

大家好, as a french, I enjoy french fries a lot so I hope I'll enjoy your round too :)

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

A 7-problem Div 2 with French fries and rap lore is exactly what we needed to end the week. Huge thanks to cool_milo, StayAlone, and the massive team of testers for the effort! (I'm guessing the one on the left in the photo is cool_milo). Good luck and high rating to everyone!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

I did poorly in the previous educational round. I wish I can get my specialist back in this round.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

French fries pig?

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

As a tester, I think the problems are insteresting! welcome to participate this round!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Have a nice day,everyone ༼ つ ◕_◕ ༽つ

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

As a tester, I hope everyone can come and participate in this interesting competition. GL & HF!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

"你好" Finally, some Chinese in codeforces!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

你好

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

aa

→ Reply
»
2 months ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

They're very "handsome"

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Have to participate after seeing "你好, Codeforces!"

→ Reply
»
2 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I love Dev 2 contests, even though my rating may decrease

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Solution of E: For any subarray B of A, assume we need to flip it. If there exist a pair of array S, T (T could be empty but S could not) such that B = S + T + S, then rev(B) = rev(S) + rev(T) + rev(S), so we can flip S, T, S instead of B. For any division of A, if no subarray fliped has property mentioned above, it will be the only division with the largest number of subarrays among all divisions with same result after flipping. So we can solve by dp: let dp[i] = the number of valid division of A[1...i], the transition will be dp[j] = sum(j<i, A[(j+1)...i] cannot be represented with STS form)(dp[j]), where the condition could be checked using KMP algorithm.

Solution of F: A graph with only nodes of even degree can be split into some cycles, look at "cells" surrounded by these cycles. If we add a path with positive sign and a path with negitive sign on every edges "inside" these cycles (which doesn't change the sum of paths), we can split all paths into some cells with four edges surrounded, with positive sign on the edges above and left, negative sign on the edges right and below. So we can represent the problem as "choose some cells with the largest sum of contribution, where the contribution of each cell is the weight of edges above and left, minus the weight edges right and below". For any invalid edge, the two cells adjacent to it must be both chosen or both not chosen, so we need to add a link between adjacent cells of any invalid edge (if any of them is outside the grid, mark another cell as invalid), then for every connected component formed by links, we only need to choose these with positive total contribution and without invalid cell.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In E, how can we prove that $$$ans_i = \sum{ans_j}$$$ for all $$$j \lt i$$$ such that $$$a_{[i:j]}$$$ isn't (1) a palindrome or (2) has a common prefix / suffix?

I initially had a way more complicated condition instead of (2) before realizing it didn't pass samples and just observing that using (2) instead made it match the test case's answer. I can intuitively see why it might prevent over-counting, but how to prove it?

→ Reply
  • »
    »
    2 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    We denote the reverse by $$$r$$$. I would call the array a string sometimes. I denote $$$a_ja_{j+1}...a_i=a_{[j:i]}$$$.

    If $$$a_{[j:i]}$$$ is a palindrome then flipping it won't do anything (string stays the same).

    If $$$a_{[j:k]}=a_{[i-k+j:i]}$$$ then $$$r(a_{[j:i]})=r(a_{[i-k+j:i]})+r(a_{[k+1:i-k+j-1]})+r(a_{[j:k]})=(r(a_{[j:k]})+r(a_{[k+1:i-k+j-1]}))+r(a_{[i-k+j:i]})$$$. Note the $$$r(a_{[i-k+j:i]})$$$ in the last expression is a shorter suffix and hence we must not double count here.

    For any other case, reversing $$$a_{[j:i]}$$$ would make $$$r(a_{[j:i]})$$$ a unique suffix that was never seen before.

    Therefore we only add $$$ans_j$$$ for the "any other case" part.

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Instead of Finding how many S can be transformed into T, We can calculate how many distinct S we can get by reversing the subarrays of S. (why? If T can be obtained from S then S can also be obtained from T by re-applying all the operations)

    Now, dp[i] = how many distinct arrays can be get from A[i ... n]

    dp[i] = sum(dp[j]) {considering we will reverse A[i .. j-1] and concatenate all the distinct arrays we can get from A[j .. n]

    Now , if A[i .. j — 1] is not a proper prefix then then there exists a k such that A[i .. k] == A[j-k-1 .. j-1] then reverse(i ..k) + reverse(k+1 .. j-k-2) + reverse(j-k-1, j-1) == reverse(i..j-1) thus this is already counted when we made a transition from dp[i] to dp[k-1]

    Thus to count unique arrays we can only transition to j's such that A[i ... j-1] is a proper prefix.

    → Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Got stuck in problem D, but it was a nice contest! Can anyone give me some hint for D?

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Hint: The valid final array if plotted will always be in "V" shape. Now maximize the length of each "leg" of the "V"

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      oh cool, let me see here.

      → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I think this doesn't work in this case

      15
7 4 10 12 9 14 5 3 8 11 1 15 2 13 6

      we can make 12 9 5 3 8 11 15 which is V-shaped and has size 7. but the answer is not 8 (15-7) .. it is 9 ... this is last test case in the question

      → Reply
      • »
        »
        »
        »
        2 months ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        Ah, you're right, I'm oversimplify my explanation too much and missed one more rule: if you plot both the "V" and the full array, the "V" plot should be always above or equal to the full array plot.

        Here is in your given case, there are part of the "V" that is lower than the full array plot:

        → Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Any hint on problem B??

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Try to think about the divisors of a number N and how this can help you to find the answer

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    u have to get all the unique prime factors and multiply them to get the answer

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Prime factorize n and think for each factors when dividing k^n.

    → Reply
  • »
    »
    2 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Try to prove this :

    Let

    $$$ x = p_1^{e_1} \cdot p_2^{e_2} \cdots p_n^{e_n} $$$

    be the prime factorization of a positive integer $$$x \ge 2$$$, where
    $$$p_1, p_2, \dots, p_n$$$ are distinct primes and
    $$$e_1, e_2, \dots, e_n$$$ are positive integers.

    Prove that

    $$$ \max(e_1, e_2, \dots, e_n) \lt x. $$$
    → Reply
»
2 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

C is so cursed!

→ Reply
»
2 months ago, hide # |
← Rev. 2  
Vote: I like it +22 Vote: I do not like it

Am I the only one who feels C >> D in terms of difficulty?

At least for me C required some thinking even after identifying "solve in reverse" to figure out how to correctly obtain the lexicographically minimum with different sized arrays.

Meanwhile D just boiled down to "A cool array is a trough", "The operation can only delete smaller elements so each side is a sequence of next largest elements", "Stack go brrr"

Not that I think C > D in terms of quality, I probably still like problem D more :)

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Yup, problem C felt way tougher. D was way easier.

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    i get the idea of reverse each array then sort it

    take the smallest array then removing the element from previous smallest array again sort array this time and repeat but not able to implement it :/

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Yeah, also the implementation of C felt quite tedious (atleast for me).

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      This. I thought it was a simple problem but didn't like the implementation. I spend some time trying to come up with a nicer way to solve it, but got nothing better.

      → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Wait, so you don't have to use lazy propagation on D?! I MIGHT have overkilled it.

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    C: More coding focused (storing sequence, removing duplicate, comparing sequence, removing sequence, a bit complex data structure, prone to indexing bug (me finally AC after 3 tries because if indexing bug o_o))

    D: More thinking focused (easy to code the formula :D)

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Use almost 30 mins to think about a greedy for C, but used only ~3 mins to realize that D is a dp on cartesian tree. C>>D imo.

    → Reply
»
2 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Is it just me or have the runtime limits on CF problems gotten stricter lately?

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Problem C was an arch-nemesis

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Great problems! So are the songs. I was listening to the song 'Take It Away' during most of the contest duration. Thanks for the round!

→ Reply
»
2 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

E is very similar as GDKOI2025 day2 probG

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Simon destroyed me lol.

I was already destroyed after 2 W.A on C but then my stupid brain misunderstood E and left D to solve E.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

I enjoy solving E, F very much, thanks for the round!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

i really enjoyed todays div2 contest. first time solved a and b fast

→ Reply
»
2 months ago, hide # |
← Rev. 3  
Vote: I like it +14 Vote: I do not like it

The problem E is similar to GDKOI2025 Day2 G.

Problem E can be reduced to this problem by selecting intervals of length 1.

I think this is just a coincidence, not intentional.

The original problem is in Chinese,you may use a translation tool to read it.

Related discussion: https://www.luogu.com.cn/discuss/1254294

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +32 Vote: I do not like it

Problem E’s test cases are weak, so my fake $$$O(N^3)$$$ solution passes the system tests.

364520080

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

G is pretty cool, thanks

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My submission of E only ran pretest. What’s wrong with it?

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what mean DBOI team?

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Chinese people are just so good at coding that's unbelievable.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

I really think C is not that good , it doesnt look like a good position to put C

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My title finally drop back to green. Still stuck on C without any ideas...

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice contest, had fun. For the D problem, I tried the following, however it gave TLE in test case 15-16ish : Mainly keep track of l,r, find the largest in this interval, now this needs to be sent to the very ending, hence deletion according to that gave me $$$min(ans(a,l,pm)+r-pm-1,ans(a,pm+1,r)+pm-l)$$$. I thought like quick sort it will have O(nlogn) average time complexity, however that didnt work... tried few early stopping condition, but still it wasnt good enough.

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The divide and conquer solution for D also works.

    But I haven't figured it out how ? Like how can I be sure that it wouldn't TLE on some specific testcase ??

    → Reply
  • »
    »
    2 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +5 Vote: I do not like it

    O(nlogn) is achievable only with middle cut on range. Here it's not guaranteed that maximum always happens to be in the middle. A counter case would be a strictly increasing sequence which leads to quadratic time.

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      How so can you say a test case? A strictly increasing seq will take O(n) only

      → Reply
      • »
        »
        »
        »
        2 months ago, hide # ^ |
        ← Rev. 3  
        Vote: I like it 0 Vote: I do not like it

        You are right but you can reverse every adjacent pairs in increasing sequence,

        2 1 4 3 6 5 ...

        This should easily TLE author's code.

        → Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

364530384

i don know why my submission skiped.

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It was skipped because it was identical to the previous submission.

    The CodeForces judge doesn't retry submissions that are identical to earlier submissions because usually the verdict will be the same. In this case, you changed the compiler setting to fix a compiler error, so it would have made sense to retry it, but apparently the CodeForces judge isn't smart enough to realize this.

    You can usually force recompilation by making some small changes to the source code when that happens.

    → Reply
»
2 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

in 3 attempts I became a specialist

→ Reply
»
2 months ago, hide # |
← Rev. 2  
Vote: I like it -10 Vote: I do not like it

became a specialist in 4 days

image

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

So, how exactly should Problem D be solved? I can only reason that the final answer is either monotonically increasing/decreasing, or shaped like a "V". How should I approach the next step? Can you give me some hints?

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think middle one is StayAlone, left one is Leftist_G, and right one is cool_milo.

Because:

The right one has glasses both on Codeforces and in real life.

The left one is a little chubby, like the cat in the avatar.

So only one account is left for the middle one.

Am i right?

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How G?

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Well, I will announce the answer. In the picture, the right is StayAlone, the middle is cool_milo, and the left is me.

→ Reply
  • »
    »
    2 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Ok, but i thought that the right one has a glasses, so in Codeforces he will select someone with glasses.

    → Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Not only is Ginge a known cheater that did well on this round, he was able to gain rating on this round as a Master.

Presumably what happened is that he had already registered for the next div2 before the rating update happened. Should this be allowed? Is there any precedent on this?

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it -14 Vote: I do not like it

    before just saying i am a cheater please give some proofs

    i train on usaco and its just time i will maintain my rating im usaco plat and trying to make my codeforces similar to it

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      You are clearly cheating, your 3 contests are already skipped and transition from rank 375 to rank 3 in just 5 days by some 2200 person is clearly impossible.

      → Reply