### AquaMoon's blog

By AquaMoon, 7 months ago,

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, Heltion, ODT, Yakumo_Ran, farmerj, flowerletter, 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:

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

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!

• +1308

 » 6 months ago, # |   +48 Good luck for everyone!!!
•  » » 6 months ago, # ^ |   0 I agree
•  » » » 6 months ago, # ^ |   0 Let's try today. I wish you all good luck and the best success.
•  » » 6 months ago, # ^ |   +3 I hope everyone enjoys this competition.
•  » » 6 months ago, # ^ | ← Rev. 2 →   -29 Have a good mood!
•  » » 6 months ago, # ^ | ← Rev. 7 →   -26 good luck
•  » » 6 months ago, # ^ |   +2 cool
 » 6 months ago, # |   +5 cooooooool
•  » » 6 months ago, # ^ |   +6 hope it will be more friendly to newbie
•  » » » 6 months ago, # ^ |   +7 Orz! I believe you will get a big suprise o(*^w^*)o (
•  » » » » 6 months ago, # ^ |   +1 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 CodeTON2: AquaMoon's Blessing on This Wonderful World!
•  » » » » » 6 months ago, # ^ |   +2 Wow! Thank you! I believe you will be an excellent programmer! Keeping your original dreams and interest is wonderful ๑(≧▽≦)✧
•  » » » » » 6 months ago, # ^ |   +6 How to be a last-minute tester?
 » 6 months ago, # |   +27 I hope it is not Mathforces again!
•  » » 6 months ago, # ^ |   +19 Don't worry. Wish you good luck! (●'◡'●)
•  » » » 6 months ago, # ^ |   0 Thanks :)
•  » » » 6 months ago, # ^ |   -43 WTF is this contest, are u serious ???
•  » » 6 months ago, # ^ |   +8 I like MathForces Hehe
•  » » » 6 months ago, # ^ |   +4 lol seems it's a controversial topic, I see the below hope for Mathforces comment even has more upvotes than mine
 » 6 months ago, # |   +27 I am SUPER excited for this round!!!!!!!!!
•  » » 6 months ago, # ^ |   +17 Good luck! ヾ(≧▽≦*)o
 » 6 months ago, # |   +9 please no math
 » 6 months ago, # |   -31 Math Round!!
•  » » 6 months ago, # ^ | ← Rev. 2 →   -17 Meme
 » 6 months ago, # |   0 Best of luck！
•  » » 6 months ago, # ^ |   +6 Gook luck! I believe you can do it! (❁´◡❁)
 » 6 months ago, # |   +19 So many nice people in the helper list, this competition will be great.
•  » » 6 months ago, # ^ |   +10 Thanks for your support! Wish you good luck! =❁ω❁=
 » 6 months ago, # |   +38 the previous contest of AquaMoon is too hard..hope this round can be a normal round.
 » 6 months ago, # |   +5 Since Yakumo_Ran is (again) a problemsetter, will there be Touhou statements?
•  » » 6 months ago, # ^ |   +46 I wonder if Doremy's IQ can handle this contest
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Maybe Cirno couldn't \xox/
•  » » 6 months ago, # ^ |   +6 Not this time, but we may continue to work together in the future, so maybe the next one will.
•  » » 6 months ago, # ^ |   +15 Nope, but there'll be many Cirno_9baka problems :)
•  » » » 6 months ago, # ^ |   0 blue meow come and kiss
 » 6 months ago, # |   +12 As a tester, good luck to everyone!
 » 6 months ago, # |   0 Good luck!
 » 6 months ago, # |   0 hope this round will be interesting
•  » » 6 months ago, # ^ |   +3 Of course. Good luck and enjoy yourself! (●'◡'●)
 » 6 months ago, # |   0 Yay codeton
 » 6 months ago, # |   +16 4 weeks ago
•  » » 6 months ago, # ^ |   +8 Will answer later
 » 6 months ago, # |   +97 As a tester, I think some of the problems are very interesting.Hope all of you will enjoy it!
