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 Nov/25/2023 17:50 (Moscow time). 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.
- tyr0Whiz, 18o3, beepbeepsheep, jamessngg, zengminghao, oolimry, iLoveIOI, pavement and jamielim for Master testing.
- Kofta, debugging_since_epoch, Nahian9696, bensonlzl and Myrcella for Candidate Master testing.
- ABalobanov, AVdovin, Blagoj, teruel, xink and Antonn_114 for Expert testing.
- BuzzyBeez, Maikyou, 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 $$$500-1000-1500-2000-2250-2750-3250-(4000+1000)$$$.
Hope everyone can enjoy the round!
Congratulations to the winners!
- Radewoosh
- ksun48
- ecnerwala
- maroonrk
- jqdai0815
- hos.lyric
- zh0ukangyang
- 244mhq
- Vercingetorix
- BigYellowDuck
Congratulations to the first solves as well!
- A: dXqwq
- B: tourist
- C: tourist
- D: tourist
- E: tourist
- F: ksun48
- G: Radewoosh
- H1: ksun48
- H2: ecnerwala
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!
As a tester, i know, that problems are interesting and the round itself is exciting
That's what they all say
I am absolutely sure of my words
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...!
Thanks to you for participating!
welcome brother...!
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.
yes bro.!
As a contribution, please give me tester
As a specialist, I miss my Expert color when I tested this round ;(
Anyways, problems are very interesting; you should read all problems' statements.
Good luck ;)
Do I get TON
No they are mine
As a tester, no.
Reverse the TON and that is answer..
Why there's no 1,024-2047 places: 1 TON each?
@everyone announcement is posted https://codeforces.net/blog/entry/122539. Can farm contribution if you want
leetcode biweekly is clashing with this contest
yes, so do codeforces
kid named codeforces: :(
Kid named leetcode o.0
As a tester, I forgot the problems. But they were enjoyable I remember.
-1024 TON
As a tester I can guarantee that the problems are good
How do u become a tester? Do they reach out to you or do you apply to be a tester?
I know the creator personally but you can randomly be invited to test
good luck & fun !!!
Good luckkkkkkkkkkkkkkkkkkkkk
But I did not get the prize of round 6 (xd
Me too
Me too
Me too
)
The main writer when you cannot solve the problems.
18o3 the 'TESTER' ::orangeheart::
as a participant, increase TON
nvm i realized they give a shitton of TON in total
I hope to win the money for two KFC-Crazy-Thursday!
I hope to win the money , I need to take care of my family.
Auto comment: topic has been updated by maomao90 (previous revision, new revision, compare).
What's TON?If I get the prize,how can I turn the TON into common money?
It's cryptocurrency
Thanks,but how can I turn the TON into common money?
Idk
Too terrible, it has demotivated me.
To have TON is better than have nothing
IKR :)
You can exchange them to USD or whatever currency you need. At least, I think so
Hope i'll became pupil after this contest ...!
hope i'll not become a newbie after this contest.... ):
you'll be cyan very soon in'sha'allah brother...!
inshaallah .. best of luck mate
I hope to be a pupil too, gotta push hard
best of luck brother...please pray for me...!
Good luck next time
Thank You vaia...!
Congratulations!
:(
Good luck to all the participants, do your best ^_^
Why are you wasting time testing Codeforces round Yoo_Jeongyeon! We were waiting for
TW-LOG @ 5TH WORLD TOUR ‘READY TO BE’ ep.JEONGYEONwill the rate updated before the upcoming codeton contest lol
The previous contest has become unrated I guess.
Definitely not, unless I missed some announcement that said that. Sometimes ratings just take a long time to update.
What does 4000+1000 score mean?
That problem (problem H) has two versions H1 and H2: an easier version and a harder version. Solving the easier version gives $$$4000$$$ points, solving the harder one gives $$$1000$$$ 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 $$$5000$$$ points, i.e. it is only slightly more difficult than the easier version.
Wow, split H?
Good luck
one refresh cost me 15 minutes
lol :)
Please let me reach Pupil today
Ohh I have made it! Lets goo! Next step Specialist!
DelayForces
Delayed agaaaaaaaaaaaain... Okay I'll have to go to sleep 15 min later...
Hope to become a pupil today
now its gonna be 1:30 AM for me when it ends :skull:
guessforces.
$$$1$$$. Guess the answer. $$$2$$$. Guess the answer $$$3$$$ Guess the construction.
There was no guessing involved wdym.
Just to be sure, do we need to use segment tree in D?
No, set plus some annoying math and casework is enough
please elaborate?
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.
What annoying math and what casework
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.
No XD
Nope, can be done with a regular set.
Oh, yeah, right, to maintain first and last positions of '1'?
Yes and a heap (priority queue) is even faster
Thanks, i actually wasn't sure which data structure could deal with this
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
Man what about Problem-D .....xD. Any approach?
Nice problem set.Enjoyed the problems!!!
Very nice contest! First time ever doing 5 questions in a div 2!
Sorry for weak tests on B :(
Hope everyone still enjoyed the round!
How to solve C? greedy only gives best possible x, but how to get exactly x?
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.
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).
Yes, it's tricky. But intuition is simple. Lets consider some worst case after shift (x = 3):
a = 1 2 3 | 5 6 7b = 7 8 9 | 4 5 6As we can see, if answer is exists and
ais sorted,bmust be also sorted.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.
Can someone please explain to me why this solution is not correct for problem D. My idea is if there is a prefix sum that is equal to the queried sum, then print yes, otherwise check if there exists an element with value one at which the prefix sum is greater than the queried sum, and if it exists the answer is yes, otherwise no.
Submission: 234308986
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
Thanks for the great round! Could someone please share the implementation/approach to D?
Store the positions of $$$1$$$ 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 $$$1$$$ from the array. From the first and last $$$1$$$ s, find which one is closer to the edge of the array and remove it along with any $$$2$$$ 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.
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
Nice problems. It would have been better if samples for C could cut wrong output format. I was printing b according to sorted a. I proved my solution but could not figure out anything for too much time.
Same man same! Wasted more than 30 minutes in it.
Very interesting H! I think I was pretty close to something like $$$\mathcal{O}(4^k)$$$ solution, but couldn't finish it
C>>>D
what was your approach for D
D>>C, C was too trivial kind off repeated idea
A. Note that if a[1]==1, we will always be able to do some operation if the permutation is not sorted (consider minimum i such that a[i]>a[i+1], because a[1]==1 we have i>1), and each operation will decrease the inversion number of it, so the answer is YES. Otherwise, since we cannot change a[1] by operations, the answer is NO.
B. Consider the beginning B's and ending A's of the string, they can't be moved. So we can ignore them and assume the string begin with 'A' and end with 'B', then the string will be like this: "ABBB | AB | ABBBB | ... | AB", and if we process "ABB...BBB" blocks from right to left (and move 'A' from left to right in each block), we can get ans=len(s)-1.
C. We can assume a[i] is sorted. When we need to choose x indexes such that a[i]>b[i], and choose n-x indexes such that a[i]<=b[i], we need to choose large a[i] and small b[i] for the first type, small a[i] and large b[i] for the second type. So we can assume that a[i]<=b[i] for 1<=i<=n-x, and a[i]>b[i] for n-x+1<=i<=n. Then we need choose x smallest values of b[i] to fill the range [n-x+1, n], and n-x largest values of b[i] to fill range [1, n-x]. To satisfy the inequalities as more as possible, these values also need to be sorted within two ranges. Finally we need to check if the answer we build is valid.
D. If we maintain the total sum T of the array, if s>T the answer is no. Let's assume that s<T for remaining part. Notice that if a[1]==1, all integers in [0, T] are valid, because there must be some i such that sum[1, i]=s or sum[1, i]=s+1, and for the second situation, we have that sum[2, i]=s. For the general cases, Let's assume there are k1 occurences of 2 before the first occurence of 1, and k2 occurences of 2 after the last occurence of 1. (So a[i] is something like " I1: 22222...2 | I2: 1.....1 | I3: 2...2222") Let r=T-2*(k1+k2) be the sum of I2, then similar with cases for a[1]=1, all integers in [0, r+2*max(k1,k2)] are valid (think about subarray I2+I3 or the inverse of I1+I2), and if s>r+2*max(k1,k2), I2 must be contained in the subarray we need (for any subarray doesn't contain I2, it will be contained in I1+I2 or I2+I3), Then we have (s-r) must be even. We can find k1 and k2 by maintaining a set of indexes such that a[i]==1.
E. For each i we let range T[i]=[i, a[i]], then the answer of a[i] will be (a[i]-i)%n — (the number of other ranges contained in T[i]), and we can calculate tha number of ranges by fenwick tree.
F. If sum of s[i] is odd or s[1]!=s[2*n] there's no solution. Otherwise, we can solve the problem in 3 operations. First, Let's ignore s[1], s[2*n] and look about s[2, 2*n-1]. For each even i in [2, 2*n-2], if s[i]==s[i+1], we put "()" on corresponding positions of b, Otherwise we put "((" or "))" instead (because sum of s[i] is even, there will be even occurences of such i, so we can choose "((" for first half and "))" for second half) Then we let b[1]='(', b[2*n]=')' and do the first operation. After that, for all even i in [2, 2*n-2], we have s[i]==s[i+1]. In the second operation, b[1] and b[2*n] are the same with first operation, and we put "()" for 00 and ")(" for 11 this time. Then for all 2<=i<=2*n-1, we have s[i]==0. If s[1]==0, we are done. Otherwise we need the third operation for b="(()()()...())".
Thanks :D
How can we calculate the number of ranges inside a range using fenwick tree?
https://codeforces.net/blog/entry/122539?#comment-1087689
In problem E, can you please elaborate on how to calculate the number of ranges contained inside T[i].
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.
Thanks
Thanks :) its really helpful
What is E idea?
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.
why completely isn't enough to be an intersecting
In problem D can I use segTree to solve it?
you don't need it
yep that's what I figured out, but I'm curious
You can.
Nice problems. Thanks for the round!
Nice Contest <3
I can't submit E now, so can someone confirm, is it just using ordered set for any index $$$i$$$, to find number of elements that will remain at the same time, when $$$i$$$ will be fixed. We will sort the ranges of {curr_idx, right_idx} by right_idx.
Yes, that's what I did at least
Oh no, I took much time to realize it (>...<)
You can use BIT instead of ordered_set also
Yeah, I would've gone for BIT if OS hadn't fit in TL.
in c, i was thinking about finding upper bound for the numbers in array a for the bi and swap it , and check whether we can get x combinations or not, can we solve it like that
Are rating changes from last Educational going to matter on the new rating calculation? I ask because the ratings were updated almost at the begining of the contest and codeforces bot is not taking care of that at least for me
Choked on G and lost 64 TONs.
Super cool contest, interesting ad-hoc problem F&G.
Super cool F indeed! Can you share your solution of G?
Divide $$$n^2$$$ numbers into $$$n$$$ groups.
Repeating Following Steps:
I did a spaghetti implementation, I get MLE and I can't replicate it with a non-adaptive grader :(
nice contest. can somebody ask my teacher not to take online classes during contest?:|
Yeah, Give me his contact details
What is solution for E?
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
problem F is very cool!
What's wrong in this submission of D- 234302167
Take a look at Ticket 17161 from CF Stress for a counter example.
Thanks ! It's my first time becoming a candidate master and geting tons!
Woah, it seems I massively overcomplicated my solution to E.
I take the permutation and make a $$$2n$$$-element array $$$p'$$$ which is just the permutation repeated twice with all the "arrows" from the first $$$n$$$ elements pointing right instead of left. Then I take that array as the leaves of a segment tree where each node is a sorted vector of its segment's elements. (So it's just like the tree you'd get from a merge sort). Then for each element of the permutation I can range-query in $$$O(\log^2 n)$$$ for the number of elements in the segment $$$[i, p'_i]$$$ that are greater than $$$p'_i$$$ using binsearch, which is exactly the time it will take for the $$$i$$$-th element to get to its place. This yields a $$$O(q \log^2 n)$$$ solution with $$$O(n \log n)$$$ memory, but with too big of a constant on the memory complexity. This got me a MLE.
So instead of holding the entire mergesort tree in memory I first make "phantom" queries into a segment tree and for every node remember which queries use it. Then the mergesort doesn't have to persist vectors at every level of the recursion, instead partially answering each query on the node it is in. Neither the time nor the memory complexity change, but with a better constant this got AC.
Also it's funny how I basically immediately got the idea for how to solve E while not being able to solve D at all. But it seems I'm the weird one and the order of the problems was chosen well :P
Ka-chow!
About problems:
I love H.
G is nice+. I don’t know if $$$2n^2-n+1$$$ wouldn’t be nicer, but I guess that’s what makes the problem hard, so I guess $$$2n^2-2n+1$$$ is a good decision.
The rest is good as there’s mostly nice thinking instead of coding, but no 0-coding. Maybe F is so-so, as it’s really a pattern made on paper, but it’s not that bad too.
Is E linear? Or is $$$n$$$ up to million because you were afraid of quadratic solutions? Anyway if high limits caused no problems (I got a bit scared, but time didn’t really grow during systests, so that’s nice) then everything is fine. It’s fine if the solution is linear too ofc.
Good problemset in general, definitely enjoyed!
Congrats on solving all the problems.
Congrats on #1!
I also enjoyed G and H, though G ended up being too hard for me. :)
Yes its because $$$O(n^2)$$$ ran super quickly so I had to make $$$n$$$ bigger. I doubt there are any linear solutions.
Seems like the test set is not strong enough for problem F. Some greedy solutions got accepted by doing something like this: let's make up another bracket sequence until there are no 1s left in the original string, and while composing the new sequence from left to right, we will try to eliminate another 1 if it is possible. Here is my implementation: 234305022.
There are also greedy solutions that do some sortings instead but I'm not sure. Maybe someone can share the details.
How could I get the prize? I won 2 TON according to the rules.
First time ever to solve a DIV2 problem C and became pupil after the contest. love this round:)
Link to my screencast and editorial of A, B, C, D, F.
A-F speedrun sub-1hr hitless
I solved problem 1896D - Единицы и двойки with
std::bitsetin time $$$O\left(\dfrac{n \times q}{64}\right)$$$ during the contest. My accepted submission works1248 ms.Here are some hints how to keep and update a set of prefix sums with
bitset:bitset[s]is equal to $$$1$$$, if there is a prefix sum with values, and0otherwise;scan be calculated with(bitset & (bitset << s)).count();deltacan be implemented withbitset = (bitset >> s[i] << (s[i] + delta)) | (pref << (size - s[i]) >> (size - s[i])).Remember, that
bitset >> K << Ksets to zero firstKelements without changing of other elements andbitset << K >> Ksets to zero lastKelements.Why is my same algorithm unaccepted (((
You forgot to enable highest level of optimization with Advanced Vector Extensions:
If you will do it, you will get accepted. Link to your accepted solution
In fact, C++20(64) is also necessary. thanks!
what s the name of this technique/algorithm ?
Why am I getting RTE on pretest 1 when it works on my IDE? Thanks!
234307252
Why I can't see the Editorial? When I click the "Editorial", it just tell me "You are not allowed to view the requested page".
maomao90
Hi can you try it again? I think it is fixed
ok
Can anyone of you help me find out why this submission for C is wrong. https://codeforces.net/contest/1896/submission/234350576.
Thanks in advance!!
dude i overthought A too hard...
I just made algorithms and algorithms for B until one worked. This one just kinda popped into my head when I was thinking of another idea...
I did B then couldn't think of a solution for A C or D...
Im_dik from Chongqing defeated the famous Legendary Grandmaster Um_nik in last Educational Codeforces Round.But we didn't see their duel again in yesterday's contest.It's so disappointing!
He is a tester. Do you think this is fun?
As a newbie really interested the round
Will I receive TON if I registered a wallet after the end of the contest? Also thanks for the round.
How do I get TON? I just created a wallet
Hi codeforces, how i can get my codetoins?
Have you gotten them? (I have the same question)
No(
Same situation.
An explanation of how my code for E in this round is similar to Akamu's code.
We did not communicate about E during the competition, but the code of question E is similar Akamu and I are friends, and three days before the competition, I wrote a problem with him when we learned the problem of statistics under the condition of two-dimensional partial order, which was basically the same as the solution of problem E.
https://www.luogu.com.cn/problem/P2163 Here is the title link for that question. https://www.luogu.com.cn/record/136243512 This is my submission record when I wrote this topic. In addition to clicking the link, you can also search for the submission record of dreamjoker2023 in Luogu and LuoguP2163 (you need to log in and pass this question to view the code by link). This submission was made on 2023-11-21. It can be proved that the code we used this time came from before the competition, and the code of LuoguP2163 is similar to the code of E. Since non-users of this site cannot directly view the code in the submission link, the administrator who needs to verify the authenticity of this record can send me a private message and I will provide my Luogu account number to prove that it is true.
It can be noted that the solutions and codes of the two problems are very similar, and the time we wrote the two problems is only three days apart. Since that problem is a model of this kind of problem, I have provided my code to him by LuoguP2163 on November 21 as a solution template for this type of problem. In this competition, Akamu and I both wanted to pass the E question by modifying the code we used before, so the code was similar.
I wonder if the $$$2n^2-2n+1$$$ bound of G is tight. If it is, can anyone please provide a mathematical proof?
I had no proof whatsoever for the bound of G, it was simply the best solution I could think of at the time :) I hope that other people could find out a nontrivial lower bound though!
Hello, Codeforces.
I managed to solve 4 problems in this round. However, after the end of the round, the Codeforces verification algorithms considered that my solution https://codeforces.net/contest/1896/submission/234264306 identical to the solution https://codeforces.net/contest/1896/submission/234269475 . Because of this, all my attempts were ignored and the rating was lowered. First of all, I do not know this person. Secondly, his decision is not identical to mine. Thirdly, task C is a fairly simple task, and in my opinion it would be wrong to consider a remotely similar solution to be identical.
Unfortunately, I have no video or other evidence that cheating did not happen. But I hope for an individual review of this comment and a change in the verdict on cheating.
Good luck to everyone!
next codeton when