Привет, Codeforces!
Мы с SomethingNew рады пригласить вас на CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!), который пройдёт в 18.09.2023 17:35 (Московское время). У вас будет 2 часа 15 минут на решение 8 задач. Раунд будет рейтинговым для всех.
Мы хотим выразить благодарность:
- 74TrAkToR за координацию раунда.
- isaf27, ugly2333, JianfengZhu, Little09, bashkort, Kieray, fishy15, Vladithur, Dart-Xeyter, pakhomovee, makrav, meowcneil, 127.0.0.1, Nanani, nnv-nick, SomethingDifferent, vl342, shiv_codegen, M1lkas, allmath, sdyakonov за тестирование раунда и полезный фидбэк.
- MikeMirzayanov за системы Codeforces и Polygon.
Разбалловка:
500 — 750 — 1500 — 1750 — 2750 — 3250 — 3250 — 4000
Мы надеемся, что наши задачи будут интересными для вас!
Разбор
Поздравляем победителей!
Информация от спонсора этого раунда:
Hello, Codeforces!
We, the TON Foundation team, are pleased to support CodeTON Round 6.
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 6 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 6 and hope you enjoy the contest!
я не понял, а где мемы в анонсе?
Их нет.
Why it's only 2 Hours for a CodeTON Round? I think we need more than that!
So many things to wonder nowadays... Ratings for many recent contests have not been updated yet :(
you are right.
Hope I can reach GM after this.
congratulations
Congratulations!
Congratulations!
As a tester, problems are really great! I hope you will enjoy the contest as much as I did.
Yeahh ! CodeTON finally ;D
As a 74TrAkToR's friend, I am sure the round under his coordination will be excellent!
Based on authors, I'm sure there will be no task with bitset lol.
SomethingNew round, are you retarded?????????????????????????????
No, no one is retarded, bro
A nice one
yea, too bad people did not get it
what if I don't want this to get normalized
You just should know that sometimes people can be frustrating.
Oh, I see.
But how did you get that joke but not this oneThen you can honestly forgive some greens who have complete no idea what they're saying.
At least there will be no goddamn bitsets in it
Do you want legends in the statements?
Yes.
doesn't matter
No.
legends in the author's statements, why????????????????????????????????????????
As a tester I recommend you to participate and I hope you will get positive delta!
Wish it will be an great contest.
as a participant, the 2 hours time combined with that score distribution is scary ._.
wishing for a charming contest
wishing for a charming contest
Finally, great contest (I hope so)
Why is the round on a weekday? I won't be able to participate as I have band practice. It's just even more weird given that it is sponsored
Omg Senpai, so true ≧◡≦
I got you! If you are really Ryo and Kita, today is Respect for the Aged Day!
As a one gray tester, give me contribution :)
74TrAkToR Round? I'll skip this one.
F is so 74TrAkToR style lmao
So rude.
Where is my money? I still haven't received my prize from last round. I had to go through the misery of creating a wallet and storing keys.
Where is my money? I still haven't received my prize from last round. I had to go through the misery of creating a wallet and storing keys.
woww :o
Hope it's the round that I become expert!
I love your avatar, good luck
thx, good luck too.
I am definitely going to have negative points. If the time remains 2hr :(
It's gonna be my first contest. I should've started with a div 3 or 4 but I like to challenge myself. Wish me luck
I wish you the best
Why there's no 1,024-2047 places: 1 TON each?
Good Luck!
Abcd speedrun
I'm nervous about participating after three months of not participating in this competition.
You have nothing to lose. Either remain newbie, or reach pupil.
Hope I can learn something new from this round, good luck everyone!
TON's price seems to fluctuate a lot.
Easy problems = panic sell, hard problems = ???
Well prepared round. My congratulations to the authors and testers. Definitely one of the best ones I've given these few months.
The contest was mexed up
Please announce last-minute round duration changes more prominently. I participated this round thinking it was 2 hours, and I couldn't compete for more than 2 hours today. I believe this situation might not be unique to me.
Can someone explain why my code isn't TLE for 1870D - Prefix Purchase?
It passed system testing too, but how???
At each step in the while-loop, you are finding the rightmost $$$x$$$ such that $$$\lfloor k/(a[l]-a[x]) \rfloor$$$ is maximal.
If the value of $$$\lfloor k/(a[l] - a[x])\rfloor$$$ is $$$0$$$, then $$$x=n$$$, and the loop will break.
Otherwise, assume this value $$$\lfloor k/(a[l] - a[x])\rfloor$$$ is non-zero.
Then write $$$k = (a[l] - a[x])q + r$$$, where $$$0\le r< (a[l] - a[x])$$$ and $$$q\ge 1$$$.
Now we have the following inequality:
$$$r< (a[l] - a[x])q\Rightarrow 2r< (a[l] - a[x])q+r=k\Rightarrow r<\frac{k}{2}$$$
So every time you assign $$$k:=k\%(a[l]-a[x])$$$, the value of $$$k$$$ becomes less than half of what it was.
In other words, your algorithm is at worst $$$O(n\log{k})$$$.
Thx!!!
np
me spending 10 minutes trying to understand what problem C was trying to say
A grandmaster (at least for now) here. It also takes me some time (~3min) to finally understand it. I initially thought "rectangle in the array $$$b$$$ containing all cells of this color" means "a rectangle which contains only this color". Then the word "smallest" (instead of "largest", which would make it an interesting problem) confused me.
Yup understood the same and thought wouldn't it make this a trivial solution for each k it would be square of length 1 if it exists in array but then figured out later that it meant that the smallest rectangle that would cover all the points with same value
Thanks for the fun contest!
How to solve E?
SomethingNew alreadly spoiled it a while ago. It's just bitsets :)
UPD. Sorry. I just replaced bitset operations with ordinary cycles with boolean operations, it became two times slower, but still got OK. I guess the solution does benefit from the usage of bitsets, but not drastically.
So I was wrong during the contest thinking that SomethingNew changed his mind about having bitsets in the jury's solution.
How to solve D?
First, we can say, that picking mininal $$$c_i$$$ determines the first element. Amongst all minimal $$$c_i$$$ we only care about one that has max $$$i$$$, so let's create a new array $$$a$$$, where $$$c_i$$$ will be stored in increasing order (we also remember their indices). Then we pick $$$a_0$$$ $$$k / a_0$$$ times. Let's subtract $$$a_0$$$ from $$$a_1$$$. Then, if we decide to pick $$$a_1$$$, that means that we cancel choice of $$$a_0$$$ and replace it with $$$a_1$$$. That's the key idea. When we pick $$$a_i$$$, we need to be able to add number on a segment. It can be done offline using difference arrays.
Suppose the minimum value in array $$$c$$$ is $$$c_i$$$, with ties broken by the largest index. Then the first value can be incremented at most $$$\left\lfloor \frac{k}{c_i} \right\rfloor$$$ times. In fact, if we keep selecting index $$$i$$$, then all values from index 0 to index $$$i$$$ will be equal to $$$\left\lfloor \frac{k}{c_i} \right\rfloor$$$, and it is impossible to increase them further. Note that there may be some surplus $$$k \% c_i$$$ coins left unused.
However, can we increase some of the later values (which would otherwise remain all 0s in this option)? This requires that we can afford to replace one of the index $$$i$$$ selections with a selection for a later index. Suppose the minimum value from $$$c[i + 1\ldots n - 1]$$$ is $$$c_j$$$, i.e., smallest element located after $$$c_i$$$. Each replacement requires us to spend an additional $$$(c_j - c_i)$$$. Based on our surplus remaining coins, we can then calculate how many of the index $$$i$$$ selections can be replaced with index $$$j$$$ selections, and update our strategy accordingly.
But what about the values after index $$$j$$$? Once again, we can consider whether we can replace an earlier selection for a later selection. Our earlier selections would be a mix of $$$i$$$ selections and $$$j$$$ selections, but replacing a $$$j$$$ selection will save more money than replacing an $$$i$$$ selection, so we can simply focus on replacing $$$j$$$ selections now. And so on.
How do we actually implement this? My approach was to first construct a cumulative suffix minimum array, where $$$snm[i] = \min_{i \leq k \leq n - 1}c_k$$$. These are the only values worth considering. For simplicity, I assumed that our initial strategy is to to select cost 0 with frequency $$$k + 1$$$ (effectively $$$\infty$$$). Then we iterate from index 0 to $$$n - 1$$$, each time keeping track of the surplus so far (initially $$$k$$$). For each index, the cumulative suffix minimum array tells us the new cost to consider. We can subtract this new cost minus latest considered cost to determine the cost of replacement, and count how many replacements would be afforded by the surplus, i.e., $$$\left\lfloor \frac{surplus}{newcost - oldcost} \right\rfloor$$$, updating and printing the count accordingly, and also updating our latest cost and surplus as well.
My submission: 223893795
https://codeforces.net/contest/1870/my
my approch is also similar but it doesnot work
One error in your implementation is that you allow the number of replacements to exceed the number of selections from the previous cost, even though you can only replace existing selections. Specifically, the output should be non-increasing, but your code allows it to increase.
Here is a countertest:
The output should be
1 1(simply pay for the second index), but your code produces1 4, because the surplus of 9 can be replaced four times by an increment of 2, but you don't actually have four selections to replace (you only have one).Thanks a lot ! Friend .Urs debug made me to get it accepted. https://codeforces.net/contest/1870/submission/223982510 (Accepted) The another silly error was of indexing (for(int j=0;i<cool[i].size();j++) if(m.find(cool[i][j])!=m.end()) m.erase(cool[i][j]);) giving wrong anwer on test 10 was i<cool[i].size(). wish you grand success.
What is pretest 3 on problem D? T_T How do we solve D?
Here's your counter-test:
Your solution gives
2 2 1 1although it is possible to make2 2 2 0(my solution breaks on that test too btw, but I have no idea how to fix those cases)Thank you so much!
Huge dislike on this contest. Spent half of contest time trying to eliminate TL on correct linear solution for C and correct NlogN solution for D on Kotlin. C successfully, D unsuccessfully. Shame on you.
Hopefully no FST today...
Nvm
I could only think of a bruteforce solution to D.
After ~1.5 hours of thinking I still don't get, how can you optimise $$$O(n^3)$$$ into $$$O(n^2)$$$. Can someone give a hint pls?
same boat :( no idea
Could it be...
bitsets bitsets bitsetsnah, probably not (unless SomethingNew got us normalized for good)
No, YocyCraft posted unofficial editorial, that's like dp with some additional array and I don't get why it works in $$$O(n^2)$$$ but it does
Yeah, but how about this one: 223919247. Coincidence? I don't think so
Can we solve E with tries or is it some dp or something else that my small brain couldn't think of?
I may have not solved D, but at least I have passed first 4 pretests.
Also this problem is somewhat similar to this problem, we can find largest index with min cost and estimate max amount of possible operations.
Actual solution is probably something like this: keep a vector of candidates with costs higher than min, for each new candidate pop every candidate that is worse, this would work in $$$O(n)$$$ because each element would be added and removed from the vector at most once, then to calculate the final answer use a difference array (I cba implementing this rn).
Good problemset
I can only think of a crazily long segment tree solution for D,which I have not enough time doing it, and for that I think there has to be some easy-to-write way.
If you came up with idea to add a number on a segment, you can do it offline using difference arrays. Suppose you want to add number $$$x$$$ on a segment $$$[l, r]$$$. To do that, you can create array $$$d$$$ and say $$$d[l] += x, d[r + 1] -= x$$$. If you count prefix sum array on $$$d$$$, you'll get that the segment was increased by $$$x$$$
I planned to use Segment Tree finding the cheapest price with the biggest index during the process of getting better result.Is this unnecessary?
I did this problem without segment tree. It can be used to do addition on segment, but other than that I didn't think about using it
thx. I think I made some mistake with the strategy to ever think of segment tree stuff.
Can't you just sort them or use a priority queue?
Did anyone else think that for C with min(Aj, Ai) they meant min(Aj, Aj+1, Aj+2 ... Ai)? That cost me 30 minutes and a headache...
A: The maximum possible mex is min(n, x+1), so we need k<=min(n, x+1). Then when k==x we can let a={0, 1, 2, ..., k-1, k-1, ..., k-1}, when k!=x we can let a={0, 1, 2, ..., k-1, x, x, ..., x}.
B: Let bi=(1<<t). If n is even, then the operation will make the t-th bit of x become 0, and if n is odd, it becomes 1. So if n is even, all operations will make x smaller, and if n is odd, all operations will make x greater. Therefore, we can use every operations or no operation to get the maximum and minimum values of x.
C: If t doesn't occur in a[i], the answer of t is 0. Otherwise, for any i,j with a[i]==t, a[j]>=t, we have b[i, j]==b[j, i]==t, so the rectangle need to contain (i, j) and (j, i), then it contains [j, j]. Therefore, If we denote S={i: a[i]>=t}, the answer of t is 2*(max(S)-min(S)).
D: First assume the i0-th operation has the minimum cost, then we need to perfrom at least floor(k/cost[i0]) operations in total. So we can assume that we perform that many i0-th operations, and we can change them into i-th operation later for i>i0 (which costs cost[i]-cost[i0] coins). Then assume cost[i1]=min(cost[j]:j>i0), then we can change as many as possible i0-th operations into i1-th operation to improve the answer. We repeat this process until there are no better operations or we spent all coins.
E: Let time[t] = the minimum i such that we can get answer t in subarray a[1, i]. For each i, we need to update for every t such that time[t]=i. The naive approach is: for every i<j<=k, we let time[t^mex(a[j, k])] <-min- k. But this approach will be O(n^3). To optimize this solution, during the dp process, we need to keep ptr[m]= the minimum k such that there exist some j, i<j<=k and mex(a[j, k])==m (we can do this by pre-calculating mex[j, k] for all 1<=j<=k<=n). The the dp formula will be time[t^r] <-min- ptr[r].
F: Let balance(t) = the change of the rank of t after sorting. Then we can see for t with same number of digits, balance(t) is monotonic. Therefore we can get the answer by binary search, the time complexity is O((log(n))^3).
Love your short and clear explanations.
Why does your solution in E work fast? From the first glance it's not obvious why can't you take all current xors for every i and try to update them with all mexes
Nvm, I saw the editorial
Well, YocyCraft's solution is different to the model one. It works fast because for every t everything is recalculated only once (when time[t] == i)
f5 f5 f5 f5 f5
Oof. Your solution is same as mine but with the difference that when i < 1000 I simply iterate through an array. That makes it sqrt(NlogN) instead of sqrt(N)logN (that parameter should be sqrt(NlogN), since in O(sqrt(N/logN)) steps it'll reach that it works in that complexity).
How do we solve D ? Only thing I could observe is just take the righmost c[i] , which gives the minimum quotient when K is divided by c[i] and then K-c[i] and repeat the step.
I was not able to solve D as well, But there is one approach I was working upon that is based upon the fact, that we have to do operations at atmost 2 indexes, one with the smallest cost and the other one at appropriate largest index possible.
I (might) solved F but I started the contest late and I couldn't finish my code in time. I needed 30 seconds :(
skill issue
True xD
Very similar to problem H
And the solution for H is mentioned in its official editorial.
H is almost the same as the problem I made before. https://www.luogu.com.cn/problem/P8950
Lucky, only a few people had accepted it before this contest.
too lazy to code problem E lol
I am proud to be the absolute loser of this competition
my problem, problem H — XXI Open Cup. Grand Prix of Korea , is today's problem G without updates.
By the way, just using binary search + saegment tree to find threshold and calculate block repeatedly guarantees time complexity which is better than $$$O(Q \sqrt N \log N)$$$? It seems to pass pretests.
As I mentioned above you can do it in 2 parts:
when the position is > sqrt(NlogN) use the segment tree
when the position is <= sqrt(NlogN) simply use an array an iterate through it.
that results in O(Qsqrt(N)*logN).
The editorial claims that simply using an iterative segment tree gets rid of the log completely but it doesn't have a proof atm.
https://codeforces.net/contest/1870/submission/223916377
Why my code on D gives wa on test 4
What's the problem in my approach 223919097 for problem D? I found all good indices list by this method. 1. Initially,
l=0,r=n-1, find minimumciin this range, and add thatito good list, and makel = i+1. 2. repeat ifl<=rNow maximum value
(mxx)we can get in result arrayais =>k/c[good[0]]. So I iterate from right to left(j)(why ? we need lexicographically largest array a) in good list, now lets say I can dopoperations (+1s) ongood[j]index. then I need to ensure thatp <= k/c[good[j]]and(k - p * v[j]) >= (mxx-p)*c[good[0]].what if there are more than one js that will be in the final answer?
I am taking all such valid js, I decrease k by p*v[j] and mxx by p
I'm confused about the item
k - p*v[j]. It seems that themxxfor ·good[0]· is changeable, but thepfor each ·good[j]· is unchangeable？if I use
poperations on indexjthen, I have to decreasek (total coins)by coins used onj:(p*c[j]). and aboutp, I am just trying to find best validpforjs.ヾ(￣□￣)ﾂMEXforces
Isn't the $$$O(\log^3 n)$$$ solution of F supposed to get TLE verdict?
Turns out many got accepted with that while I'm struggling to squeeze my code into the time limit. :(
What's the O(log(n)^2) solution?
bitset passed in problem E, ___ ___ ________?
I tried to solve E by precalculating mex of all subarrays and then using dp to find the best subset of subarrays but getting Wrong answer on test 11 , can someone help ?
223917560
why my code gives wa on test 4
PROBLEM D
https://codeforces.net/contest/1870/submission/223922693
Input:
Answer:
10 4 4 4 1 0Your output:
10 4 4 4 0 0Hope it helps!
Thank You , I realized i couldnt chooose just two positions so I did a rolling ball kind of thing and got AC
Finished the first 4 problems in 34 mins, but stuck at E for the rest of the contest :(
I tried to do something with the highest bit of the answer, but it didn't work.
I even considered using bitsets to accelerate the DP, but I didn't know how to do "swap every $$$b[i]$$$ with $$$b[i \oplus c]$$$ in a bitset" in $$$O(\text{fast enough})$$$.
I approached the problem with bitsets and had a similar problem. Actually, I optimized my solution enough that it even works without fast bitset operations (223899736 with bitsets worked in 218 ms; 223934854 without bitsets [actually, with bitsets, but treated as ordinary boolean arrays] worked in 436 ms). However, here you are,
xor_convolveis what you need. Asymptotics is $$$\frac{n \log n}{w}$$$ (assuming that $$$w$$$ is the length of RAM word).Any hints for D Please.
I spent all my time considering that optimal answer will be only from a pair of elements, but my assumption is wrong.
pick the minValue coin as much as you can.
Can you transform the rest of the array such that divide and conquer can be applied?(problem reduced to same problem with smaller contraints this time)
Subtract the minValue from the rest of the elements and ditch the elements starting from position 1 to the last occurance of minValue, Now you're left with the original problem where k = remainder that was left after the spoiler 1 and array is the new array left after performing the subtract and trim operation.
Video Editorial For problems A,B,C,D.[Aadhi Hindi + Half Inglish]
I will cross 1400 this round. Next target 1600.
this didn’t last very well
Turns out it did :)
congrats! I got specialist too, but idk why i think the ratings are being reevaluated
Yeah, yesterday night they rolled back ratings from the beginning of August and reevaluated them. P.S. — you will get cyan today :)
yay :)
This didn't last very well
Anyone knows why in the problem E, solution $$$O(n \cdot t)$$$ where $$$t$$$ stands for the number of segments $$$[l, r]$$$ so that $$$mex[l][r]$$$ is equal to neither $$$mex[l + 1][r]$$$ nor $$$mex[l][r - 1]$$$ passes all the tests? In other words how to bound $$$t$$$ to less than $$$O(n^2)$$$?
Fun fact: Problem E from today is very different but has the same idea as this F2 from old div2 in which 74TrAkToR was the problemsetter and he is the coordinator from todays round
This generator kills not small number of E.
Kill for TLE or WA?
TL / ML. Mainly dp[position] = {the set of possible XOR} with $$$O(n^3)$$$ transition is the target.
I attempted to hack 8 and succeded in 1 of my friends. Big ratio indeed
I only shrinked $$$r$$$ of all segment instead of both of $$$l,r$$$. It got uphacked.
Good contest, enjoy it very much. E is brillant(it takes me the longest time to come up with the solution). F is interesting. However I found G much easier(n logn sqrtn with small constant, not standard solution, which got accepted soon after system test) but I was too sleepy to impletement it correctly in the last 15 minutes and successfully missed my LGM.
And then my E got uphacked :) So i should feel lucky instead of regret now!
Finally purple.
MEXforces
Hello, can the question setter or tester provide an incorrect example?223967713
Hello, can the question setter or tester provide an incorrect example?223972005
Input:
Answer:
10 4 4 4 1 0Your output:
10 2 2 2 2 2Hope it helps!
Thank you. Your example really helped me
Is it too late to create a TON wallet in order to get my TON now?
Hi. Did you receive your tons?
No...
its been ages since the last time problem ratings were updated. :feelsoldman:
Thanks for the round.
The problems were interesting and nice, but the TLs were too tight, so the pleasure of solving the problems was more or less neglected.
Please rethink the culture of selecting TLs.
Hi. How can I get a prize?
Hello everybody! What should I do if my attempts are ignored because my code is too similar to someone else's? I received a message from System that my code for task C is very similar to the NoiceFi code, although I wrote it myself. Looking at the NoiceFi code, I noticed that it really is very similar to mine, but I have no idea how it happened. (223885953 and 223878962)
So, when are we getting paid?
My prize didn't come did I make a mistake at my wallet code ?
have not came yet?
unfortunately, yours
So you received your prize ? TONS didn't arrive for me too..
Did anyone get the prize?
Funny fact, CodeTon 7 Finished and we are still waiting for the prizes of the 6
I dont think funny is the best word for that :)
prizes **
Fixed
TON round 7 finished. Yet, round 6 TONS not added..
Any update?
Nah, haven't been added to the wallet yet..
Okay, thanks for it.