•  » » 6 months ago, # ^ | ← Rev. 2 →   -93 A really good round!
•  » » » 6 months ago, # ^ |   -93 I agree with you!
•  » » 6 months ago, # ^ |   +190 this some of gives more trust than usual all
 » 6 months ago, # |   +14 Super data structures round?
•  » » 6 months ago, # ^ |   +2 No.
 » 6 months ago, # |   +6 Is AquaMoon a girl?
•  » » 6 months ago, # ^ |   +24 Of course she is!
•  » » 6 months ago, # ^ |   +12 Suiseiseki is one of my best friends, you can trust him. No doubt I am a girl ~ (☆▽☆)
 » 6 months ago, # | ← Rev. 2 →   +41 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)
 » 6 months ago, # |   +6 Why is spaghetti.code shown two times in the registrants page with a red highlighted number?
 » 6 months ago, # |   +22 What's the prize distribution?
•  » » 6 months ago, # ^ |   +29 We will update it later. Now it is still mysterious to stimulate your interest! (≧▽≦)
•  » » » 6 months ago, # ^ | ← Rev. 3 →   -32 Amazing contest, I really enjoyed it!!
 » 6 months ago, # |   +51 Cute AquaMoon's cute round with cute problems!Hope everyone enjoy it :)
•  » » 6 months ago, # ^ |   +26 Cute Yakumo_Ran ! ☆w☆
 » 6 months ago, # |   +32 Can't help but notice Aquamoon trying too hard to be cute in every comment and blog-post.No offence o(*^w^*)o (●'◡'●) ヾ(≧▽≦*)o (❁´◡❁)...
•  » » 6 months ago, # ^ |   +5 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.
•  » » 6 months ago, # ^ |   0 Cause she is cute. Moe moe kyun
 » 6 months ago, # |   +29 I hope it is Mathforces! 0w0
 » 6 months ago, # |   0 so many people!
 » 6 months ago, # |   +10 I'm too curious to see your face!
•  » » 6 months ago, # ^ |   +65 Just imagine a cute girl! ☆(≧▽≦)☆
•  » » » 6 months ago, # ^ |   +33 It's been proved for me that imagination is never close to the reality ^_________^
 » 6 months ago, # |   +20 WOW!!So many testers in this round XD
 » 6 months ago, # |   +2 AquaMoon orz ❤❤
 » 6 months ago, # | ← Rev. 2 →   +15 Are u really a cute girl? Don't dig traps for me. ;-;
•  » » 6 months ago, # ^ |   +64 Yes, I promise! o(> ω <)o
•  » » 6 months ago, # ^ |   +10 I can guarantee that because I am one of the writers, you can trust me.
•  » » » 6 months ago, # ^ |   0 I have been bamboozled so hard
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 so hard I really had to scroll up to check
•  » » » » 6 months ago, # ^ |   +3 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.
•  » » » » » 6 months ago, # ^ |   +3 ok but afaik alts are illegal? intensive thinking
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 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
 » 6 months ago, # |   0 Good luck for everyone! :D
 » 6 months ago, # |   0 Someone encourage me to participate please I only lose my rate *_*
•  » » 6 months ago, # ^ |   +5 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.
•  » » » 6 months ago, # ^ |   +3 Thx bro i won't give up
•  » » 6 months ago, # ^ |   0 just ignore your rate and only focus in the problems and then the rate will become easily(✿◠‿◠)
•  » » » 6 months ago, # ^ |   0 Thank you I will try to get A B C ^_^ Egypt is the mother of world ^_^
•  » » » » 6 months ago, # ^ |   0 And Syria is my second country ❤(^◕.◕^)
 » 6 months ago, # |   0 I hope it will be a good round.
 » 6 months ago, # |   +27 We hope you will enjoy this round >_<
 » 6 months ago, # |   +3 I think it is gonna be a very creative and unique round. Hope I can reach BLUE thru it though a bit worried...
 » 6 months ago, # |   0 Note the unusual timing ...
 » 6 months ago, # |   0 "after college entrance examination".You mean gaokao in China? In India we have JEE. Did all the authors get into tsinghua university?
