Note the unusual start time of the round.
Hello, Codeforces!
Now that Gaokao is over, we are very glad to invite you to participate in CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!), which will start at Jun/24/2023 17:05 (Moscow time). You will be given 9 problems and 3 hours to solve them. The round will be rated for everyone.
All problems are written and prepared by Gary2005, Asuka, Crying, sjcsjcsjc, MonkeyKing, DerekFeng, KbltQaQ, ShmilyTY and me.
Statements and editorials will be available in Chinese (Simplified) after the contest.
We would like to give our sincere thanks to:
- errorgorn for his wonderful coordination!
- Alexdat2000 for translating problem statements.
- gyh20, wangziji, MagicalFlower, themoon, qiuzx, Atomic-Jellyfish, valeriu, nvmdava, mtw, AlperenT, ffao, AquaMoon, Umi, zengminghao, blobugh, Arraiter, FengzhuJian, He_Ren, LZDQ, CrTsIr, Pineapplello, feecle6418, 1.618, Alexdat2000, tzc_wk, WAtoAC2001 and tibinyte for testing this round and providing valuable feedbacks.
- MikeMirzayanov for the great codeforces and polygon platform.
- Lastly, we would like to express our gratitude to you for participating in the round.
The main character of the problems will be Tenzing Tsondu.
We hope that everyone can enjoy the round! As this round is sponsored, everyone will have an opportunity to win some prizes!
Good luck!
UPD1: Here is the score distribution:
250 — 500 — 1000 — 1500 — 2000 — 2500 — 3000 — 3750 — 5000
UPD2: Tutorial is available.
UPD3: Congratulations to the winners.
UPD4: Congratulations to the first solver of each problem.
A: alexwice
B: ksun48
C: PinkieRabbit
D: Um_nik
E: Qingyu
F: amenotiomoi
G: tourist
H: rain_boy
I: maroonrk (after contest)
UPD5: Chinese statements
UPD6: Chinese editorials
Some information from our title sponsor:
Hello, Codeforces!
We, the Ton Foundation team, are pleased to support CodeTON Round 5.
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 5 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 5 and hope you enjoy the contest!
Hope to become cm
Me too, good luck to us.
As a problem setter, give me contribution.
Do I get TON
Do I get TON
Do I get TON
Do I get TON
Do I get TON
Do I get TON
Do I get TON
DO I get TON
Do I get TON
Do I get TON
Do T get ION
Do I get TON
Do I get TON
Do I get TON
Do I get TON
Do I get TON
Do I get TON
Do I get TON
True
Do I get smoke
I got you all my mind.
platelet orz
As a first time tester I really liked the problems and highly recommend to read all the problems!
WAtoAC2001 orz
how much would average pupil solv
WAtoAC2001 orz
As a tester, give me TON.
As a tester, give me TON.
As a tester, give me TON.
As a contestant, give me TON
As a writer, give me TON.
As a writer, Gary2005 orz
Asuka Orz
Requesting to involve div2 testers.
Am I a joke to you????
In terms of your rating — absolutely :)
"Our eyes can also disguise us sometimes!!" ...What a beautiful line , isn't it :)
As a tester, I recommend participation
platelet orz
platelet orz
platelet and WhiteBloodCells orz
platelet orz
Good luck with your Gaokao results!
https://www.youtube.com/watch?v=kg5AMPZ5NUM
Let's gooo! My favourite type of rounds (combined) back after a long while!!
.
As a TON, give me participants!
I got you all my mind.
As a participant give me frequent contest.
.
Cf>>Leetcode Always!
codeton round doesnt clash with leetcode biweekly contest, leetcode biweekly contest clashes with codeton
Exactly ! CF iS LoVe , CF>>>>>LC
but always codeforces >>>>>>>>>>>>>>>>>>
things we do for contribution
Only one tester below CM? bad idea
and if you know tibinyte, there are essentially no testers below CM
As the author mentioned Gaokao, Gaokao results will be published during the contest for many areas in China.
Why is the contest schedule so disoriented? Like we have 4 contests in a week(2 contests in a day) and then next contest is showing 3 weeks later :( ?
Div. 1 (and Div. 1 + 2) contests usually appear on the schedule very early, unlike other contests. Like now, a Div. 1 + 2 has been announced 3 weeks into the future, but Div. 2, 3 and 4 contests usually appear on the contests page only 5 to 10 days before the contest. There is already an EDU round scheduled in 5 days after this contest and I am confident to say that there will be a lot more contests before that next Div. 1 + 2.
Why can't Chinese statements be available during the contest :(
My unmatched perspicacity coupled with my sheer indefatigability makes me a feared opponent in any realm of human endeavor.
I will eat kebab before this round so I hope it will be tasty round
Can i get +53 this time? Or Will I fail again!!!
Please tell me what does "TON" mean?
The Open Network (TON) represents an inclusive and decentralized internet platform, aiming to establish extensive cross-chain interoperability within a secure and scalable framework. It's primary objective is to process a very high TPS, ultimately catering to hundreds of millions of users in the future.
Read their whitepaper for more!!
Which province are you from?
I hope it is Mathforces! シ
I want to rating, o~.
A 5000 points problem! Sound scary.
As the main character of the problems,I wish you could get a positive delta.
you're a liar. you're not a tester.
I'm not a tester,but I appeared in the statements of the problems.That's the truth.
Interesting Score Distribution...
As a beginner, the score distribution seems pretty scary to me!! Looks like it would be a TON of fun.
then spare a thought for me(1st contest) :)
I want to become Purple.Btw,score distribution is wild.
The first problem has 250 point. It does mean it is very very easy?
I hope this game won't be unrated and everyone can get good scores!
5000 score problem vs rainboy.
sad :(
Hope to become expert!
TBH I got -50 or worse deltas at all of the previous 4 CodeTONs.
Now it's time to end this curse. GLHF!
Goodluck
Hmm, I'll get -12 but it's not terrible actually, but it's still negative...
For a moment, let me sum it up. It sums up to 1024*10 = 10240 TON approximately 1.2M Ruble/Rupee or 15k Euro or 100k Yuan every once or twice in a month! So much to support CF unconditionally. Ty Testers, setters and supporters!
Might be even more if a lot of people are tied around 1023.
Do I get a ton of TON?
I want to know too..
3 hrs is a bit large contest duration
Literally tourist is like gun machine every time I solve reload page tourist solves some problem tourist really a big orz i finished reading problem at the time tourist solve touxh problem
Aligaduo Tenzing Sang
Too hard:(
ps: Didn't note the start time, so I started half an hour later:) No TON for me!
Thanks you for the contest, problem D and E were really amazing!
Can you give a hint how to aolve E?
Dp[i] equal to min cost to cover points in triangle with points (0;k), (i;0), (i, k-i). Answer equal to dp[0]. I used lazy segtree to update and query dp's values. You should think a little about dp transitions.
And one more hint is that triangles in optimal solution don't intersect.
there's a different kick and nervousness getting hooked to the screen praying for NO FST, rank fall and being a CM after a long grind.
E is an amazing problem, I didn't expect the final dp to be so simple after reading the statement :)
In $$$E$$$. We have a line of $$$k + 1$$$ cells. We can paint some cells. Paint one cell costs $$$A$$$. There are segments $$$[l_i, r_i]$$$. For every segment, if we have not painted it whole, we pay additionally $$$c_i$$$.
How to solve it?
Consider $$$N$$$ lines. One line needs a triangle with a minimum side equal to the length of it. This means the cost of type $$$1$$$ is (length*A), and it will erase all complete overlapping lines. The cost of the individual is 'c'.
Then the segment tree and DP are enough where $$$Dp[i]$$$ represents the minimum cost to erase all lines in the $$$[0, i]$$$.
Is E just re-adjustment of points based on c[i], and merging the triangles after that? I hope it's not just that..
notice that triangles wont overlap
D was a bit hard to think about tbh.
Hint?
What happens if we have > 1 connected component? What happens if node 1 and node n are in different components?
True, the statements pointed to a graph problem, but I couldn't find a proper conversion to a graph setup..
any hint for c.
dynamic programming
How to solve G and H?
Orz hos.lyric
Finally understand why this problem has a score of 5000. Orz hos.lyric
I was just submitting stupid(?) heuristics, so I'd say orz problemsetters & testcases!
A and B were too easy but i really like C. It has been a while since i solved a dp problem
Good problems but for me D>E>F.
Maybe I'm Teasing GrandMaster Takagi-san now ^_^.
I liked the contest, but why was D worded so confusing :weary:
And now I fst... I love wasting 40min understanding statement that takes 10min to solve and 0 points in end.
yeah same for me, and i don't know why i got fst, can anyone help me point out the mistake until tutorial is released. submission
How to solve F?
for an edge, if there are $$$s$$$ points on the left and $$$k - s$$$ on the right.
$$$|k - s - s| = k - \min(s , k - s)\times 2$$$,which is because of $$$|a-b| = a+b-2\times \min(a,b)$$$.
And $$$\sum \min(s,k-s)$$$ for the edges means the distance all the point gather at one point.
You can enumerate the point and calculate the distance of nearest $$$k - 1$$$ points.
Don't mind my broken English (:
can anyone help me with problem D?
3 4
11110 1
10110 1
10010 2
does not pass the first case
4 4
11110 1
10110 1
10010 1
10010 1
passes the first case
but both the answer are same.. just converted the last t from 2 to 1.. t can be unique for each set.. then what is the problem??
You reversed the two numbers in the first row. You should first output the total time, and then output the number of games.
your printing order is wrong. First you have to print total time used in games and then the no. of games. you are printing in opposite order. It should be 4 3 11110 1 10110 1 10010 2
About problem $$$D$$$. It's "base" it nice. It was funny to notice after 10 minutes, that I'm just simulating dijkstra on paper.
Though, the format of problem is very bad. It was harder to understand, what am I asked to print, and how that $$$n^2$$$ is related to that. It would be better to just make something like $$$\sum_{i \in [1, n]} c_i \le 10^5$$$ and print in any format. Or print for everyone, how much time we can take him to set.
Video solutions A. Tenzing and Tsondu
B. Tenzing and Books
C. Tenzing and Balls
can C be solved using recursive dp??
mine was giving tle https://mirror.codeforces.com/contest/1842/submission/210936974
Problem C is ok with dp
can be
here is the accepted solution for recursive dp C https://mirror.codeforces.com/contest/1842/submission/210938852
Wonder how many people could prove the solution of A...
Yeah, I tried around 15 minutes, then observed that sum seemed to be the decider, since it was A, just went with it without testing the logic because I was already quite late and it seemed like something that could be the logic of A. lol.
exactly I had the same situation.
Ignore my dumb comment. should have checked carefully before posting. Understood that it indeed depends on the sum now.
It depends on sums, and in if they are equal the game will be draw. In this example the arrays would look like this:
Starting arrays:
After 0. index and 0. index;
After 1. index and 1. index;
After 2. index and 1. index;
After 2. index and 2. index;
Because after every move the ability not only from weaker monster will be changed but also from stronger one.
I think the "proof" is that any attack maintains the sum of strength on both sides. Since every attack the unit with smaller strength dies (that side loses that strength from their sum), and dishes out its strength in damage. So every attack both sides lose the same amount of strength.
It’s actually pretty easy. After every move the total sum of each does not change. Therefore the final result can be determined solely based on total sum
I submitted problem B via codeforces.com and m3.codeforces.com and I got accepted in both, however the system subtract 50 points of my problem B' score
because resumbitting substract 50 points too.
You submitted in different languages so that's a different submission, even though the text is maybe the same.
Problem C is somehow similar to: https://mirror.codeforces.com/problemset/problem/1788/E that I just need to modify a little bit.
what was your approach to solve this problem
Using dynamic programming. Let dp(i) is the maximum number of balls Tenzing could remove until i^th prefix. The transition is sinple. For the i^th ball, we can decide whether to choose it or not. Then dp(i) equals to maximum between dp(i — 1) if you don't choose the i^th ball, and max(i — j + 1 + dp(j — 1)) over all j < i, a[j] = a[i] if you choose it.
how can you choose for all j < i , a[j] = a[i] ??? that will become N ^ 2 . You must have used some optimisation, in case your solution got accepted.
As you're iterating over the array, for each value x, set $$$m[x]$$$ to be the maximum of $$$-j + 1 + dp[j-1]$$$ for $$$a_j = x$$$ seen so far. Because then for $$$dp[i]$$$, you can just say $$$dp[i] = \max(dp[i-1], i + m[a_i])$$$.
exactly, that's the optimisation. we can't go for all j < i , where a[i] = a[j]. I was mentioning that author of the above comment didn't mention the optimisation.
I have solved similarly.
https://mirror.codeforces.com/contest/1842/submission/210968569
.
Yeah, I didn't mention the optimization on purpose cause I just want to give a thorough dp idea. Of course, it's O(n^2) if you traverse all j, and you have to do something to find max(dp(j — 1) — j) efficiently. How people optimize it will be based on each one.
After this contest, Litang and tenzing's story will be much more popular than before.
When I read the statement about tenzing, I hope someone can give me a smoke.
The problem D without clarification was difficult to understand, but adding an explanation along with the problem statement would have been very helpful for many people.
What is orz ?
https://mirror.codeforces.com/blog/entry/110951?#comment-988719
its a picture of a person bowing on the ground, look closely, o looks like a head
what is testcase 39 for D?
Finally CM (hopefully).
Well it seems like a long journey but probably it's even a longer path ahead. Here's what I learned in this journey.
All the best everyone. wish you positive deltas in the future :)
Congratulations bhaiya!! Thank you.
Thanks :)
Congrats i_pranavmehta bhaiya
Path becomes easy when learning becomes joyful. --the most liked
tourist Orz
Some feedback on the problem set:
long longvsintbug.Overall the problems were very nice and, even though my performance was underwhelming, I liked participating. Thanks to the authors.
Thanks for your feedback!
I don't know if you will agree, but I think H is the best problem in the contest. Please try it :)
It is a fantastic problem indeed! Thank you for suggesting it.
There is a bit of magic going on in problem H. After reading it I immediately thought "This must be a technical thing about computing the measure of an arbitrary polytope", I was wrong.
Did any one solve C using dp (recursively)?
you can have a look https://mirror.codeforces.com/contest/1842/submission/210938852
// you can solve this using 2 state dp
My python solution for D got accepted during contest, but during system testing it got stuck in TLE. My week is ruined now.
Hey, sorry I didn't get to answering your question from before.
It's on you to research/test how any code you didn't write will perform. Python is a lot of someone else's code, with their work, wins, but also their assumptions, mistakes, and tradeoffs... and there are multiple implementations (cpython vs. pypy) each with their own characteristics. If such research is beyond your level of motivation, then c++ might spare you some friction in cp, but a lot of the issues exist in every language -- some are just taken care of due to c++'s popularity in cp (like custom stack space for deep recursion) while others still need research anyway (fast IO copypasta)...
I'd start at "just use pypy-64" and "substitute for input,
input=sys.stdin.readlineis a fine starting point but other options exist"Things to worry about down the line:
Otherwise, congrats on recognizing what D was actually asking. Good luck with whatever choice you make, and hey, you don't need to pick only one, nor does your choice need to be permanent... otherwise I'd still be writing in ye old C and just not doing any hobby coding.
Could I have a hint for D and E?
I've noticed from people's code that D is something to do with shortest paths, but I don't see the connection. All I know is that if 1 and n are not in the same connected component you can play for infinity.
For E, I noticed that if two triangles overlap you can replace them with one big one but I didn't know what to do from there.
Notice how a set 111...0 where only the last elenent is 0 is always a viable game. How many times can you play such game? Then try constructing a weighted graph. What are the weights of this graph?
OK that makes sense, I think I get it now. Thanks also hhvmegyy and Hmys
for a problem D: greedily play with every playable friend until there's noone playable
I think a hint is that, if you have a path from 1 to n, any time you play a game, you have to decrease an edge on that path. Because 1 has to be included and n can't be included.
Since the language in problem D was a bit unclear, I request to consider those cases where time spent with animals is 0 to be not considered a game that is 1 should be in that constraints should be lifted.
I got the idea of F after about 25 minutes, but I tried solving it with dp on tree, ignoring that it can be calculated with bruteforce. I felt into a thinking trap that it must be difficult to implement because it is F.
Can someone explain question D? What do the restrictions exactly mean?
1&2- We must include animal 1 and exclude n in all games. 3- For 2 animals u and v, (only u without v) + (only v without u) should not be more than R times.
Thanks. I think this was written in the notification we got during contest. Is there any way to look at a contest notification again after I close it?
Yes, in the dashboard page, below the questions, all past notifications appear.
I did D with just straight forward greedy. The idea is that the order of the set doesn't matter. So you can just start from a set of friends of only 1, then remove the smallest edge out of the connected component and add the new friend into the CC. It should take at most N games to finish.
Got a small bug with edge of weight 0 and took a whole hour to find it. So sad.
Can anyone help me in problem C Code1 is accepted while Code2 is giving TLE?
Base logic for both are same the only difference in Code2 we are iterating for all occurrences but in Code1 101 occurrences from start and 101 from end.
I had thought of using this solution, but it would have been a hack. this solution must be hacked.
In problem C, I saw some solutions using a global dp array and memset, still being accepted. I was wondering that since test cases are $$$10^3$$$ unlike conventional $$$10^4$$$, probably that is making them safe. But are the submissions not on the very edge, like $$$2 * 10 ^ 8$$$ computations in $$$1$$$ second ?
Yeah Actually, I still couldn't understand the intuition behind iterating 100 times from front and back. Was it pure luck/ hit and trial or am I missing something here?
memset is fast because it uses some optimizations under the hood. It is much faaster than a for loop
https://www.youtube.com/watch?v=JmQugCTIVgA My solution for C
why so many downvotes?
no idea gg
How is the prize money distributed?
How can we receive the TONs?
in the past, the wallet was requested later only from those who won something (cf message from system)
Any proofs why bfs from every vertex works for F?
consider the most optimal group of K vertices, select the centroid V in it, when traversing, when we fix the vertex V as a centroid, after adding k vertices, we will find the same group because we choose the most optimal values for the centroid V
Can anyone prove or disprove/hack this solution for D:
I use the heuristic of picking the cut with the minimum number of edges. If an edge between two nodes goes to 0, I merge the two nodes into one node. Repeat until the graph is just 1 node.
My solution gets AC: https://mirror.codeforces.com/contest/1842/submission/210975963, but I personally think its incorrect.
Does G actually need formal power series/exponential generating functions? That was the only way I was able to make it make sense; it feels like there should be an easier way...
Got a runtime error (STATUS_ACCESS_VIOLATION) at D test 16. Does anyone know what STATUS_ACCESS_VIOLATION means? Is it the same as accessing out of range for array? The strange part is that the data range in 16 is the same as in previous tests.
You are probably accessing
lim_set.rbegin()when it is empty.Yeah. A stupid mistake T_T. Should check the boundaries more.
Hey I have an issue with my email, can i know how can i receive the prize if I don't have my email working. Can i get the prize through codeforces directly.
I got TON
I didn't :')
Just ignore it, he didn't participate even.
ik :))
ik was kidding :')
When can we expect to get prize? Like what is the timeline of distribution since system testing is already over.
Someone please mention whether they have received the prize or not.
I have the same question.
It takes a bit for them to reach out, maybe 1 or 2 weeks. I received prize in a previous round, it just takes a little bit.
In fact, there is an $$$O(n)$$$ solution for problem E(submission). I have explained it in in the "Alternative Solution" section.
Orz
My rating ...
Why are the ratings of this contest rolled back without notice.
Maybe plag check
why was this contest not rated, even though it is written it is rated? today i saw my rating and it dropped , and there is no update by organizers. please update!
I was stunned after seeing such downvotes! even though my argument was correct. even Though Happy that ratings were rolled back.
you said "why was the contest not rated", though it was and ratings usually get rolled back for sometime after the contest (I am not sure about the reason). Hence your comment got downvotes as you said something which was totally false, try asking questions next time when you are confused rather than jumping to conclusions, Maybe "why are the ratings rolled back" would've fetched correct responses :). Hope this helps.
why ratings of this are round taken away ? will they be returned?
Is the contest being reevaluated?
Yea i think so
How will we receive the prizes won in this contest, that is, the TON cryptocurrency?
I've heard they'll ask for wallet credentials in some time
The game added a lot of points and I'm very grateful for the game
I think I entered wallet correctly but I still not received TON in my wallet. When will the reward be received?
Maybe after July. 7 (DDL), I think.
sus
.
Has anyone received their TON yet?
Well. NO. Received msg from codeforces system before that I should update wallet address ahead of 7th July, but nothing received yet..
I finally received it on August 11
Just noticed how similar problem C is to the N^2 DP solution of longest increasing subsequence!
When you're the $$$n$$$-th friend in 1842D - Tenzing and His Animal Friends :