CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

Hello Codeforces,

We are very glad to invite you to participate in CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!), which will start on Saturday, November 25, 2023 at 14:50UTC. You will be given 8 problems and 2.5 hours to solve them. The round will be rated for everyone.

All the problems are written and prepared by lanhf, Mike4235, thenymphsofdelphi, xuanquang1999 and me.

We would like to give our sincere thanks to:

• errorgorn for his wonderful coordination!
• Alexdat2000 for translating problem statements.
• Um_nik and conqueror_of_tourist for Legendary Grandmaster testing.
• jeroenodb, Kuroni, dario2994 and dreamoon_love_AA for International Grandmaster testing.
• generic_placeholder_name, MofK, minhcool, dvdg6566 and magnus.hegdahl for Grandmaster testing.
• dantoh for International Master testing.
• apoorv_me, 18o3, beepbeepsheep, jamessngg, zengminghao, oolimry, iLoveIOI, pavement and jamielim for Master testing.
• Kofta, Dewi, Nahian9696, bensonlzl and Myrcella for Candidate Master testing.
• ABalobanov, AVdovin, Blagoj, teruel, xink and Antonn_114 for Expert testing.
• BeezMinh, aureg109, Yoo_Jeongyeon, Sunnyyyy and SYY for Specialist testing.
• NVGU for Pupil testing.
• vszda, tibinyte and hminh for Newbie testing.
• MikeMirzayanov for the great codeforces and polygon platform.
• You for participating in the round.

The score distribution is .

Hope everyone can enjoy the round!

Congratulations to the winners!

Congratulations to the first solves as well!

UPD1: The contest is delayed by 15 minutes due to prior issues with the registration system in order to make sure everyone is correctly registered. Please double-check that you are registered.

UPD2: Editorial

And here is the information from our title sponsor:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 7.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 7 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

• 1st place: 1,024 TON
• 2–3 places: 512 TON each
• 4–7 places: 256 TON each
• 8–15 places: 128 TON each
• …
• 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 7 and hope you enjoy the contest!

• 3 weeks ago, # ^ | That's what they all say

  • 3 weeks ago, # ^ | I am absolutely sure of my words

• 3 weeks ago, # ^ | As a newbie...i was completed 1st two problem in 23 minute and then after 2+ hours i'm trying to solve problem C. But, i can't . Anyway, It's 1st time 1 complete 2 problem in div. 2. Thanks all writer and tester...!

  • 3 weeks ago, # ^ | Thanks to you for participating!

    • 3 weeks ago, # ^ | welcome brother...!

  • 3 weeks ago, # ^ | i am also tracked in problem C in div.2 for many times. often their solution are greedy... it is a little hard to construct a methed and prove its validity.

    • 2 weeks ago, # ^ | yes bro.!

• 3 weeks ago, # ^ | No they are mine

• 3 weeks ago, # ^ | As a tester, no.

• 3 weeks ago, # ^ | Reverse the TON and that is answer..

• 3 weeks ago, # ^ | leetcode biweekly is clashing with this contest

  • 3 weeks ago, # ^ | yes, so do codeforces

    • 3 weeks ago, # ^ | kid named codeforces: :(

      • 3 weeks ago, # ^ | Kid named leetcode o.0

• 3 weeks ago, # ^ | How do u become a tester? Do they reach out to you or do you apply to be a tester?

  • 3 weeks ago, # ^ | I know the creator personally but you can randomly be invited to test

• 3 weeks ago, # ^ |

• 3 weeks ago, # ^ | ← Rev. 2 →   +9 nvm i realized they give a shitton of TON in total

• 3 weeks ago, # ^ | It's cryptocurrency

  • 3 weeks ago, # ^ | Thanks,but how can I turn the TON into common money?

    • • 3 weeks ago, # ^ | Too terrible, it has demotivated me.

        • 3 weeks ago, # ^ | To have TON is better than have nothing

    • 3 weeks ago, # ^ | You can exchange them to USD or whatever currency you need. At least, I think so

• 3 weeks ago, # ^ | hope i'll not become a newbie after this contest.... ):

  • 3 weeks ago, # ^ | you'll be cyan very soon in'sha'allah brother...!

    • 3 weeks ago, # ^ | inshaallah .. best of luck mate