•  » » 6 months ago, # ^ |   0 cirno_9baka went to Tsinghua University.
 » 6 months ago, # |   0 Chinese editorial! That's great!
 » 6 months ago, # |   0 Good luck and have fun!!
 » 6 months ago, # |   0 kinda DS round
 » 6 months ago, # |   0 I will never take part in div1+div2,because I'm bad(
 » 6 months ago, # |   +54 My nightmare of Round #732... Now the problemsetters come back again!
 » 6 months ago, # |   0 Good luck! but I am not skilled in math problems :(
 » 6 months ago, # |   +22 As a tester,wish you good luck and enjoy the contest!
 » 6 months ago, # |   0 Is this contest rated for everyone?
•  » » 6 months ago, # ^ |   0 Yes.
 » 6 months ago, # |   -23 Really enjoyed Round 732 <3
 » 6 months ago, # |   -7 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!
•  » » 6 months ago, # ^ |   0 hurray!
•  » » 6 months ago, # ^ |   +8 According to the comment, is it true that Sparky_Master_WCH1226 and other "Bostwana" users are actually from HK?
•  » » » 6 months ago, # ^ |   -42 Sparky_Master_WCH1226 is from HK, but I don't know for others.
 » 6 months ago, # |   +8 where is the score distribution ?
•  » » 6 months ago, # ^ |   0 It will be updated later. (●'◡'●)
 » 6 months ago, # |   +13 Chinese statements! Cool!
•  » » 6 months ago, # ^ |   +16 Chinese statements and tutorials will be updated after the contest. (๑•ᴗ•๑)
 » 6 months ago, # |   0 Good luck for everyone XD
 » 6 months ago, # |   0 Cool Round Hope i will able to solve 1++ problems in the contest Good luck everyone :D
 » 6 months ago, # |   +13 Everyone should have a dream, and I hope I can reach 1400 points through this round.
 » 6 months ago, # |   -16 Fun factAll persons will get in total 10240 TON.
 » 6 months ago, # |   +3 what is ton
•  » » 6 months ago, # ^ |   0 it's explained in the announcement
 » 6 months ago, # |   +57 Codeforces users when they see a problemsetter who is actually a girl:
•  » » 6 months ago, # ^ |   -26 Not everyone is like youhttps://indianmemetemplates.com/wp-content/uploads/women.jpg
 » 6 months ago, # |   +26 Why was I marked as a tester of this round? I haven't solve it. Will Can I take part in this round?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 I invited you, maybe you forgot.Thank you so much for taking our test! You can ask me on discord for specific things.
•  » » » 6 months ago, # ^ |   +57 Ohh! I checked it one more time and i really tested your round few month ago. Sorry for this fake message :D
•  » » 6 months ago, # ^ |   +25 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
•  » » » 6 months ago, # ^ |   +23 Sorry for fake message :p
 » 6 months ago, # |   +2 Hope it will not be mathforces again
•  » » 6 months ago, # ^ |   0 It won't be. Problems will be as cute as AquaMoon
•  » » » 6 months ago, # ^ |   +8 Thank you ~ (๑•ᴗ•๑)
 » 6 months ago, # |   0 I really hope it's not Mathforces with Mathrounds.(@_@)
 » 6 months ago, # |   -19 I am creating a website named DATEFORCES. It is like dating site of codeforces. It is still in progress but I thought this would be a good time to announce. here is the github link
 » 6 months ago, # |   +4 CUTEFORCES
 » 6 months ago, # |   0 Good luck to myself and good luck to everyone in the rankings!
 » 6 months ago, # |   -70 I wish I could get rank 1 in this contest and defeat tourist too and impress AquaMoon
