Hello Codeforcers!
We are pleased to invite you to participate in CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!). This round will start on Mar/30/2024 17:35 (Moscow time) and will be rated for all participants. There will be $$$8$$$ problems to be solved in $$$3$$$ hours, with one divided into two subtasks. Similar to USACO, you will help Farmer John and his cows resolve a series of first world problems. Be there or be square.
This round was cooked up by smax, sum, oursaco, cry, and buffering.
We would like to thank the following people for making the round possible:
Our favorite cherry TheScrasse for the wonderful and speedy coordination.
Our MVP testers, Benq, Geothermal, and rainboy, for dedicating so much time to reviewing problems, providing essential feedback, and perfecting the problemset.
The rest of our testers for their unparalleled efforts: errorgorn, rqi, hyforces, LipArcanjo, MridulAhi, omeganot, darkkcyan, Phi-001, awesomeguy856, JagguBandar, camc, drdilyor, lethan3, rohit2593, willy108, WAtoAC2001, jay_jayjay, -1e11, evenvalue, lunchbox, kaztayev, kondasujay2, maxrgby, htetgm, thehunterjames, GlassesNerd, SunShine11, wozhenshuai, chromate00, I_FloPPed21, MrPavlito, priyanshu.p, ETL, yash_9a3b, Aurora__, nelsi_sousa, susvant, and myvaluska.
Alexdat2000 for translating the statements to Russian.
MikeMirzayanov for developing Codeforces and Polygon, or else this contest literally wouldn't exist.
You, for participating!
Score Distribution:
$$$500 - 1000 - (1250 + 750) - 2250 - 2500 - 3000 - 3000 - 4500$$$
Editorial
Congratulations to our Winners and First Solves!
Top 5:
First Solves:
A. A_G
B. jiangly
C1. ksun48
C2. turmax
D. Omer223
E. tourist
F. Radewoosh
G. tourist
H. ecnerwala
And here is the information from our title sponsor:
Hello, Codeforces!
We, the TON Foundation team, are pleased to support CodeTON Round 8.
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 8 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 8 and hope you enjoy the contest!
Another Amazing CodeTON Let's Go !
As a tester I really enjoyed the round and I highly recommend everyone to participate in it!
WAtoAC2001 orz
WAtoAC2001 orz
WAtoAC2001 orz
As a tester, this round will happen at a really funny time!
willy108 orz
i wonder why teamscode had to delay their contest
awesomeguy856 orz
As a tester I really liked the problems, I recommend you to participate!
As a participant, i hope everyone will get positive abs(Good bye 2023's) delta.
priyanshu.p orz
What can 1 TON buy me ?
whatever 5$ can buy you.
Doge council decided that problems are great and you should participate
drdilyor orz
where is smiesmie :/
I joined！！！
and the bred doge luck's funny
As a tester, I'm sad I couldn't participate.
MridulAhi orz
MridulAhi orz
ORZ
OMG! rainboy is tester!
As a tester, I can say that this round is GOATed!
rohit2593 orz
rohit2593 Orz!
As a monkey tester, the cows are friendly :)
JagguBandar orz
As a tester, smax orz
smax orz
fr, smax orz
smax orz
smax orz
smax orz
as a tester with photo of Stewie Griffin i say .........................................................................Brian Griffin
I_FloPPed21 orz
smax orz
As a tester, I enjoyed helping Farmer John with his never-ending problems.
wozhenshuai orz
As a tester, I can confirm the epicness of this contest.
As a tester, I have to say, excellent round, I hope everyone enjoys it thoroughly.
Having such intelligent individuals commenting on the problems is very encouraging, yet depressing at the same time.
Have a nice contest!
nelsi_sousa orz
orz myvaluska the pupil tester
orz myvaluska the pupil tester
As a non-tester, I want to say that I hope the round will be cool
Best div ever
Is the score distribution right (1250-750) or it should be (1250-1750).
C is broken up into two subtasks, the easy version worth $$$1250$$$ points and the harder version worth an additional $$$750$$$ points.
1800 plz!
Heh, just realized it would be ~4.5 years since my last rated contest, and I'm now kinda willing to take part in a rated one for old time's sake.
Hope that I would not get a -ve delta T.T
UPD: I screwed myself up badly T.T Still the problems were great anyway!
good luck!
I too am broken
Oops I failed :( well for the good part I still did A to C2 flawlessly (at least pretest said so)
I wish codeforces had the same high quality UI design like ton.org does.
Good luck to everyone!
First time participating in a CodeTON, what is the difficulty of the problems in USACO terms?
Thank you in advance)
Problems of CodeTON round has always been very unique and enjoyable.
Hope for a enjoyable round.
Excited for this one, let's goo
value of TON tripled since the last CodeTON round, it's $5/TON now
so the first place winner will receive a prize of $5,000. wow
I'm so excited for this contest
Looks like Codeforces has some serious issues with Leetcode.
I believe that listening to the best video game official soundtrack may help your performance during this round.
which one?
I personally listen sawano hiroyuki every contest. GOAT compositor.
i want to work at TON. plz give me job. I know Tag language, a little. I identify myself as a lgm as well
Thank you all for this wonderful round. I am very excited!
I'm glad that the prize isn't NOT coin :D
mike was too lazy fixing the problem ratings so he thought why not remove rainboy completely from the contest
WOW! Benq Geothermal and rainboy! This test will be wonderful!
What does (1250+750) represents in terms of points, like do we need to solve both the problems to get the points, if not why the D problem is of 750 pints ?
I believe that problem will have easy and hard version
Problem C has two versions — C1 (easy) and C2 (hard).
Solving C1 gives 1250 points, solving C2 gives 750.
The solution to C2 (most likely) is also a correct solution to C1. Thus, effectively, C1 is worth 1250 and C2 is worth 1250 + 750 = 2000 points.
Thanks for the reply, if i only solve c1, do i get the 1250 ?
Yes
Or more specifically, similar to other problems, you won't get the full 1250 points — you'll get closer to the 1250 the sooner you solve the problem. Solving it at the very beginning of the contest would give the full 1250, but for example solving it now (at 2 hours 42 minutes into the contest), you'd only get 710 points.
Thanks a alot for the clarification.
Another 1024 TON to tourist.
that's 5000 USD
Not this time
Can newbies or beginners register??? And solve problem will there degradation in rating if my problem goes wrong???
anyone can participate, regardless of your rating!
i hope i can get 2 ton!
good luck everyone :>
As a tester, I almost forgot to make "as a tester" comment.
Anyway, the problems are great! Huge orz to the setters and I recommend everyone to participate in this round.
left after seeing polygons...
i did the same lol.
skill issue
very tough contest ;(
INTERESTING_FORCES unfortunately got so many penalties in C2
Very good and interesting problemset.
this contes could be better
Problem D: Learning to Paint is a straight-forward application of the famous interview problem.
I have added hints and thought process for this problem on CF Step.
254174144
Problem D. Can someone explain, why random gives TL?
apparently multiset always TLEs and the authors wanted priority queue solution. T_T made same mistake during contest.
No, the intended solution with set instead of priority_queue passes in 0.5 s.
The question is how to make a bad test for my random solution, because it passes random tests locally in $$$\le$$$ 1 s.
Ohhh noooo T_T tourist.
the problem f is broken
Can anyone please explain solution to probelm-C2
is C2 constructive, casework problem?
calculate the distance, first select power of 2 to get extra, second select even until 2, then add rest? idk
you are in right direction
Actually I think it's optimal to first select the intervals with odd length...
yeah, and priorize them by the smallest to largest.
need hints for c1 :/
chosen vertices will also form a polygon
make a closed loop and observe how can you make triangles in it
Number of triangles equals (number of chosen dots) + (number of unchosen dots that located between them) — 2.
A question about task E: "It may be the case that the game will continue indefinitely" as far as I'm concerned, that's not true, right? I couldn't find any example configuration where the game continued indefinitely
You're correct, that never happens.
I guess the problemsetters didn't want to spoil anything, as the fact that every game terminates doesn't trivially follow from the way the game is described (before you think about strategy).
Good to know that, thanks
that sentence was added an hour before the round LOL
As a music gamer, I got defeated by the tiebreaker (looking forward to the solution). Anyway thanks for the cool round!
The song is mega but the problem is well-known in China(it was set 8 years ago in UOJ) and many Chinese just copy the code of that problem...
OMG, ΩΩPARTS was actually buried under there...
why did I notice E so late? T_T, idk how to solve D without segtree or efficiently with segtree
Can anyone tell why my code is giving wrong answer for question c2? https://mirror.codeforces.com/contest/1942/submission/254186598
UPD: Nvm, system tests are over
Problem C has definitely ruined all this competition.
it was an interesting problem, but a lot of casework in c2.I could not solve.
C ain't that bad, for both versions. Good observations would result in better execution.
i did bad, very bad. c1 defeated me. i don't know why i did not notice that the inner polygon is also created for 2 hours.
well that was a waste of a morning, lol
In D problem1
1- if i do dp to get maximum sum(mx_sum) and hm ways i can get this sum (freq)
2- k-=freq
3- then dose 1 again but i wanna second max so i use the mx_sum from last dp.
is this solution will pass?
A frustrating contest indeed !!
Are some of my observations for E incorrect?
The only thing which actually matters is the min gap between some $$$a_i$$$ and $$$b_i$$$, i.e, $$$min(b_i - a_i)$$$.
Any move always preserves the parity of this, meaning P1 will always win for an odd value and lose for an even value.
The gap between $$$b_{i - 1}$$$ and $$$a_i$$$ doesn't matter since A's movement left / B's movement right is bounded while the other's is unbounded (subject to the loss by parity above).
So for each odd gap upto $$$L$$$, we can count the number of ways of the min gap between an $$$a_i$$$ and $$$b_i$$$ being exactly that, the answer should be the sum of those values.
We can get the ways of assigning gaps so min gap between $$$a_i$$$ and $$$b_i$$$ is $$$\geq x$$$ and rest are $$$\geq 0$$$ using bars and stars, so we take (ways of $$$min\ gap \geq x$$$) — (ways of $$$min\ gap \geq x + 1$$$).
This doesn't work for the large sample, any guesses on what I might be missing? (or is it just an implementation skill issue?)
I don't think that only the min gap between some $$$a_i$$$ and $$$b_i$$$ matters. If you consider the array of non-zero $$$a_i - b_i$$$, $$$\Delta$$$, then $$$\Delta = {2, 4}$$$ is a loss for the first player but $$$\Delta = {2, 3}$$$ is a win. The minimum value is the same, but the result differs.
Edit: I'm a dumbass, I misread the problem and though the farmer had to move ALL of their cows left / right in a given move...
Holy cow, I also misread the problem and "solved" it in the exact same way you did lol
I think proving it as a win by showing the interaction is hard since there are so many states. This kind of explains the solution so I'll put it in a spoiler:
The idea of the problem is that you have $$$\Delta = {b_i - a_i}$$$ and in every move, you can reduce any number of entries in this array by 1. The losing player can waste time by doing some op to add 1 to an entry, but eventually this becomes impossible so only the reduction matters. In case of $$$\Delta = 2, 3$$$, an interaction could be:
2, 3
2, 2
1, 2
0, 2
0, 1
0, 0
Basically the winning player will always make every number even, and the losing player is forced to make at least one odd. The base case is $$$\Delta = 1, 1, \cdots$$$, which is a win for the first player.
The only thing that matters is that the gap between some $$$a_i$$$ and $$$b_i$$$ should be odd.
Any reason for such tight constraints in D, isn't brute force O(n^2klogk)
There exists a more efficient solution, IG. $$$O(n^2*log(k)))$$$
Yes i know that, my solution was nk logn as well but got tle in implementation, now that i think about probably my fault for using segtree, should have used set instead
I take my words back still giving tle with a set, was able to pass it by making an array of reverse iterators, not a fan of the constraints
Not gonna give any div1+div2 round onwards. Only div2 seems to be the way.
Great contest. Loved the problems! 💯
Fixed my bug on problem D only to see the "contest over" message flash right before I could submit. 🤧
Well, that's also a fun experience once in a while. The mistakes stick harder! 😂
Expert, here I come! 🤓
not able to solve prob D since last 3 rounds. Disappointment as always
Us bro, us! I even dropped C2 in hopes of D 🤡
Can anyone help me with this? Why is this wrong? https://mirror.codeforces.com/contest/1942/submission/254188720
Could you please pose H in a data structure training contest... (or at least have a subtask?) From $$$O(NQ)$$$ to $$$\widetilde{O}(N+Q)$$$ is apparent (if you have prepared) and boring.
imo it is impossible to solve this without a dynamic dp template and there are too many details in implementing. feels like this round does not have a real extremely hard problem.
Solved Problem C1
8 wrong submission
.
FST on B here too, and C1 took too long for me.. and could not crack C2 :(
Is there any $$$O(nk)$$$ solution for D?
Authors seem to hint that there exists one of a similar order, $$$O(n^2 + k)$$$
E
I misread it as selecting the kth cow and moving it (which is also a common situation, I think), and wasted an infinite amount of time. It would have been better if you had written it like a subset.
Can someone please explain how my $$$O(n^2log(k)log(nA))$$$ solution passes in D?
Submission
$$$n\leq10^3, k\leq5\cdot10^3$$$ and time limit is 4.5 seconds..
Yeah but surely it would take more than 1 second right?
Thanks for the contest, I liked ABCEF, all are high-quality interesting problems. But I dont understand why problems like D still being accepted for Div1s in 2024, isn't it just very standard problem?
I definitely think there's a place for problems like D in Div1s. Even though you can say there is a standard "merge sorted lists using a priority queue" idea, it took me some time to reduce the problem to that (and I enjoyed it).
💀
just realize number of participant too low compare to regular round, why is this the case?
Little bit sad for my unclear submissions for C, basically it's an easy observe problem with short code...
Thanks for the contest!
For problem E, the case of $$$n = 1$$$ previously appeared in AGC 020 A which I wrote — not a big deal of course, but it helped me to come up with the solution a little bit faster.
Hello folks,
Do you know that JavaScript V8 4.8.0 was released in 2015? And included in node since 2016. That's over 8 years ago. Unlike most programming languages, JavaScript has evolved significantly since then. Latest available V8 version is 12.5.0 (Mar 18, 2024).
I'm well aware that JS is not usually used for competitive programming. But using obsolete language version is a guarantee that it will stay this way.
Cool round, had fun. Congrats to the setters
Read E for the first time and solved it in 20 mins, bruhhhhhhhhh
Cool round , although it was strange to have a C like this
Anyway , does anybody has 7 rating points to donate to me :(
It seems that G is a little too easy for the position? I personally consider F more difficult than G.
Why has TON skyrocketed so dramatically?
Following the whole crypto market ig
Can anyone help me with Golang
https://mirror.codeforces.com/contest/1942/submission/254314439
For this problem, in test 6 with n=200000, TIME_LIMIT_EXCEEDED even if I only debug and read & print the input
MathForces
I think there are too many math-like problems.
But it cannot be denied that the competition was indeed quite good.
How to exchange TON into dollars?thanks!
Hi guys, I am new to codeforces so I want to ask something from you guys. I am very polite about this. In this CodeTON contest I solved Accepted 2 Questions and two were Runtime error. But My Rating Change is 0. Not even Positive or negative. Can you tell me why this hapenned? I also got a positive score of 1512 but my rating change is 0. Please help me figure about that.
Ummm, So how can I recieve the TON? I only realised that I can put a wallet in setting after the contest :))
Same question :))
+1
+
For previous rounds I got a system message asking to put my wallet details in my profile (https://mirror.codeforces.com/settings/wallets). This message was quite a while after the contest (eg January this year for round 7 which was in Nov) with a deadline for adding the details at the end of January (and the ton was added too my wallet in March).
i got a message from system saying that my solution coincides with some other solution for C2 1942C2 - Bessie's Birthday Cake (Hard Version) i think this is a coincidence an exactly similar question with the same logic was asked in one of the regional math olympiad i gave in fact for this particular question i gave three wrong submission before it was finally accepted and those submissions also used the same logic you can check that. System testing has skipped my submission can someone please help MikeMirzayanov priyanshu.p. Around 60 other people have a similar solution so it can be a common solution.
Dear Codeforces and MikeMirzayanov,
My Python submission for problem 1942C2 was independently developed, and any similarities with other submissions are coincidental. The logic employed in my solution was based on my unique approach, building upon the solution I devised for problem 1942C1. I assure you that there was no intentional violation of the rules.
Help Please
Exptecing a positive increase in rating
This is my family and my old friends
Hi may I ask if prizes have been given out? I havent received anything, thank you!
Just received a notification about filling the wallet address. But my TON keeper says that there are two address formats, starting with E and starting with U.
Which one should I write in my profile?
I won two TON coins in CodeTON Round 8, but now I don't know how I can receive them. I have a TON account
and also I updated my wallet before April 16 UTC.
What can I do beside just waiting?
I'm still not received the Ton Coin, have anyone received it ?
I haven't receive anything yet too
yes another month passed, coins are not delivered yet
Hey, the TON coins has not been delivered yet. Is there any update about why that happened?