# 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

my Doge councildrdilyor orz

where is smiesmie :/

I joined！！！

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 Paintis 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?

Codeapparently 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-C2is 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

hintmake 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://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 problem11- 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:

SpoilerThe 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://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 hardproblem.HappySolved Problem C1

Sad8 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://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://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

Hello codeforcers and MikeMirzayanov. I had written original solution for C2, it had also appeared in a regional mathematics contest here at india, so the idea was kind of intutive to me. I had solved all problems from myself, and even my idea for 1942C1 (which was easier version of C2) was original, and I had used my very own method and I extended the same idea to cater C2 as well. As someone who is serious and honest for rating, I find this a mere coincidence and I assure you no such violation of rules would be done by mistakely or otherwise.

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?