•  » » 6 months ago, # ^ |   +63 I can understand wanting to win first place, but I don't understand the point of impressing aquamoon, she has a boyfriend, good luck.
•  » » 6 months ago, # ^ |   +17 did you seriously make an account just to simp for AquaMoon ._.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +5 Sorry, I noticed that your message was not a reply to me, but I can't delete it, please ignore it.
 » 6 months ago, # |   0 good luck everyone!!! hope you get some prizes
 » 6 months ago, # |   0 what is div1 +div 2??i mean what will be the difficulty of questions
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 like global round.. check this
 » 6 months ago, # |   +4 8 prblms in 2.5 hrs . Hmm seems like Div3 level i guess ??
 » 6 months ago, # |   +2 Good luck
 » 6 months ago, # | ← Rev. 2 →   0 It's a good job
 » 6 months ago, # |   0 I hope there is not too large gap of difficulty between any adjacent problems.
•  » » 6 months ago, # ^ |   0 The difficulty gap between the problems is at most $998244353$....=❁ω❁=
•  » » 6 months ago, # ^ |   +62 What ToroTN wants: A:2400, B:2500, C:2600, D:2700, E:2800, F:2900, G: 3000, H: 3100 Yep that seems legit.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 I should say not too large and not too small. Lmao.
 » 6 months ago, # |   +21 When will the scoring distribution be announced?
 » 6 months ago, # |   0 If somebody won't take their prizes, will it pass to the next ones?
•  » » 6 months ago, # ^ |   0 Also thanks for that valuable prizes.
 » 6 months ago, # |   +21 I got a feeling that the problemset is bound to be nice, given the grand problemsetter & tester team.
 » 6 months ago, # |   +7 Hoping for a balance round!!
 » 6 months ago, # |   +10 Hope I will reach CM after this round
 » 6 months ago, # |   +4 Good Luck EveryOne!
 » 6 months ago, # |   0 Time penalty or score?
 » 6 months ago, # | ← Rev. 2 →   -11
 » 6 months ago, # |   +4 So will the score distribution be announced?
•  » » 6 months ago, # ^ |   0 Updated. (●'◡'●)
•  » » » 6 months ago, # ^ |   +5 Thanks!
 » 6 months ago, # |   +6 Second "note the unusual start time" comment.
 » 6 months ago, # |   -8 I'm so happy to be able to compete with the big boys again!
 » 6 months ago, # |   0 Finally today the Great Battle between the top 3
 » 6 months ago, # |   0 giving a CF rated contest after almost 3 months . lets relive those days again
 » 6 months ago, # |   0 Good luck for everyone!
 » 6 months ago, # |   +25 dang it, I think tourist will be dethroned today
•  » » 6 months ago, # ^ |   +15 no
•  » » 6 months ago, # ^ |   +27 oh damn last second NEVERMIND!!!! LET'S GOOOOO
•  » » 6 months ago, # ^ |   0 ups...
 » 6 months ago, # |   +98 Who the fuck wrote problem D's statement?
•  » » 6 months ago, # ^ |   +85 What was wrong with it? It was clear to me
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   +8 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???
•  » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » 6 months ago, # ^ |   +8 "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
•  » » » » » » » 6 months ago, # ^ |   0 lol, Okay then how come this passes 166396472That's how I understood the problem too but I wasn't able to solve it until I made that assumption.
•  » » » » » » » » 6 months ago, # ^ |   +8 It passes, because it is a correct solution even without assuming your false assumption
•  » » » » » » » » » 6 months ago, # ^ |   +8 OHHHHHHHHHHH, okay lol my bad just noticed.
•  » » 6 months ago, # ^ |   +16 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;
 » 6 months ago, # |   +55 02:29:15, wow!
 » 6 months ago, # |   0 How to solve $E$?