• 3 weeks ago, # ^ | I hope to be a pupil too, gotta push hard

  • 3 weeks ago, # ^ | best of luck brother...please pray for me...!

    • 3 weeks ago, # ^ | Good luck next time

      • 3 weeks ago, # ^ | Thank You vaia...!

  • 3 weeks ago, # ^ | Congratulations!

• 3 weeks ago, # ^ | The previous contest has become unrated I guess.

  • 3 weeks ago, # ^ | Definitely not, unless I missed some announcement that said that. Sometimes ratings just take a long time to update.

• 3 weeks ago, # ^ | That problem (problem H) has two versions H1 and H2: an easier version and a harder version. Solving the easier version gives points, solving the harder one gives points. It might seem really stupid: why does the harder version give less points? The reason is that almost always the solution to the harder version directly solves the easier version (you can submit the same code to both and get AC). Thus, solving the harder version effectively gives points, i.e. it is only slightly more difficult than the easier version.

• 3 weeks ago, # ^ | Ohh I have made it! Lets goo! Next step Specialist!

• 3 weeks ago, # ^ | There was no guessing involved wdym.

• 3 weeks ago, # ^ | Just to be sure, do we need to use segment tree in D?

  • 3 weeks ago, # ^ | ← Rev. 2 →   +1 No, set plus some annoying math and casework is enough

    • 3 weeks ago, # ^ | please elaborate?

      • 3 weeks ago, # ^ | The rough idea is that you maintain indices of ones and twos, then you consider the first 1, if sum to the right including it is at least x it is possible. Otherwise we need to include the twos to the left, so you try to get the max sum starting from the first 1 with the same parity as x by removing the suffix of twos, and a one.

    • 3 weeks ago, # ^ | What annoying math and what casework

      • 3 weeks ago, # ^ | Okay, it’s not that bad, it can surely be done more elegantly. But my solution was quite casework-based because… don’t know why.

  • 3 weeks ago, # ^ |

  • 3 weeks ago, # ^ | Nope, can be done with a regular set.

    • 3 weeks ago, # ^ | Oh, yeah, right, to maintain first and last positions of '1'?

      • 3 weeks ago, # ^ | Yes and a heap (priority queue) is even faster

        • 3 weeks ago, # ^ | Thanks, i actually wasn't sure which data structure could deal with this

  • 2 weeks ago, # ^ | segment tree also works you have to find the prefix sum just less than the given sum it can be done using bs on segment tree and then you just have to think how you can increase the subarray sum by 1

• 3 weeks ago, # ^ | Man what about Problem-D .....xD. Any approach?

• 3 weeks ago, # ^ | Still gready. Sort b and cyclically shift it to the left by X. So you get a gready answer for sorted a. Then "unsort" b by 'a' and check answer is ok.

  • 3 weeks ago, # ^ | It worked but still can't understand why shifting to left works, Are we garunteed to get a new ai > bi on every shift? (assuming there is an answer).

    • 3 weeks ago, # ^ | Yes, it's tricky. But intuition is simple. Lets consider some worst case after shift (x = 3): a = 1 2 3 | 5 6 7 b = 7 8 9 | 4 5 6 As we can see, if answer is exists and a is sorted, b must be also sorted.

      • 3 weeks ago, # ^ | Thanks, I understand now. So to put it in words : for the current smallest element of ai the best current answer is next maximum of bi, and at some point in the middle if this condition doesn't hold that's because there are not enough elements on b that can satisfy the smallest elements of a so no solution.

• 3 weeks ago, # ^ | ← Rev. 2 →   +3 I have not seen your code, it's looks quite complex to be honest, but based on your idea, Isn't answer of this Test Case is No, but should be YES Array : 1 2 2 queried sum : 4

• 3 weeks ago, # ^ | Store the positions of s in the array in a set. Now calculate the maximum even and odd subarray sum you can get. If the whole array has an even sum, the maximum even subarray sum is just this sum. To find the maximum odd subarray sum, we need to remove a single from the array. From the first and last s, find which one is closer to the edge of the array and remove it along with any s between it and the end of the matrix. You can get similar results for if the whole array has an odd sum, and need to recompute these maximum odd and even subarray sums each time an element is updated. Then when we get a subarray sum query, check if its less than the maximum of corresponding parity.

