Hello, Codeforces!
A wonderful summer holiday! After College Entrance Examination, we are extremely delighted to invite you to our second round, CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!), which will be held on Jul/31/2022 17:05 (Moscow time). Note the unusual start time of the round.You are given 8 problems and 2.5 hours to solve them.
All problems were written and prepared by Cirno_9baka, CoupDeGrace, Sugar_fan, ODT, Yakumo_Ran, farmerj, MagicalFlower, izlyforever, kuangbin, mejiamejia, ugly2333 and me.
Task statements and editorials will also be available in Chinese (Simplified) and Chinese (Traditional) after the contest.
We are sincerely thankful for the help provided by:
3.141592653, emorgan, errorgorn, SevenDawns, prabowo, why_no_girlfriend, valeriu, arvindr9, ExplodingFreeze, Huah, chenkuowen, plagues, antontrygubO_o, lych123, YunQian, magnus.hegdahl, Bench0310, Roundgod, njupt_lyy, null_awe, aniervs, Savior-of-Cross, dorijanlendvaj, Suiseiseki, dannyboy20031204, Lucina, ChthollyNotaSeniorious, JianfengZhu, aaaaawa, leukocyte, RiverHamster, -skyline-, Nanako, Nezzar, I.Gleb, glebustim, Y25t, gisp_zjz, Mitsukasa_Ayase, ustze, Vladithur, IIIIndex, Acfboy, 127.0.0.1, tibinyte, i_wyxkk_ak, TML104, spookywooky, 4qqqq, CSP_Sept, marzipan, efimovpaul, Erkhemkhuu, ak2006, NeuraXmy, RomkaRS, bpaT_Kapaca, sus, snowysecret, 755352046, IgorI, and Kieray for testing and good advice
74TrAkToR for his excellent round coordination and help with preparation
MikeMirzayanov for great systems Codeforces and Polygon
MinakoKojima, Ynoi, Suiseiseki for proposing problems that didn't been used in the final version of the round.
- Nanako, absi2011, Nezzar, QAQAutoMaton, rgnerdplayer for helping prepare the problems.
magnus.hegdahl for strengthening the data of one problem (but because the problem was too hard, we removed it)
emorgan for reviewing the statements
dannyboy20031204 for traditional chinese statement and editorial
You, for participating!
This is our second round! Great efforts have been put in during the past year. We are sincerely looking forward to your participation and we hope everyone will enjoy it. Besides, this round is sponsored, which indicates that everyone has an opportunity to get the prize!
Good luck!
UPD1: Here is the score distribution:
500-750-1250-1750-2000-2750-3500-(2250+2750)
UPD2:Tutorial is available.
UPD3: Simplified Chinese tutorial is available.
UPD4: Traditional Chinese tutorial is available.
UPD5: Congratulations to the winners
- tourist
- jiangly
- ksun48
- Rewinding
- djq_cpp
- maroonrk
- cnnfls_csy
- he_____hezhou
- 353cerega
- WYZFL
- ecnerwala
UPD6: Simplified Chinese statement is available.(please download it and open it with edge)
And here is the information from our title sponsor:
Hello, Codeforces!
We, the TON Foundation team, are pleased to support CodeTON Round 2.
The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.
Since July, 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 2 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 2 and hope you enjoy the contest!
Good luck for everyone!!!
I hope everyone enjoys this competition.
cool
cooooooool
hope it will be more friendly to newbie
Orz! I believe you will get a big suprise o(*^w^*)o (
As a last-minute tester, solving the problems in this contest has re-sparked my interest in competitive programming, something which I have forgotten about for a while now.
Thank You, AquaMoon
Wow! Thank you! I believe you will be an excellent programmer! Keeping your original dreams and interest is wonderful ๑(≧▽≦)✧
How to be a last-minute tester?
I hope it is not Mathforces again!
Don't worry. Wish you good luck! (●'◡'●)
Thanks :)
WTF is this contest, are u serious ???
I like MathForces Hehe
lol seems it's a controversial topic, I see the below hope for Mathforces comment even has more upvotes than mine
I am SUPER excited for this round!!!!!!!!!
Good luck! ヾ(≧▽≦*)o
please no math
Math Round!!
Best of luck！
Gook luck! I believe you can do it! (❁´◡`❁)
So many nice people in the helper list, this competition will be great.
Thanks for your support! Wish you good luck! =❁ω❁=
the previous contest of AquaMoon is too hard..hope this round can be a normal round.
Since Yakumo_Ran is (again) a problemsetter, will there be Touhou statements?
I wonder if Doremy's IQ can handle this contest
Maybe Cirno couldn't \xox/
Not this time, but we may continue to work together in the future, so maybe the next one will.
Nope, but there'll be many Cirno_9baka problems :)
blue meow come and kiss
As a tester, good luck to everyone!
Good luck!
hope this round will be interesting
Of course. Good luck and enjoy yourself! (●'◡'●)
Yay codeton
4 weeks ago
Will answer later
As a tester, I think some of the problems are very interesting.
Hope all of you will enjoy it!
A really good round!
I agree with you!
this
some ofgives more trust than usualallSuper data structures round?
No.
Is AquaMoon a girl?
Of course she is!
Suiseiseki is one of my best friends, you can trust him. No doubt I am a girl ~ (☆▽☆)
My glad to be a tester again. Thanks to all of the authors!
This round will be very interesting.
Wish everyone good luck!
(The statements are short and pretests are strong and give me contribution XD)
Why is spaghetti.code shown two times in the registrants page with a red highlighted number?
What's the prize distribution?
We will update it later. Now it is still mysterious to stimulate your interest! (≧▽≦)
Amazing contest, I really enjoyed it!!
Cute AquaMoon's cute round with cute problems!
Hope everyone enjoy it :)
Cute Yakumo_Ran ! ☆w☆
Can't help but notice Aquamoon trying too hard to be cute in every comment and blog-post.
No offence o(*^w^*)o (●'◡'●) ヾ(≧▽≦*)o (❁´◡`❁)...
She is indeed very cute. I treat her as my own sister. When I chat with her on QQ, she has a lot of expressions, at least I am used to it.
I hope it is Mathforces! 0w0
so many people!
I'm too curious to see your face!
Just imagine a cute girl! ☆(≧▽≦)☆
It's been proved for me that imagination is never close to the reality ^_________^
WOW!!
So many testers in this round XD
AquaMoon orz ❤❤
Are u really a cute girl? Don't dig traps for me. ;-;
Yes, I promise! o(> ω <)o
I can guarantee that because I am one of the writers, you can trust me.
I have been bamboozled so hard
so hard I really had to scroll up to check
No, I am indeed the account of one of the writers. It's just that for some reason, I don't use that account to leave a message. You can notice a fact: if what I say isn't true, aquamoon will definitely ask who I am.
ok but afaik alts are illegal? intensive thinking
I thought the use of alts are okay as long as you don't participate in a contest with more than one account at a time based on what others were saying
Someone encourage me to participate please I only lose my rate *_*
Don't worry too much about your rating. Just ignore it for now and the only way to improve faster is to participate in as many contests as possible.
Thx bro i won't give up
I hope it will be a good round.
We hope you will enjoy this round >_<
I think it is gonna be a very creative and unique round. Hope I can reach BLUE thru it though a bit worried...
"after college entrance examination".
You mean gaokao in China? In India we have JEE.
Did all the authors get into tsinghua university?
cirno_9baka went to Tsinghua University.
Chinese editorial! That's great!
Good luck and have fun!!
My nightmare of Round #732... Now the problemsetters come back again!
Good luck! but I am not skilled in math problems :(
As a tester,wish you good luck and enjoy the contest!
Is this contest rated for everyone?
Yes.
Really enjoyed Round 732 <3
Hurray we have traditional Chinese statements and editorial!!! I am a HongKonger (not shown in my profile though) and I'd love to see that!
hurray!
According to the comment, is it true that Sparky_Master_WCH1226 and other "Bostwana" users are actually from HK?
Sparky_Master_WCH1226 is from HK, but I don't know for others.
where is the score distribution ?
It will be updated later. (●'◡'●)
Chinese statements! Cool!
Chinese statements and tutorials will be updated after the contest. (๑•ᴗ•๑)
Good luck for everyone XD
Everyone should have a dream, and I hope I can reach 1400 points through this round.
All persons will get in total 10240 TON.
what is ton
it's explained in the announcement
Why was I marked as a tester of this round? I haven't solve it. Will Can I take part in this round?
I invited you, maybe you forgot.Thank you so much for taking our test! You can ask me on discord for specific things.
Ohh! I checked it one more time and i really tested your round few month ago. Sorry for this fake message :D
Hi dear friend! In fact you have already tested it a few months ago ~
I guess you forget it ~
So I am afraid that you can not participate in it o(T︿T)o
Sorry for fake message :p
Hope it will not be mathforces again
It won't be. Problems will be as cute as AquaMoon
Thank you ~ (๑•ᴗ•๑)
CUTEFORCES
Good luck to myself and good luck to everyone in the rankings!
I wish I could get rank 1 in this contest and defeat tourist too and impress AquaMoon
I can understand wanting to win first place, but I don't understand the point of impressing aquamoon, she has a boyfriend, good luck.
did you seriously make an account just to simp for AquaMoon ._.
Sorry, I noticed that your message was not a reply to me, but I can't delete it, please ignore it.
what is div1 +div 2??
i mean what will be the difficulty of questions
like global round.. check this
8 prblms in 2.5 hrs . Hmm seems like Div3 level i guess ??
Good luck
I hope there is not too large gap of difficulty between any adjacent problems.
The difficulty gap between the problems is at most $$$998244353$$$
.
.
.
.
=❁ω❁=
What ToroTN wants:
A:2400, B:2500, C:2600, D:2700, E:2800, F:2900, G: 3000, H: 3100
Yep that seems legit.
I should say not too large and not too small. Lmao.
When will the scoring distribution be announced?
If somebody won't take their prizes, will it pass to the next ones?
Also thanks for that valuable prizes.
I got a feeling that the problemset is bound to be nice, given the grand problemsetter & tester team.
Hoping for a balance round!!
Hope I will reach CM after this round
Good Luck EveryOne!
So will the score distribution be announced?
Updated. (●'◡'●)
Thanks!
Second "note the unusual start time" comment.
I'm so happy to be able to compete with the big boys again!
Finally today the Great Battle between the top 3
giving a CF rated contest after almost 3 months . lets relive those days again
dang it, I think tourist will be dethroned today
no
oh damn last second NEVERMIND!!!! LET'S GOOOOO
Who the fuck wrote problem D's statement?
What was wrong with it? It was clear to me
The "For every" part is vague, mainly because he asks you for the number of type 2 operations, which kills the assumption that all arrays have the same number of operations.
I see two occurrences of "for every" in this statement and I do not see any ambiguity with them. Also, where did you get the assumption that all arrays have the same number of operations from???
I mean the second one, It kind of went that the actual operation eric was doing is doing an operation for every array.
Also, I am 100% sure I am not the only one who didn't understand this part.
"There are two operations that Eric can perform on an array ct:" — I don't see how you can get such assumption with this specified. It's quite clear that each operation concerns one specific array and the "for every" part doesn't change that. I don't see any fault on the authors side
lol, Okay then how come this passes 166396472
That's how I understood the problem too but I wasn't able to solve it until I made that assumption.
It passes, because it is a correct solution even without assuming your false assumption
OHHHHHHHHHHH, okay lol my bad just noticed.
I feel pity to read this comment cuz actually author team rewrite and polish the statement of D for many times. Personally speaking, I don't think the misunderstanding you mentioned is that frequenct for others, I feel it sounds more like a accident. ;w;
02:29:15, wow!
How to solve $$$E$$$?
How to fix
Wrong answer on pretest 5in $$$E$$$? :(I thought the answer is: Sum of all values that will reach the sink plus amount of steps in which the sink won't output any number. These steps can only happen in the first $$$~1010$$$ steps. But I got WA pretest 5. :/
You should terminate if there is nothing left I think.
Yes, I stop searching for steps in which the sink won't output any number, if there are no more values left to be output.
How do you calculate the amount of steps in which the sink won't output?
Every node $$$i$$$ has an array $$$a_i$$$ with $$$a_i[0]$$$ being the input. We sort the nodes topologically and start propagating along edges $$$i \rightarrow j$$$: $$$a_{j}[t+1]:=a_{j}[t+1]+a_{i}[t]$$$. This makes one timestep. This won't be exactly right if simulating it, since the values don't get propagated all at once, but they will have to wait in the next node either way.
Then I take a look at $$$a_{sink}[t]$$$ and iterate $$$t$$$, adding the value to the variable $$$occupied$$$. After each step $$$occupied$$$ is reduced by one. If $$$occupied$$$ reaches $$$0$$$, we have a step with no output. We only need to check the first $$$~1000$$$ steps. See also 166388098.
Take a look at Ticket 15961 from CF Stress for a counter example.
Oh wow, the case $$$a_i=0$$$ for all $$$i$$$ was my mistake. Had to change a $$$0$$$ to a $$$-1$$$. That is disheartening.
Tourist with the CLUTCH SOLVE to beat Jiangly!!!!
Hints for problem D?
Notice, that the first operation doesn't change sum of prefix sums and the second one decreases it by 1.
Thank you so much. It was a very unique observation. Can you also give hint for how to find the number of operations please?
UPD: Never mind
prefix sums
Tourist nailed it at the last minute and came on top! What a competition!
I tried D for 2 hrs and was not able to solve it
And tourist managed to read, think, code and submit it in just 3 mins !!!!!!
How???
$$$\sum i \cdot c_t [i] $$$ is same for each row except the special row $$$k$$$, for which it is one higher for every operation done on it.
Not only is his IQ much higher than ours, it is also likely hyper-concentrated in quick assimilation of information, mathematical accuracy, and logical creativity.
$$$+$$$ Lot of experience and practice.
After solving a zillion different problems about prefix sums, you would be able to spot in three minutes that the sum of prefix sums decreases by 1 for the special array, and for the rest, it remains constant
tourist's last minute submission. Damnnnn...
When I thought that jiangly will finally reach top 1:
Then this happened:
dramatic.
That was one of the finest buzzer beater !
What's that delta predictor extension you are using?
Carrot.
I also think jiangly will become the new King until the last minute :)
nice round, but disgusting problem D :(
Why is TL in E so unnecessarily strict? I have $$$O(n*(n+m))$$$ solution which does not cross TL, but according to the constraints, it should pass easily.
It's not strict, you forgot to check vis state in DFS.
fuc******** cant believe missed AC by 1 line
1 min before the end of the contest: Jiangly will beat tourist! After the contest: what? tourist solved G at 02:29:15?
wowww..! tourist's last minute clutch!!
It's dramatic that tourist overtook jiangly 1min before the contest ends.
Plot armor irl!
Thanks, OEIS!
in which problem?
F
problem F
F is much too weird. Maybe it's better to set $$$n\le 1000$$$ for those who doesn't know the conclusion?
Please stop making OEIS problems.
Problem E can __int128 hold all variables?
Of course not , the maximum variable can be about $$$O(2^{n/2})$$$ .
can java BigInteger or Python pass it?
No.
May be It can be calculated , it will get TLE .
My bigint solution in C++ passed system tests.
Cool. So it seems Java BigInt can solve it too.
how's that O(2^(n/2)) calculated? can u prove it?
Say if you had a graph like this
Initially, assume a value 1 at node $$$1$$$. After $$$t = 1$$$, this value will go to nodes $$$2$$$ and $$$3$$$, and at $$$t = 2$$$, they will combine to become 2 at node $$$4$$$. At $$$t = 3$$$, the value will go to nodes $$$5$$$ and $$$6$$$ and at $$$t = 4$$$, they will combine to become 4 at node $$$7$$$.
So, the value will keep doubling every $$$N/2$$$ nodes, resulting in $$$2^{N/2}$$$.
Thank you! Learned a lot from u.
Why would you want to do that if we are asked to compute modulo an int?
Because it seems to be small enough, not the case of 1 million bit, it is like we use bitset for 64 times faster. If a type can hold it, we can simulate it using O(n*n).
I solved it like that as I didn't think of simulating the first $$$n$$$ iterations: 166393805. Note that the big integer operations work in O(n/2/60 = 9) in the worst case.
Cool. So mine will be ok if I replace int128 to some BigInt-like struct. Thank you.
Whoever came up with problem D is an artist. Best problem of this year
I await the punchline
Fight between tourist and jiangly is always legendary and dramatic for 1st position !
I live to see Tourist vs Jiangly.
Sorry, I hate this round very much.
(≧▽≦)
In G, I reduced it to the following problem:
Given arrays $$$\left\lbrace a_i\right\rbrace_{i\in\lbrace 1,2,\ldots,n\rbrace}$$$ and $$$\left\lbrace b_i\right\rbrace_{i\in\lbrace 1,2,\ldots,m\rbrace}$$$, find all positions $$$j$$$ such that the array $$$c=a[j{.}{.}j+m-1]$$$ is equal to or greater by $$$1$$$ than $$$b$$$ in every position: that is, for every $$$j\in\lbrace 1,2,\ldots,m\rbrace$$$ $$$c_j=b_j$$$ or $$$c_j=b_j+1$$$. Recall that if we remove the $$$+1$$$ possibility (that is, $$$c_j$$$ should be equal to $$$b_j$$$ for all $$$j$$$) then this is simply a substring search task that can be solved using KMP.
Any ideas for "weak substring" problem?
Let's split the numbers that appear in a in b by numbers that appear a lot and numbers that don't appear a lot. Try to match a number x in b with numbers x or x+1 in a.
For numbers that appear a lot use fast convolution, for numbers that don't appear a lot use brute force. This ends up in $$$O(N\sqrt{NlogN})$$$ if you split numbers at frequency around $$$O(\sqrt{NlogN})$$$ I think.
Using Fast Fourier transform we can calculate $$$\sum_{i = 0}^{m - 1} (a_{i + j} - b_i)^2(a_{i + j} - b_i - 1)^2$$$ for every $$$j \in \{1, 2, \ldots ,n - m \}$$$ in $$$O(nlog n)$$$ time. Each $$$0$$$ in this sequence corresponds to "weak substring" starting from position $$$j$$$.
Yep, that's a nice generalization of "match strings with questionmarks", that is also computed with
Another way to do it is to do string matching with wildcards twice, on even and odd values.
For the first matching on even values, we mark all odd numbers on $$$a$$$ as wildcards. For all odd numbers in $$$b$$$, we add $$$1$$$ to it. Then this becomes the usual string matching with wildcards.
The second matching is done similarly. We just have to check that the substrings match in both cases.
Can't believe I guessed the second part of answer for D based on the test samples and some data I collected for the first part.....still no clue why it works.....but somehow I have confidence that it would pass the system test....
Even though I sit for almost 2 hours thinking about D and I feel totally useless, I have now read the required observation and it's just beautiful. I wouldn't mind failing miserably every time if the problems are like this one. Thanks to the author.
How to solve 1704H1 - Game of AI (easy version)?
I got it slightly late :(.
We case on B. Each element $$$k$$$ of b falls into 4 types, depending on the two decisions $$$b[k] = k$$$, and whether there exists i!=k such that $$$b[i] = k$$$.
Let's say there are i elements such that b[i] = i, and j of those appear again in the array. The total number of such arrays is the product of:
$$$\binom{n}{j}$$$ -- number of ways to choose elements such that b[i] = i
$$$\binom{i}{j}$$$ -- number of ways to choose elements (b[i] = i) that appear again
$$$\binom{n - i}{n - i - j}$$$ -- number of ways to choose elements (b[i] != i) that appear again
$$$j \cdot (n - i + 1)!$$$ -- number of ways to set the values for the n-i elements that do not equal themselves (This is non-obvious, but try creating a recurrence relation)
Then for each of these b arrays, there are $$$(n-i)^{i-j} (n-1)^j$$$ a arrays that correspond to each.
Summing over all $$$i,j$$$ gives the answer.
Oh wow, that's completely inverted line of thinking to what I was thinking was much more natural. I thought to characterize for each a how many bs we can get and sum over that (which actually looked quite viable, but didn't manage to do so)
I spent most of my time doing that, but when I switched perspectives it worked really well (but not fast enough :( ).
I couldn't really come up with any ideas to combat the fact that things in a can have high 'indegree'. What were you coming up with?
In this problem we are dealing with functional graphs. If we focus on one connected component then it is almost a tree and the problem is easily solvable on trees by some dynamic programming. We would like to maintain two numbers for a tree that we assume has some outgoing edge of the root. Namely, how many final configurations we can get depending on whether the root will make a move or not. If these pairs for our subtrees are
then if we denote the pair for the root as
then
and
and this is computable through some dps (possibly in $n^3$ as we can use preprocessing)
The idea would be to improve this approach to handle the additional edge somehow and combine various connected components in a knapsack-like fashion with some Newton's symbols along the way.
I guess that's what I was doing, looks like I'm the only stupid guy with hundred lines of weird dps instead of 5 lines of formulas (I still don't understand your solution). 166399131
Ok, the main idea is that for each array $$$b$$$, we want to count how many $$$a$$$ will work.
If we have $$$b[k] = j$$$ for $$$k \neq j$$$ that forces $$$a[j] = k$$$ (because $$$j$$$ must have invaded $$$k$$$). This means that if we have $$$n - i$$$ elements of $$$b$$$ that are not fixed points (and $$$i$$$ fixed points), then $$$n - i$$$ of the values of $$$a$$$ are fixed.
Now for the indices $$$ind$$$ for which we do not know $$$a[ind]$$$ that were invaded, they can have any of the $$$n - 1$$$ possible values, as we can just assume they are placed later in the permutation than the thing that invaded them, and everything will be consistent. For the indices that survived, they can go anywhere that does not have $$$b[k] = k$$$ because we can assume their invasion was overridden later.
Basically any $$$a$$$ that does not cause simple contradiction is possible, because we can just place certain elements at the beginning or end of the permutation.
(I'm not good at English so I used DeepL translation. So if there is any unnatural English, I am sorry.)
This image is a Google search result during Coding Phase.
They (the uploaders of the top 3 videos) seem to upload their solutions to YouTube during the contest, isn't this a violation of the terms and conditions?
(if I misunderstand and this is not a violation, sorry.)
PS: I took my friend's advice and improved the grammar of this comment.
https://twitter.com/kenkenokkuu/status/1553781614941175808
How to solve H1?
E is cool, D is too unnatural to be a good problem, but it's decent, B and C both very boring problems with standard greedy, A is fine
How do you solve problem A efficiently ? I tried recursive memoized approach, got TLE.
My Submission
You just check if the last m-1 characters in string a is the same as the last m-1 characters in string b, where m is size of b. Then just check if the first character in b exists somewhere in string a before the last m-1 characters. If both are good, then its true.
Notice that you can't change last m-1 symbols of string a. So if last m-1 symbols of string a are not equal to the last m-1 symbols of string b, then the answer is "No". Now we should check b[0]. Consider two cases:
1) b[0] == '0'. If a[0:n-m) contains '0', then we just apply (n-m) min operations to string a to get '0'. We can't do that ONLY if string a[0:n-m) consists of n-m '1' symbols (as min(1,1) = 1; max(1,1) = 1).
2) b[0] == '1'. If a[0:n-m) contains '1', then we just apply (n-m) max operations to string a to get '1'. We can't do that ONLY if string a[0:n-m) consists of n-m '0' symbols (as min(0,0) = 0; max(0,0) = 0).
We can check these conditions in O(n).
I'd really appreciate if people told me why did they downvote my answer.
This approach works (166352851).
Why there wasn't any announcement that the statement for E changed? I was debugging for an hour just because of the third example. :(
Finished E after contest (at least I think finished)
Dropping out of violet because of the wrong submission for A...
No worries, you will regain your rating for sure.
How to solve E?
My idea is pretty much optimized simulation
Cannot check whether it is right until systests finish though
For the guys who solved D. How did you come up with the prefix sum observation? Had you solved similar problems before?
I thought about prefix sum as well but my final solution does not have it
I was looking for an invariant. I didn't find a prefix sum observation (although it is the same after all).
First idea was sum of values... though this stays also the same for the fake-row. So it was of no use.
Next idea was alternating sum. That was strange and I couldn't get any information out of that.
Third idea I imagined the values as stones. Each operation is moving one stone to the left and another one to the right. Now the stones are worth some points. I needed the pointvalue to stay constant after an operation. So I decided, moving a stone to the left removes one point. Moving it to the right adds one point. So every stone contributes as many points as its position. Doing the normal operation keeps the total score constant. Doing the fake operation adds one point. So $$$\sum_i i \cdot c_t[i]$$$ was my invariant which I could directly use to find the fake row and calculate the number of operations on it.
Same here
I thought that it should be possible use some array with only two nonzero elements
Then thought where should those elements be
Then after experiments and thoughts about centers of mass ended up with these formulae
Thinking about the center of mass is nice too indeed! It also stays constant under the first operation and moves on the second operation. Cool physical interpretation.
It can also be interpreted as the position of the center of mass (multiplied by the mass).
Still, Why would anyone come up with i * ct[i]? Why are we multiplying? You yourself are saying every stone contributes as many points as its position so total points is just sum of stones (no use). After this how do we get i * ct[i]? All logic before this seems intuitive but the formula does not. How does one come up with this?
Imagine you played a game. You place stones on a score track. At the end your total score is the sum of all stone's scores. This is your situation right now:
How do you calculate your total score?
Hmm, Clear now, Thanks.
It's a common technique. When you have operation like adding or subtracting, see what's the effect on the prefix sum/difference array.
I was thinking in terms of parity of the difference array but couldn't get anywhere.
Its common to take prefix/suffix sums when we consider operations on adjacent indices. Another recent example problem: link
can anybody tell me what is wrong in my code for B ? i spent much time to this due to which i solved C very late and had only 20 min for D https://codeforces.com/contest/1704/submission/166395252
Your approach fixes $$$v$$$ to be equal to the first value of $$$a_i$$$ after a change (or at the start), but this is not necessarily optimal. For example, if your $$$k = 3$$$, and the first two food piles have values $$$4$$$ and $$$10$$$, then you should actually use $$$v = 7$$$ to eat both without changing.
Instead of actually choosing the value of $$$v$$$, you should instead keep track of the maximum/minimum so far. As long as the difference is $$$\leq 2k$$$, then there exists a value of $$$v$$$ that can handle all those elements. Once the difference becomes $$$> 2k$$$, a change is required and you can reset maximum/minimum.
For E how actually to take mod without influencing the final answer. I suppose taking mod before calculating maximum will produce WA, so there is no way to take mod before output (but then the answer can reach 2^300 somehow)... Got stuck for the whole contest orz.
I guess we can just take the last vertices without outgoing edges, then we don't need to think about maximums
.
.
Could you or someone else please point me to an official statement regarding the usage of pretests during the round? I'm not trying argue with you, I'm genuinely curious about this. Obviously, pretests reduce the pressure on the system, but also, they are a nice tool to make the whole experience more exciting (like freezing in ICPC). Another thing is that pretests make you a better coder. Yeah, it sucks when you get FST, but the danger of it makes you more careful both when solving and coding. Lastly, pretests make the whole hacking process possible.
All I found is this from the contest rules:
It is known that pretests do not check solution completely. Usually there are 2-10 pretests, and the fact that the solution passed pretests says only that it is quite reasonable. Typically pretests not contain the maximal tests, corner cases, etc.
And also this from the contest preparation rules (from this post):
In general, pretests should include: a test with maximum size of input (e.g. maximum n), a test against integer overflow, a few random small tests. All corner cases that are easy to miss. If you deliberately don’t include some corner case, talk to the coordinator about this.
These rules also say, that wrong solutions should be prepared for integer overflow and for case work. These solutions should also fail pretests, which kind of contradicts the first citation:)
While some might complain that the contest was too hard (I think it's fine for a Div1+2 though), I don't think anyone can complain about the quality of the sample input/output. Very robust set of input/outputs such that a matching output is unlikely to be a coincidence. You still need to consider edge cases by yourself, of course, but I really appreciate not having to deal with the paranoia that the general idea is wrong even when the sample output matches.
Me:
FML
does eng Tutorial of G,H gonna be available later or only Chinese are given?
They will be later
The editorials of problem G and H will be adding soon.(from editorial)Wow! Now tourist has a one kiloTON of crypto!
Weak tests in E, why are solutions that just simulated using big integers passing?
As a tester, I'm sorry for not realizing that the main test for E is weak :(
I've submitted an uphack just now.
So will have a re-run?
I also uphacked my solution with a test that provokes overflow, as I had forgotten to take mod in some places. But I couldn't find other solutions failing with the same test. Maybe because my approach is a bit different to most other solutions. Thanks for the weak tests anyway :D
What was the point of such strict time limit in E? (one second for seemingly intended O(n^2), n = 10000)
My python solution doesn't pass, c++ — easy.
I understand when it is intended to cut down inefficient c++ solutions but was there really anything like that here?
N=10000 (O(N^2)=10^8) is not the same as N=1000, T=10 (O(T*N^2)=10^7).
I edited your last python submission, changed the number of steps from 10000 to 2000, and it passed 166417578
Thanks. I really didn't pay attention to the first part of constraints and just assumed that we can have 10k vertices....
And now that I look at my code again I should've added break if not changed, then it wouldn't matter
To not keep you waiting, the ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!
It's very sad when attempts are ignored because of random coincidences. I am not a cheater, but I have no evidence that I did not cheat. I just love solving contests, I don't even have a suggestion on how to fix the random match situation. Just sad :(
Rating: 1900
Hope removing cheaters will not reduce my rating :laugh:
Generally speaking, removing cheaters will increase other people's rating.
Though it is what happens often, it is not so obvious for me why it is the case.
Say cheaters had a negative delta, then on average their removal should decrease everyone else's rating.
I would assume that on average cheaters like anyone else have neutral delta and so their removal should also be rating-neutral (on average)
It is much likely that cheaters have positive delta simply because they have cheated and therefore could solve more than they normally would.
So, if a negative delta seems inevitable during the round, would tricking MikeMirzayanov to believe you're a cheater help you avoid this negative delta~ ha~
So. With cheaters being removed my rating decreased by 1 )
sad story ;w;
editorial for Traditional Chinese, I will ask aquamoon to update it to the announcement tomorrow. https://hackmd.io/nSTr3Ky4SyWNyvatJOXefw?view
It is my regret that I did not attend
D is really nice, but I wonder what's an issue with using just $$$n=2$$$. The conditions seem pretty contrived to me.
I'm the author of question d, and dannyboy has suggested the same thing, but I feel like discovering what multiple arrays have in common would make the question more interesting, just a personal opinion.
This round changed my impression to chinese round.
If F is not an oeis problem or make a subtask for n^2, it will be better.
How can I recieve the prize in TON?
We got a response and mike will post a blog on how to get the bonus.
So how could we receive the prize sponsored by TON?
We got a response and mike will post a blog on how to get the bonus.
What a great round!
I must say that problem D was terrific. Thanks for the round.
Could someone explain to me the intuition behind
mx - mn > 2 * xin B?The way I solved the problem is that I checked if the intervals of
[a_i - x, a_i + x]had overlap. If yes, update interval to intersection, else use new interval of currenta_iand increment counter. This passed.However, everyone seemed to solve the problem using the inequality
mx - mn > 2 * x. I understand how this comes from manipulatingabs(v - a_i) <= x. However, I do not understand it intuitively. Like, how does that work practically? How is double the value of x and the difference betweenmax(a_i)andmin(a_i)related in such a way to solve this problem? Like beyond the maths of it and rather intuitively.It is actually pretty much the same thing you did. Instead of looking at "how long will my $$$2x$$$-long intervals ('intervals of
[a_i - x, a_i + x]' as you call them) overlap" this looks at "How long can I place new points, such that a $$$2x$$$ Interval still can overlap all of them".Attention!
Your solution 166365821 for the problem 1704C significantly coincides with solutions ruimina/166361635, xxh1999/166365112, siganai/166365821, shobonvip/166366942, OpKos/166367243, bharat007/166373462, Aksnov/166374356. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I received these messages, but I did not cheated. I think it is a false detection of the fast input code. Fast input code is published on https://gist.github.com/ShubhamKJha/f16f5eb7e6da41da5f4b95d004b55d6e
I received these messages too. And I agree with you.
The logic of this problem is very simple. Our logic in the main function is similar, but there are still differences in our code. Fastio is commonly used in Python for fast reading and writing. I use it in every problem.
I'm on that list, and received the same message. I agree with you too.
If I use Python/Pypy without FastIO, I'll often get TLE. Once I had failed system tests with TLE due to I/O slowness, and since then I've always used it.
I received the same message, the only similarities i can see between our solutions is that we all use FastIO for Python, which was clearly published before the competition. I don't know if it triggers those false alarms regularly, but maybe FastIO should be whitelisted from the cheat detection system.
I received these messages too. I agree with you guys. I've been using FastIO for a long time, so do other people I think. It seems the main function part of our solutions are significantly different.
Thanks for the contributors of this contest. I become an Expert!
Why is the Simplified Chinese statement machine translated?
Why do you think so? This is manually translated by me and kuangbin, aquamoon, maybe the quality is not very high, but we spent a lot of time.If your message is said without any evidence, it will only lead to more and more Chinese round authors giving up on making Chinese statement, because it is a thankless task.
I am very sorry if my comment is offensive,but some part of that is quite weird.
Can you give some examples? Let's improve it. (I think we all translate very seriously)
Like the fourth line in "Input" of D,the sentence does not make sense.
This question was not translated by me, but I looked at the place you mentioned, and there is indeed a problem. We will review all statements and then update it, it may take some time, thank you for your feedback.
I reviewed the entire statement with aquamoon and temporarily updated a version. Sorry for the late update, because I'm not a student, I have work to do, and my sister aquamoon has been busy lately. I'm asking izlyforever and CoupDeGrace to review it again, we should have another update over the weekend. Then, when I reviewed it, I found that the quality of the translation was really poor, no wonder it was suspected of being a machine translation, and I am very sorry for that. If you find any problems, please give feedback in time, and we will change it until almost everyone is satisfied.(UPD: We updated the version reviewed by izlyforever and CoupDeGrace.)
Hi,
Out of curiosity, when will the problem ratings for these problems be updated in the problemset? Some of the more recent contests have their problem ratings assigned already (like the Division 3 round and the Educational round) but this set is missing them.
Thanks!
I spoke to the coordinator and it has now been updated.
Very nice problems, thanks！
It seems that the statement in Chinese has broken. Would you mind updating the statements, if possible? Or if it's just my own problems, could you show me how to operate it appropriately？
Nope, no damage, I tried it. Please try the following steps: 1. Download it. 2. Check whether the extension name of the file is mhtml (note that if the operating system is set to hide the known extension name, please set it to display the known extension name) 3. Open with edge.