•  » » 6 months ago, # ^ |   +5 How to fix Wrong answer on pretest 5 in $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. :/
•  » » » 6 months ago, # ^ |   0 You should terminate if there is nothing left I think.
•  » » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 How do you calculate the amount of steps in which the sink won't output?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » » » 6 months ago, # ^ |   0 Take a look at Ticket 15961 from CF Stress for a counter example.
•  » » » » » » 6 months ago, # ^ |   0 Oh wow, the case $a_i=0$ for all $i$ was my mistake. Had to change a $0$ to a $-1$. That is disheartening.
 » 6 months ago, # |   +25 Tourist with the CLUTCH SOLVE to beat Jiangly!!!!
 » 6 months ago, # |   +3 Hints for problem D?
•  » » 6 months ago, # ^ |   +30 Notice, that the first operation doesn't change sum of prefix sums and the second one decreases it by 1.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +5 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
•  » » 6 months ago, # ^ |   +3 hintprefix sums
 » 6 months ago, # |   +29 Tourist nailed it at the last minute and came on top! What a competition!
 » 6 months ago, # |   +46 I tried D for 2 hrs and was not able to solve itAnd tourist managed to read, think, code and submit it in just 3 mins !!!!!!How???
•  » » 6 months ago, # ^ | ← Rev. 2 →   +23 $\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.
•  » » 6 months ago, # ^ |   +4 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.
•  » » » 6 months ago, # ^ |   0 $+$ Lot of experience and practice.
•  » » » » 6 months ago, # ^ |   0 right
•  » » 6 months ago, # ^ |   +35 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
 » 6 months ago, # |   +43 tourist's last minute submission. Damnnnn...
•  » » 6 months ago, # ^ |   0 tueeeeeeeeee
 » 6 months ago, # |   +117 When I thought that jiangly will finally reach top 1:Then this happened:dramatic.
•  » » 6 months ago, # ^ |   +24 That was one of the finest buzzer beater !
•  » » 6 months ago, # ^ |   0 What's that delta predictor extension you are using?
•  » » » 6 months ago, # ^ |   +5 Carrot.
•  » » 6 months ago, # ^ |   0 I also think jiangly will become the new King until the last minute :)
 » 6 months ago, # |   0 nice round, but disgusting problem D :(
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   +38 It's not strict, you forgot to check vis state in DFS.
•  » » » 6 months ago, # ^ |   +39 fuc******** cant believe missed AC by 1 line
 » 6 months ago, # |   +17 1 min before the end of the contest: Jiangly will beat tourist! After the contest: what? tourist solved G at 02:29:15?
 » 6 months ago, # |   +14 wowww..! tourist's last minute clutch!!
 » 6 months ago, # |   -63 Really, a very bad round too hard problems
 » 6 months ago, # |   +20 It's dramatic that tourist overtook jiangly 1min before the contest ends.
•  » » 6 months ago, # ^ |   +14 Plot armor irl!
 » 6 months ago, # |   +61 Thanks, OEIS!
•  » » 6 months ago, # ^ |   +11 in which problem?
•  » » » 6 months ago, # ^ |   +12 F
•  » » » 6 months ago, # ^ |   +24
 » 6 months ago, # |   +41 F is much too weird. Maybe it's better to set $n\le 1000$ for those who doesn't know the conclusion?
•  » » 6 months ago, # ^ |   +15 Please stop making OEIS problems.
 » 6 months ago, # |   -8 Problem E can __int128 hold all variables?
•  » » 6 months ago, # ^ | ← Rev. 3 →   +4 Of course not , the maximum variable can be about $O(2^{n/2})$ .
•  » » » 6 months ago, # ^ |   0 can java BigInteger or Python pass it?
•  » » » » 6 months ago, # ^ |   +5 No. May be It can be calculated , it will get TLE .
•  » » » » » 6 months ago, # ^ |   +11 My bigint solution in C++ passed system tests.
•  » » » » » » 6 months ago, # ^ |   0 Cool. So it seems Java BigInt can solve it too.
•  » » » 6 months ago, # ^ |   0 how's that O(2^(n/2)) calculated? can u prove it?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +30 Say if you had a graph like thisInitially, 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}$.
•  » » » » » 6 months ago, # ^ |   +3 Thank you! Learned a lot from u.
•  » » 6 months ago, # ^ |   0 Why would you want to do that if we are asked to compute modulo an int?
•  » » » 6 months ago, # ^ |   0 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).
•  » » » » 6 months ago, # ^ |   +3 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.
•  » » » » » 6 months ago, # ^ |   0 Cool. So mine will be ok if I replace int128 to some BigInt-like struct. Thank you.
 » 6 months ago, # |   +3 Whoever came up with problem D is an artist. Best problem of this year