• 3 weeks ago, # ^ | First, store the positions of all 1's in a set. Then you can retrieve first and last 1's easily. For the first 1, there will be only 2's before it, and for the last 1, there will only be 2's after it. Let l be the position of the first 1, and r be the position of the last 1. For any prefix ending with a 1, you can get all elements from 1 to the sum of the prefix, and for any suffix ending in 1 you can do the same. You can also add the 2's before and after the suffix and prefix, respectively. So for a query, you only need to check if either x is less than this suffix and prefix sum, or that it is a multiple of two(which is less than the total number of twos before or after l or r) above the suffix or prefix sum. Handle prefix/suffixes with a segment/fenwick tree. Updates queries can then be done easily. Implementation

• 3 weeks ago, # ^ | Same man same! Wasted more than 30 minutes in it.

• 3 weeks ago, # ^ | what was your approach for D

• 3 weeks ago, # ^ | D>>C, C was too trivial kind off repeated idea

• 3 weeks ago, # ^ | In problem E, can you please elaborate on how to calculate the number of ranges contained inside T[i].

  • 3 weeks ago, # ^ | ← Rev. 6 →   +7 First, these ranges are considerd circular, which means for [L, R] when R<L, this range is the union of [L, n] and [1, R]. To solve this issue we can turn in into [L, R+n], and for any other range [L2, R2], if L2<=R2, then we check if [L, R+n] contains [L2, R2] or [L2+n, R2+n] (they can't both be contained), and if R2<L2, we check if [L, R+n] contains [L2, R2+n]. Then we turned the problem into this: There are some pairs of (l[i], r[i]), we have some queries in form (L, R), find number of i such that L<=l[i]<=r[i]<=R. We can solve it by offline: Sort queries by L, and for a certain i, we add 1 to r[i] on time 1, and minus 1 to r[i] on time l[i]+1. Therefore, we add 1 to r[i] between time 1 and l[i]. Then for query (L, R), we find the prefix sum on [1, R] on time L, which will be the answer of the query.

• 3 weeks ago, # ^ | Thanks :) its really helpful

• 3 weeks ago, # ^ | You can represent the distance from where a number is and a number should be as segments. Then you need to count for each segment, the number of other segments which it completely overlaps.

  • 3 weeks ago, # ^ | ← Rev. 2 →   0 why completely isn't enough to be an intersecting

• 3 weeks ago, # ^ | you don't need it

  • 3 weeks ago, # ^ | yep that's what I figured out, but I'm curious

• 3 weeks ago, # ^ | Yes, that's what I did at least

  • 3 weeks ago, # ^ | Oh no, I took much time to realize it (>...<)

• 3 weeks ago, # ^ | You can use BIT instead of ordered_set also

  • 3 weeks ago, # ^ | Yeah, I would've gone for BIT if OS hadn't fit in TL.

• 3 weeks ago, # ^ | Super cool F indeed! Can you share your solution of G?

  • 3 weeks ago, # ^ | Divide numbers into groups. Repeating Following Steps: Find the maximum in each group Find the maximum of the maximums and take it.

    • 3 weeks ago, # ^ | I did a spaghetti implementation, I get MLE and I can't replicate it with a non-adaptive grader :(

• 3 weeks ago, # ^ | Yeah, Give me his contact details

• 3 weeks ago, # ^ | If you consider cyclic subarray i,...,a[i]. Then ans[a[i]] is going to be the number of elements which you push out of this subarray because each operation pushes 1 element out of this subarray. An easier implementation would be subtract number of elements which does not need to be pushed from total elements like this

• 3 weeks ago, # ^ | Take a look at Ticket 17161 from CF Stress for a counter example.

• 3 weeks ago, # ^ | Congrats on solving all the problems.

• 3 weeks ago, # ^ | ← Rev. 2 →   +11 Congrats on #1! I also enjoyed G and H, though G ended up being too hard for me. :)

• 3 weeks ago, # ^ | Yes its because ran super quickly so I had to make bigger. I doubt there are any linear solutions.

• 3 weeks ago, # ^ | Why is my same algorithm unaccepted (((

  • 3 weeks ago, # ^ | You forgot to enable highest level of optimization with Advanced Vector Extensions: #pragma GCC optimize("Ofast") #pragma GCC target("avx") If you will do it, you will get accepted. Link to your accepted solution

• 3 weeks ago, # ^ | Hi can you try it again? I think it is fixed

• 3 weeks ago, # ^ | He is a tester. Do you think this is fun?

• 11 days ago, # ^ | ← Rev. 2 →   +8 Have you gotten them? (I have the same question)