•  » » 6 months ago, # ^ |   +87 I await the punchline
 » 6 months ago, # |   +27 Fight between tourist and jiangly is always legendary and dramatic for 1st position !
 » 6 months ago, # |   +6 I live to see Tourist vs Jiangly.
 » 6 months ago, # |   +36 Sorry, I hate this round very much.
•  » » 6 months ago, # ^ |   0 (≧▽≦)
 » 6 months ago, # |   0 Meanwhile tourist in parallel universe:tourist : "Damn! why problem A is so hard?"
 » 6 months ago, # | ← Rev. 2 →   +10 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?
•  » » 6 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +28 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$.
•  » » » 6 months ago, # ^ |   +20 Yep, that's a nice generalization of "match strings with questionmarks", that is also computed with $\sum\limits_{i=0}^{m-1} a_{i+j} b_i (a_{i+j}-b_i)^2$
•  » » 6 months ago, # ^ | ← Rev. 2 →   +8 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.
 » 6 months ago, # |   -8 Anime girl images please
 » 6 months ago, # |   +8 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....
 » 6 months ago, # |   +6 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.
 » 6 months ago, # |   +8 How to solve 1704H1 - Игра ИИ (простая версия)?
•  » » 6 months ago, # ^ | ← Rev. 3 →   +18 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.
•  » » » 6 months ago, # ^ |   0 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)
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » » 6 months ago, # ^ |   0 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 $(a_1, b_1), \ldots, (a_k, b_k)$then if we denote the pair for the root as $(A, B)$then $A = \sum_{i=1}^{k} i \cdot \sum_{|B|=i} \prod_{j \in B} b_j \prod_{j \not\in B} a_j$and $B = A + a_1 \cdot \ldots a_k$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.
•  » » » » » 6 months ago, # ^ |   +8 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
•  » » » » » » 6 months ago, # ^ |   +10 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.
 » 6 months ago, # | ← Rev. 2 →   +84 (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
 » 6 months ago, # |   +14 How to solve H1?
•  » » 6 months ago, # ^ | ← Rev. 2 →   -120 I'm Sorry bro, i didn't mean to make fun at you i apologize to you i was just joking with you my comment was fun at me not you my level is low i was just kidding at my self i hope to reach your level one day, at last please forgive me bro :)
•  » » » 6 months ago, # ^ |   -9 Your submissions say otherwise... Also, if it was easy, you would be able to explain how to solve it instead of making fun of Temotoloraia
 » 6 months ago, # |   +24 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
•  » » 6 months ago, # ^ |   -43 Yes you are right bro Can you tell me how to be expert soon ?
 » 6 months ago, # |   0 I think I solved problem C 10 mins after the contest ended, what a pitty
 » 6 months ago, # |   0 How do you solve problem A efficiently ? I tried recursive memoized approach, got TLE.My Submission
•  » » 6 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ |   -10 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).
•  » » » 6 months ago, # ^ |   +5 I'd really appreciate if people told me why did they downvote my answer. This approach works (166352851).
 » 6 months ago, # |   +81 Why there wasn't any announcement that the statement for E changed? I was debugging for an hour just because of the third example. :(
 » 6 months ago, # |   +6 Finished E after contest (at least I think finished)Dropping out of violet because of the wrong submission for A...
•  » » 6 months ago, # ^ |   +6 No worries, you will regain your rating for sure.
 » 6 months ago, # |   0 How to solve E?
•  » » 6 months ago, # ^ |   0 My idea is pretty much optimized simulationCannot check whether it is right until systests finish though
 » 6 months ago, # |   +23 For the guys who solved D. How did you come up with the prefix sum observation? Had you solved similar problems before?
•  » » 6 months ago, # ^ |   0 I thought about prefix sum as well but my final solution does not have it
•  » » 6 months ago, # ^ | ← Rev. 2 →   +42 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.
•  » » » 6 months ago, # ^ |   +9 Same hereI thought that it should be possible use some array with only two nonzero elementsThen thought where should those elements beThen after experiments and thoughts about centers of mass ended up with these formulae
•  » » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   +8 It can also be interpreted as the position of the center of mass (multiplied by the mass).
•  » » » 6 months ago, # ^ |   0 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?
•  » » » » 6 months ago, # ^ |   +14 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?
•  » » » » » 6 months ago, # ^ |   0 Hmm, Clear now, Thanks.
•  » » 6 months ago, # ^ |   +13 It's a common technique. When you have operation like adding or subtracting, see what's the effect on the prefix sum/difference array.
•  » » » 6 months ago, # ^ |   0 I was thinking in terms of parity of the difference array but couldn't get anywhere.
•  » » 6 months ago, # ^ |   0 Its common to take prefix/suffix sums when we consider operations on adjacent indices. Another recent example problem: link
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 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.
 » 6 months ago, # |   +5 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.
•  » » 6 months ago, # ^ |   0 I guess we can just take the last vertices without outgoing edges, then we don't need to think about maximums
 » 6 months ago, # | ← Rev. 2 →   -79 .
•  » » 6 months ago, # ^ | ← Rev. 3 →   -43 .
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +20 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:)
 » 6 months ago, # |   -6 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.
 » 6 months ago, # |   0 Me: Reads statement of D. Immediately takes prefix sums. Notices operation $2$ is just operation $1$ with extra subtraction. "Hmm...how can I possibly tell these two operations apart?" FML
 » 6 months ago, # |   0 does eng Tutorial of G,H gonna be available later or only Chinese are given?
•  » » 6 months ago, # ^ |   0 They will be later The editorials of problem G and H will be adding soon. (from editorial)
 » 6 months ago, # |   +3 Wow! Now tourist has a one kiloTON of crypto!
 » 6 months ago, # |   +21 Weak tests in E, why are solutions that just simulated using big integers passing?
 » 6 months ago, # |   +27 As a tester, I'm sorry for not realizing that the main test for E is weak :(I've submitted an uphack just now.
•  » » 6 months ago, # ^ |   -8 So will have a re-run?
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # | ← Rev. 3 →   +7 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?
•  » » 6 months ago, # ^ |   +13 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
•  » » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   +79 To not keep you waiting, the ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!
•  » » 6 months ago, # ^ |   +13 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 :(
 » 6 months ago, # | ← Rev. 2 →   +2 Rating: 1900Hope removing cheaters will not reduce my rating :laugh:
•  » » 6 months ago, # ^ |   0 Generally speaking, removing cheaters will increase other people's rating.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +20 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)
•  » » » » 6 months ago, # ^ |   0 It is much likely that cheaters have positive delta simply because they have cheated and therefore could solve more than they normally would.
•  » » » » 6 months ago, # ^ |   0 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~
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +53 So. With cheaters being removed my rating decreased by 1 )
•  » » » » 6 months ago, # ^ |   0 sad story ;w;
 » 6 months ago, # |   +13 editorial for Traditional Chinese, I will ask aquamoon to update it to the announcement tomorrow. https://hackmd.io/nSTr3Ky4SyWNyvatJOXefw?view
 » 6 months ago, # |   0 It is my regret that I did not attend
 » 6 months ago, # |   +16 D is really nice, but I wonder what's an issue with using just $n=2$. The conditions seem pretty contrived to me.
•  » » 6 months ago, # ^ |   +21 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.
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   +68 How can I recieve the prize in TON?
•  » » 6 months ago, #