### Kuroni's blog

By Kuroni, history, 4 weeks ago,

"Love" is a violent word.
"I love that about you..." Doesn't that just mean "If that changed, I wouldn't love you anymore?"
"Love" is a word that binds you.
— Touko Nanami —

Hi Codeforces!

Ari and I are pleased to invite you to participate in Codeforces Round #715 (Div. 1) and Codeforces Round #715 (Div. 2), which will be held at 16.04.2021 17:35 (Московское время). Each division will have 6 problems and 2 hours and 15 minutes to solve them.

Big thanks to the following people:

The round will be themed around Yagate Kimi ni Naru, which is a romantic anime/manga series. If you haven't picked up the series yet, I highly recommend you to do so after the round ;)

Please do read all of the problems, stay hydrated during the round, and solve as many as you can! Good luck have fun to everyone!

Here are the scoring distributions:

• Div. 2: 500 — 1000 — 1500 — 2250 — 2500 — 3000
• Div. 1: 750 — 1000 — 1500 — 2250 — 2250 — 4000

UPD1: The round has concluded! Congratulations to the winners from both divisions:

• Div. 1:
• Div. 2:
1. wannahavealife (solved all problems!)
2. traxex2
3. _su1sen
4. I_love_Ilya_Krasnov
5. tsugu

UPD2: Editorial is up!

Thanks to everyone for participating in this contest, this has been a wild ride from start to finish. See you all next time!

• +1371

 » 4 weeks ago, # |   +537 As a tester, they shoved weeb propaganda down my throat. I recommend participation.
•  » » 4 weeks ago, # ^ |   -110 So, you are on our side now , right? We did it guys, we have the power of god, anime and now 1-gon on our side.
 » 4 weeks ago, # |   +144 As a tester, the problems are very elegant and you should participate in the round.
 » 4 weeks ago, # |   +164 anime propaganda? i'll skip.
•  » » 4 weeks ago, # ^ |   +539 Round rotavirus skips -> good round
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +68 are the rounds, in which rotavirus participates, bad?
•  » » » » 4 weeks ago, # ^ |   +18 you've participated in his rounds so ...
•  » » » » 4 weeks ago, # ^ |   +30 The implication is one-directional: there exist good rounds you participate in. But if a round is bad, then you necessarily participate in it.
•  » » » » » 4 weeks ago, # ^ |   +24 But if a round is bad, then you necessarily participate in it. I'll participate in this one then
•  » » » » » 4 weeks ago, # ^ |   0 nah this is not interesting.
•  » » » » » 4 weeks ago, # ^ |   +29 contrapositive geniosity
•  » » 4 weeks ago, # ^ |   -40 Anime is shit, change my opinion!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +15 my waifu for aiur
•  » » » » 4 weeks ago, # ^ |   0 u high bruh?
•  » » 4 weeks ago, # ^ |   +10 this was a wise decision....but XD
•  » » » 4 weeks ago, # ^ |   0 i totally agree
 » 4 weeks ago, # | ← Rev. 2 →   -151 Wtf.Yagate Kimi ni Naru is a Shoujo Ai Anime. Shoujo ai is something related to yuri and yuri means Lesbian.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +51 So what? Its a piece of art.Change my mind.
•  » » » 4 weeks ago, # ^ |   +58 I won't let anyone change your mind
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 So? It's art, bro
•  » » 4 weeks ago, # ^ |   +29 Even better
•  » » » 4 weeks ago, # ^ |   +11 I see you're a fellow capybara enjoyer
 » 4 weeks ago, # |   +70 Now this is called a complete round, This round gives you anime recommendation(Yagate Kimi ni Naru) for dealing with post contest depression or celebration.
 » 4 weeks ago, # |   +95 These bleeding weebs lmao
 » 4 weeks ago, # |   +73 i never expected a timeline where bloom into you is getting a competitive programming adaptation
•  » » 4 weeks ago, # ^ |   +215 Neither did I so I made it myself.
•  » » » 4 weeks ago, # ^ |   0 Adapt a "Kimi no Na wa" then, next time. Seems you're a fan of love.
•  » » 4 weeks ago, # ^ |   0 completely shocked when I entered the main page, haha
 » 4 weeks ago, # |   +29 Looks like anime will soon takeover the world :D
•  » » 4 weeks ago, # ^ |   -13 This post shows ,it already have
 » 4 weeks ago, # |   +19 I like this round already
 » 4 weeks ago, # |   +56 See the series "after the round". Given the round is based on this series, isn't there high chances that not that great memory would be associated with this series after the round is over? Kuroni
•  » » 4 weeks ago, # ^ |   +130 The problems will be very good so no bad memories will be associated :sunglasses:
 » 4 weeks ago, # |   +35 I confirm that Yagate Kimi in Naru is a wonderful lesbian/yuri Japen comic, I highly recommend it too :(
 » 4 weeks ago, # |   0 Thanks for the early score distribution : )
•  » » 4 weeks ago, # ^ |   0 nice contest~
 » 4 weeks ago, # |   +50 WEEB IN!!!
•  » » 4 weeks ago, # ^ |   0 otakus also in !!!
 » 4 weeks ago, # |   +34 I think I need to code for counting the number of a's in neko_nyaaaaaaaaaaaaaaaaa
 » 4 weeks ago, # |   +49 You say weebs, but all I see are people of culture. Respect!
 » 4 weeks ago, # |   +9 Hope to perform my best till now, in this round!
 » 4 weeks ago, # |   +66 So, when are we getting a round themed around AOT?
•  » » 4 weeks ago, # ^ |   +13 What about jujutsu kaisen ?
•  » » » 4 weeks ago, # ^ |   +9 besto friendooo.....
 » 4 weeks ago, # |   +76 As a Japanese otaku, this is why I cannot retired from CF!I hope the tasks are as amazing as Yagakimi.
 » 4 weeks ago, # |   +71 Honestly saying I dont like of idea of round being theme based, I hope statements would be clear as daylight and wont involve these characters. From my side if one wants to make a round theme based simply name the problems as your fav anime/manga whatever and people will get the propoganda nothing more than that.
•  » » 4 weeks ago, # ^ |   +4
•  » » 4 weeks ago, # ^ |   -33 I don't think there is a problem with choosing a theme for their contest, if there is a part in the problem statement and that's not related to the problem, you'll notice it and you can skip that part. Furthermore, anime characters can make the problem fun and more enjoyable.
 » 4 weeks ago, # |   +42 Oh, Vietnamese authors. Good job! Keep going your contributions. I hope that one day I can write a contest. Of course, I need to be purple at least first.
•  » » 4 weeks ago, # ^ |   +74 Didn't know Ari was Vietnamese :O
•  » » » 4 weeks ago, # ^ |   +212 Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to see their nationality being called into question
•  » » » » 4 weeks ago, # ^ |   +64
•  » » » » » 4 weeks ago, # ^ |   -83 I see, people tag Ari unnecessarily after her comment
•  » » 4 weeks ago, # ^ |   +6 More like northern American authors
 » 4 weeks ago, # |   +23 I think something went wrong here. In the post, it says that the contest last 2 hours and 15 minutes. In the register page, it says that just 2 hours.
•  » » 4 weeks ago, # ^ |   +19 I believe the registration page is not updated yet. I will contact to fix the issue :)
 » 4 weeks ago, # |   +3 As a "noob" tester. This round is very "balance" and very good. Wish all the participants have a positive rating! :)
•  » » 4 weeks ago, # ^ |   -46 Imagine calling yourself a noob when you have got a privilage to test a round.such a geniosity.....
•  » » 4 weeks ago, # ^ |   0 Will I go green UwU?
 » 4 weeks ago, # | ← Rev. 2 →   0 Loved the suggestion, "stay hydrated during the round", also the quote mentioned.
•  » » 4 weeks ago, # ^ |   0 Yeah but always take care to not to take out your stress by drinking a lot, overhydration is also not good.
 » 4 weeks ago, # |   +35 .
 » 4 weeks ago, # |   0 A round with anime propaganda? I'm in.
•  » » 4 weeks ago, # ^ |   0 up
 » 4 weeks ago, # |   0 I am very excited for this codeforces round because the Problemsetters are Ari and Kuroni.
•  » » 4 weeks ago, # ^ |   0 Me too~
 » 4 weeks ago, # |   +10 im trying to understand the blog & comments but i have no clue : (
•  » » 4 weeks ago, # ^ |   +48 Normie
•  » » 4 weeks ago, # ^ |   +31 hope you don't feel the same way with problems
•  » » 4 weeks ago, # ^ |   -8 If you have no clue, then think of us:( May be an editorial over comment history be a new update:)
 » 4 weeks ago, # | ← Rev. 3 →   +14 Hope the Aquaman in me wakes up for some time during the contest instead of Aqua sama.
 » 4 weeks ago, # |   -36 sir why does contest have lessbyan cartoon theme?????
•  » » 4 weeks ago, # ^ |   +18 You should be judged by KAMI SAMA for addressing an Anime as a cartoon :D
 » 4 weeks ago, # |   +10 Being an otaku , very excited for this round. I hope we will get more episodes of these kind of round XD
 » 4 weeks ago, # |   0 Colorful testers :)
 » 4 weeks ago, # |   0 I love the quote.
 » 4 weeks ago, # |   -16 From Vietnam ưith love!
•  » » 4 weeks ago, # ^ |   -16 ưhat's up :)
 » 4 weeks ago, # |   -78 The comment is hidden because of too negative feedback, click here to view it
 » 4 weeks ago, # |   +25
 » 4 weeks ago, # |   +19 A round? I prefer two matches in Dota 2.
•  » » 4 weeks ago, # ^ |   +8 I prefer a positive delta change of > +50 in an Anime theme round XD
•  » » » 4 weeks ago, # ^ |   0 Wow According to CF predictor I got a positive Delta of +60 XD and also my Highest rating. What can be better for a Anime Fan like me :D:D
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 you definitely mean one match of Dota 2 with Techies
 » 4 weeks ago, # |   +30 I love how the scoring distribution is released so early. +1 from me. I also have another quote for you: LOVE...Actually, there is a word for that. It's love. I'm in love with her, okay? If you're looking for the word that means caring about someone beyond all rationality and wanting them to have everything they want no matter how much it destroys you, it's love. And when you love someone you just, you...you don't stop, ever. Even when people roll their eyes, and call you crazy. Even then. Especially then. You just-- you don't give up. Because if I could just give up...if I could just, you know, take the whole world's advice and-- and move on and find someone else, that wouldn't be love. That would be... that would be some other disposable thing that is not worth fighting for. But I-- that is not what this is." -Ted Mosby"
 » 4 weeks ago, # |   -35 is div 2 round rated?
 » 4 weeks ago, # | ← Rev. 2 →   +1 HAPPY ANIME DAY!!!(15th April)
 » 4 weeks ago, # |   +31 YagaKimi is brilliant. Contest setter has good taste.
 » 4 weeks ago, # |   -86 NGL, it seems this blog has less number of downvoted comments. Is this because of "LOVE"? Has the CF community become less toxic only because of the word "LOVE" and a reference to a romantic anime?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +92 Cool, it's still as toxic as always :)
 » 4 weeks ago, # |   0 Kuroni do you play Pokemon Planet? I once saw someone selling stuff in the trade chat named Kuroni and I was wondering if it was you. The anime theme of the contest further makes me think it might actually be you.
•  » » 4 weeks ago, # ^ |   +4 No I don't
 » 4 weeks ago, # | ← Rev. 2 →   0 Haven't seen this many upvotes for a contest blog in ages . This contest was great.
•  » » 4 weeks ago, # ^ |   +65 Monogon literally just held his contest...
•  » » 4 weeks ago, # ^ |   0 I think so
 » 4 weeks ago, # |   +12 Although I'm having a history exam on the next day, I can't wait to participate in this round! Hope that I could collaborate with you in future rounds Kuroni, maybe as a tester? Anyway, wish this round will goes perfectly!
 » 4 weeks ago, # | ← Rev. 2 →   -38 can't wait to participate!!
 » 4 weeks ago, # |   +30 Kuroni's stand be like Meme
 » 4 weeks ago, # |   0 A romantic contest ... I like it
•  » » 4 weeks ago, # ^ |   0 Don't judge a book by it's cover. SpoilerSame goes with Yagate Kimi ni Naru
•  » » » 4 weeks ago, # ^ |   0 I just started that anime ... Seems pretty good
 » 4 weeks ago, # |   -24 Finally a contest with Div2 B = 1000 score! No Alan Turing level mathematics I expect!
•  » » 4 weeks ago, # ^ |   -9 maybe
 » 4 weeks ago, # |   0 Hope I remain EXPERT after this contest!.
•  » » 4 weeks ago, # ^ |   0 why not
 » 4 weeks ago, # | ← Rev. 2 →   +15 Score of Div2. D is scaring me !! SpoilerD = 2250
 » 4 weeks ago, # |   +22 How many problems are common between both divisions?
•  » » 4 weeks ago, # ^ |   +21 According to the score distribution seems that Div2 D = Div1 A
•  » » » 4 weeks ago, # ^ |   0 How can it be compared from score distribution?
•  » » » » 4 weeks ago, # ^ |   0 The usual score distribution is: 500 — 1000 — 1500 — 2000 — ... in this round Div2 D = 2250 and Div1 A = 750
•  » » 4 weeks ago, # ^ |   +30 Div2 D = Div1 A
•  » » » 4 weeks ago, # ^ |   -12 ??
 » 4 weeks ago, # |   0 hlw guys plz tell me how to make a user my friend???
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 press on this star
•  » » » 4 weeks ago, # ^ |   +5 ok thnx
•  » » » 4 weeks ago, # ^ |   0 thnx
•  » » » 4 weeks ago, # ^ |   0 ok
 » 4 weeks ago, # |   +11 Hopefully I will become pupil after this contest.
•  » » 4 weeks ago, # ^ |   +9 You will man :)
•  » » 4 weeks ago, # ^ |   +5 you will~
•  » » 4 weeks ago, # ^ |   0 Don't worry I am sure it will be easy :)
 » 4 weeks ago, # |   +13 I wish i would solve atleast 3 to 4 problems in this contest ;-;
•  » » 4 weeks ago, # ^ |   +10 you can , i believe you~
 » 4 weeks ago, # |   0 A contest on Naruto also:)
•  » » 4 weeks ago, # ^ |   0 Naruto Uzumaki~
 » 4 weeks ago, # |   0 All the best every one.
 » 4 weeks ago, # |   -6 I am Sooooooooooooo Excited ❤
•  » » 4 weeks ago, # ^ |   0 me too
 » 4 weeks ago, # |   0 Dmitry cdkrot Sayutin likes this post 'cause it's propaganda for two girls to participate in SIS.
 » 4 weeks ago, # |   +3 I hope they make an Attack on Titan round when the last episode airs next year >.>
•  » » 4 weeks ago, # ^ |   +4 chapter 139 had me in tears ngl,eremika forever!!
 » 4 weeks ago, # |   -8 Have a great Rating Change :)
•  » » 4 weeks ago, # ^ |   +1 i got
•  » » » 4 weeks ago, # ^ |   0 I also got, but my rating decreased XD
 » 4 weeks ago, # | ← Rev. 2 →   +11 sdfoiSF
•  » » 4 weeks ago, # ^ |   +10 hi
 » 4 weeks ago, # |   +3 WA on pretest 5
•  » » 4 weeks ago, # ^ |   0 I can feel this comment.
•  » » » 4 weeks ago, # ^ |   0 Yeah, it's WAForces!
•  » » » » 4 weeks ago, # ^ |   0 how to share photos?very grateful to you!
 » 4 weeks ago, # |   +15 I got to say the pictures that explain the examples are lovely.
 » 4 weeks ago, # |   +4 what the heck is pretest 5 of div2C
•  » » 4 weeks ago, # ^ |   0 how to solve div2C?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I solve it using dp,i sort the distinct value of all input,then we consider the last operation we can make , neither we put the max or min value , then dp[i][j] = min(dp[i+1][j] + count[value[i]] * diff,dp[i][j-1] + count[value[i]] * diff),here is my code: dp solution
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 It is the place where green's rest.
•  » » 4 weeks ago, # ^ |   +1 try 8 1 2 4 4 5 9 9 10
•  » » » 4 weeks ago, # ^ |   0 ans?
•  » » » » 4 weeks ago, # ^ |   +1 33 (4 4 5 2 1 9 9 10)
•  » » » » » 4 weeks ago, # ^ |   0 Thanks, this is where I failed
•  » » 4 weeks ago, # ^ |   +1 Same! I simply traversed a sorted circular array n times for each i and a reverse sorted circular array. Thought it was right, but got stuck on pretest 5
 » 4 weeks ago, # |   +3 How to solve Div 1 A ( Binary Literature ) ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +14 Choose two strings which have at least $n$ zeros or ones in common (clearly at least one such pair must exist). Take $n$ of these common, then just place the remaining $2 \times n$ elements in the same relative order.
•  » » » 4 weeks ago, # ^ |   0 Oh! FU**!. Thanks.
•  » » » 4 weeks ago, # ^ |   0 Tried to did the same. No idea what went wrong ?submission link
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Out of the 3 strings, you can find a pair of strings such that both have >= n zeroes or both have >= n ones. Treat the 0s (or 1s in other case) as common subsequence. Now you can combine these 2 strings (Leaving this as an exercise).
•  » » » 4 weeks ago, # ^ |   0 My bad. Thanks.
 » 4 weeks ago, # |   +15 I feel like I have been getting better and then I fail to Div 2C? How to solve D2 C?
•  » » 4 weeks ago, # ^ |   0 DP
•  » » 4 weeks ago, # ^ |   +4 Can be solved using DP. At the end of the altered array you have two options either max(1--n) or min(1--n) for optimal ans. So at each step you have two options. Lets make a vector of all speeds in a sorted manner and solve the dp, dp(l,r) = min(dp(l+1,r), dp(l, r-1)) + v[r]-v[l]; ans = dp(0, n-1);Submission Link
•  » » 4 weeks ago, # ^ |   +2 Since it is about the differences we can need to sort a[].dp[i][j] is min cost to have runner i to j of the sorted list started in any order.dp[i][i]=0;for all i+1<=j:dp[i][j]=min(dp[i+1][j]+a[j]-a[i], dp[i][j-1]+a[j]-a[i])So, we start with any runner, and take as next the next faster or slower one.
•  » » 4 weeks ago, # ^ |   0 At each point you've to either place group of smallest elements of group of largest elements in the end (try to prove yourself).So you do a dp[l][r] on the sorted list of distinct elements and at each point decide to place either all a[l]s or all a[r]s in the end of the final list and then do l++ or r-- and continue
•  » » 4 weeks ago, # ^ |   0 Sort the speeds then compute the minimum cost to include racers with speeds si...sj. Initialize dp[i][i] = 0 for all i (cost of including single racer is 0) At each step k, dp[i][i+k] is the minimum cost of including all racers between i and i+k, which can be computed from the previous dp[i][i+(k-1)] and dp[i+1][(i+1)+(k-1)] You can actually use 1D DP because at any given k you're only using the results from k-1 before overwriting them.
•  » » » 4 weeks ago, # ^ |   +5 I was able to upsolve that, thanks.
•  » » 4 weeks ago, # ^ |   0 I solve it using dp,i sort the distinct value of all input,then we consider the last operation we can make , neither we put the max or min value , then dp[i][j] = min(dp[i+1][j] + count[value[i]] * diff,dp[i][j-1] + count[value[i]] * diff),here is my code: dp solution
 » 4 weeks ago, # |   0 Can some one please explain how to solve Div2 problem D
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +6 Suppose there are two strings $a$,$b$ such that number of zeros in $a$ and $b$ are greater than $50$%. Then we can choose string $a$ and insert number of $1$'s in string $b$ in string $a$ such that $b$ is substring of whole string.Same case when number of $1$'s in $a$ and $b$ are greater than $50$%.When both $1$ and $0$ are equal to $50$% in both $a$ and $b$ then also it can be solved with same logic.Let say $a=11111100,b=11110000$ then final string will be $111100001100$
•  » » 4 weeks ago, # ^ |   +3 Since there are 3 strings, we can always pick 2 out of them, such that either both of them have at least n times 0 or both of them have ar least n times 1. Let's call this the mode. It is 0 in the first case and 1 in the second case. Then we can create a string with n times the mode. Now we matched at least n characters from the first string, and at least n characters from the second string. We are left with n characters from the first and n characters from the second string. We can simply add them by traversing both strings to get a string of length at max 3n.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 we can prove the at least there two strings which is have at least n characters are same , '0' or '1',for any case ,we assume it is '1',we just can replace n '1' in any string with another string ' s '1',don't change the order of other characters ,we can make it;here is my code: my code
 » 4 weeks ago, # |   0 How to solve Div2B?
•  » » 4 weeks ago, # ^ |   0 Couldn't participate in the contest today. But upon reading , you just traverse through the string and check that at no point , the count of M should be greater than the count of T. then repeat the same thing , while going backwards , that is from n-1 to 0. And then just see if the count of T is 2 times the count of M. If the string satisfies all the above conditions , print yes
•  » » » 4 weeks ago, # ^ |   +1 Yes, saw some solutions. But, why does this works?
•  » » » » 4 weeks ago, # ^ |   +1 while traversing from start..for every M..there must be atleat one T before it..similarly while traversing from back
•  » » » » » 4 weeks ago, # ^ |   0 I feel dumb now.
•  » » » » 4 weeks ago, # ^ |   0 Sent you a message. Cause I am unrated , its not allowing to comment more than once in 10 mins
•  » » » » » 4 weeks ago, # ^ |   0 Thanks, I understand it now.
•  » » » » 4 weeks ago, # ^ |   0 What special about "TMT", for every M there is one T to the left and 1 T to the right. So if we check that count of Ts is twice the count of Ms and check whether each M has a T to the right and left by traversing the string both ways, we will have the answer.
•  » » 4 weeks ago, # ^ |   0 we can check two pass from left to right and from right to left,every pass ,we must make every m can get a t in it's front ,otherwise we can't make it ,by the way ,we always have the number of 'T' is two times of the number of 'M'
 » 4 weeks ago, # |   +4 Was DIV2 D much easier than DIV2 C ? It was just case analysis right ? If we have two strings with 50% 0 and 50% 1 then we are done . Or else if we have two strings with number of 0 greater than 50% then also we can combine them.I read it in last moment and found that implementation was bit difficult else it was easier than DIV2 C.
•  » » 4 weeks ago, # ^ |   +17 I feel like implementation is the biggest pain in Div2D / Div1A, took 5-10 mins to come up with the solution, 20-30 mins to code it correctly. Maybe I'm just bad at implementation.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 I think an easy implementation can be done with two pointers. Once we find pair of strings with a bit appearing $>= n$ times, iterate both string. If the bit match, append the bit to the answer and advance both pointers. Else append the bit that appears $<= n$ times, and advance its pointer.
•  » » » 4 weeks ago, # ^ |   0 agree with you,c is much easier to code
•  » » 4 weeks ago, # ^ |   +5 Read every submission from jiangly and your implementation will become CLEAN and FAST.
•  » » » 4 weeks ago, # ^ |   +3 Thanks, I will follow him. I also think that removing fear from mind that "i cannot solve D if i can't solve C" is also very important. If i would have read D well before time i would have got positive delta.
 » 4 weeks ago, # |   0 can anyone help with div2 D? Couldn't get it working during contest.
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   0 Hints: There must have 2 string where no of 0/1 in both two string >=n. approach:when any of two string no of 0/1 >=n. Then take one string fully , so other string n element already taken, so taken the rest <=n elements of the other string with some tricks which was not common. its always <=3n operation.implementation
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 how did you reach this deduction of count(either 0 or 1) being greater than n for at least 2 strings? UPD : Thanks, got it
 » 4 weeks ago, # |   0 Anyone can tell me why my solution for D/Div2 get WA?113255849
 » 4 weeks ago, # |   +10 Aw hell, I wasted so much in C. I knew the main idea right away — find unassigned connected components, if they don't form a forest then compress them into vertices and find the weight of MST there, otherwise build the tree and add min(XOR, for each unassigned edge the smallest weight of a non-MST edge that crosses it). I just didn't go for the straightforward implementation that uses $N \lt 900$ and finds those smallest weights of non-MST edges crossing all MST paths, but tried other things that I thought would be simpler and fast. Got a lot of WAs and wasted like an hour, only to implement that $O(N^2)$ in the end.
•  » » 4 weeks ago, # ^ |   +8 A simpler solution (at least in my mind) with complexity $O(m\log m)$: If $\frac{n(n-1)}{2}-m\ge n$, answer is just MST. Else, $n=O(\sqrt{m})$. Naively process will give $O(m\sqrt{m}\operatorname{dsu}(n))$, but note that only $n$ out of these $m$ edges are useful (run MST with only fixed edges, only used edges are useful). Now the complexity is $O(n^2\operatorname{dsu}(n))=O(m\operatorname{dsu}(n))$.
•  » » » 4 weeks ago, # ^ |   0 Tbh my solution is simple — build MST with $N-1$ edges, list all paths in the form $(root,v,parent(v),depth(v))$, sort them by depth = length, make a table $W_{u,v}$ for minima of weights of non-MST edges crossing paths $(u,v)$ and do $W_{par(v),v} = min(W_{par(v),v}, W_{root,v})$ for all paths.What I was going for was more like print cost of MST + min(XOR, minimum of non-MST edges), which failed, but it's not obvious to me why it failed because I tried making a simple counterexample and found out it wasn't a counterexample.
•  » » » » 4 weeks ago, # ^ |   0 The same general approach succeeded for me, although I used a different method for finding the minimum non-MST edge (just find LCA and check how many non-assigned edges are on the path to LCA). So maybe it was just a bug.
•  » » » » » 4 weeks ago, # ^ |   0 I made a multiset of weights strictly smaller than XOR, then removed weights as I was building the MST. Hard to make a mistake there, it's like 5 lines and I avoided obvious pitfalls like empty multiset or removing by value instead of by element.
•  » » » » » » 4 weeks ago, # ^ |   0 The exact approach worked for me. So the answer is MST + min(XOR, minimum of non-MST edges). Except for non-MST edges you have to check that there is at least 1 added edge ( e.g. edge not present in the original graph ) , for that I used a similar approach to the one KADR mentioned, I have LCA with binary jumping which keeps the minimum weight edge from a node to its parent in MST.
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 EDIT: Found my mistake.
•  » » » » » » » 4 weeks ago, # ^ |   -18 Sounds like your "exact approach" needs more effort than anything I tried. If you simplify DFS/DP-ing all paths into one formula and then complexify that simple formula into LCA with binary jumping, you didn't simplify...
•  » » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I meant the exact idea for solution. anyway...
•  » » » » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Regarding the "simplifying", personally I think it is better (easier) to copy paste binary jumping and use it, since you need to modify just a few lines, rather than trying to code something unusual that makes use of the specific constraints of the problem. Also, who says I am trying to simplify, I am trying to solve the problem with less code or alternatively with less effort.
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Well, writing something well-known is the right approach and the one I didn't take until near the end. However, why start with deciding for a formula, then figure out that there's an exception to that formula and you need to use some more standard code-y approach, when you can ignore the formula and do the standard code-y approach from the start...Note that I'm just repeating my first post now.
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Because that s the first thing that came to mind in contest. Also I think you might be comparing oranges and apples here, “the standard code-y approach” part of my solution is mostly copy paste.
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Doesn't really matter if copypaste or quickly written from memory, the difference I'm focusing on is nice solution vs boring solution, specifically that I tried a nice solution and failed so I had to go with a boring one.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Oh so you mean for the unweighted O(N) edges, we just need to iterate on the MST of the given edges? PS : Also I think O(M sqrt(M) * alpha) might pass cause alpha might be quite small for union find.
•  » » 4 weeks ago, # ^ |   0 I did this:Apply Prim/Kruskal with the difference that unassigned edges' weights will be assigned "on the go".On each iteration, if there is more than one available edge which is unassigned, it gets value 0. If there is exactly one edge which is unassigned, it gets value XOR.I got WA for my submission :( but I'm not sure if I have a bug or the idea is wrong.
•  » » » 4 weeks ago, # ^ |   0 That doesn't sound right at first glance.
 » 4 weeks ago, # |   +6 The hardest part of Div2-C is SpoilerFiguring out it's dp
•  » » 4 weeks ago, # ^ |   +2 I don't think that figuring out that it was dp was the hardest part since it was somehow obvious from constraint. Figuring out how to do the transitions was hardest.
•  » » » 4 weeks ago, # ^ |   +4 So you are saying that you can know whether a problem is brute force or dp by just looking at the constraint.
•  » » » » 4 weeks ago, # ^ |   +2 No, but we can give few minutes to think if this problem can be solved by DP or brute force.
•  » » » » » 4 weeks ago, # ^ |   +3 Have u even attempted this question , cuz i can't find any submission
•  » » » » » » 4 weeks ago, # ^ |   -6 I want to remain invisible. I don't want to discuss from my regular rated account and don't want any attention in it. This account is for sharing ideas.I know making 2 account is bad, but i am not using it for any bad purpose.
 » 4 weeks ago, # |   +17 Nice round! Love the animated sample explanations.
 » 4 weeks ago, # | ← Rev. 2 →   +7 Me before contest- "Hope I'll become expert today for the first time" Me after contest- "Nevermind! I'll regain my specialist in next contest" (-_-)
•  » » 4 weeks ago, # ^ |   0 I can feel you bro :/
 » 4 weeks ago, # | ← Rev. 2 →   0 When you know it's a dp problem but just can not figure out the solution.
•  » » 4 weeks ago, # ^ |   0 LOL
 » 4 weeks ago, # |   +21 Thank you for the contest. Really liked problems B and C even though I messed up and wasted an hour on C. Towa Maji Tenshi!
•  » » 4 weeks ago, # ^ |   +15 Towa Maji Daitenshi
•  » » 4 weeks ago, # ^ |   +17 Towa Cute Angel
 » 4 weeks ago, # |   0 Div 2 B Video Tutorial: https://www.youtube.com/watch?v=NrZH8kuIcQk&t=2s
 » 4 weeks ago, # |   0 The most upset moment is that I always get TLE for problem C in div2 even I can do this. Time limit exceeded in Pretest 13 (for pypy3)
•  » » 4 weeks ago, # ^ |   0 you should try dp
 » 4 weeks ago, # |   +4 Can anyone tell what bug is there in this code ? div2D/div1A (Binary Literature)Code Link
 » 4 weeks ago, # |   +2 Is it just me or B's are getting harder these days? its heartbreaking after a year of hard work T_T
 » 4 weeks ago, # |   0 Why problem C use dp ? I think it should be greedy。
•  » » 4 weeks ago, # ^ |   0 greedy is used also in dp solution
 » 4 weeks ago, # |   +3 Why is the following algo wrong:? Given $s1$ and $s2$, if they have $x$ positions having different characters => number of same characters $2*n - x$ from i = 0 to 2*n: if s1[i] == s2[i]: print(s1[i]) else print("01") if $x <= n$, the string printed above has $length <= 3*n$. It can be proved. Getting WA on pretest 5 :(
•  » » 4 weeks ago, # ^ |   0 0101 1010 Your algo will print 01010101 (length 8 and 3*n = 6)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 The third-string will be used here. At least one of 0101 and 1010 has x<=n different characters with the third-string. Edit : This assumption is wrong. vioalbert has given an counter example.
•  » » » » 4 weeks ago, # ^ |   +3 I think your algorithm fails on the following test case. 1 3 000000 001111 110011 
•  » » » » » 4 weeks ago, # ^ |   0 Yes, was trying to find this during the contest. Thanks!
•  » » » » 4 weeks ago, # ^ |   +8 000111 011100 101010Try this, (1,2) will give 0010110101 (length 10) (2,3) will give 0101101010 (length 10) (1,3) will give 0100101101 (length 10)
•  » » » » » 4 weeks ago, # ^ |   +4 Can you please tell me where this noob solution fails https://codeforces.com/contest/1509/submission/113241451
 » 4 weeks ago, # |   0 Did anyone else solve B by figuring the minimum and maximum possible positions of each character 'M'? I thought that was really interesting! Also, the problems were fun, although I felt that the gap b/w C and D was a bit too much. Nevertheless, kudos to the authors!
 » 4 weeks ago, # |   +2 is true in div2C? each number is all either the maximum of the remaining or the minimum
•  » » 4 weeks ago, # ^ |   0 right
 » 4 weeks ago, # | ← Rev. 2 →   0 How to solve B ? I took lot of time coming up with right solution. I want to know if there is some better method.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 Key observation is, that we can use the first n/3 Ts as first T, and all other Ts as second T. Then you count the first Ts, the Ms and the second Ts. If at any point the number of Ms is bigger than the first Ts, or the second Ts is bigger than the Ms, then ans=NO.
•  » » » 4 weeks ago, # ^ |   0 Thanks, Now i think i really complicated it.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 My observation was that there must be at least one T on the left side of one M. For example, going from the left, "MMT" doesn't work, neither does "TTMMM". However, this only solves the left side "TM" of "TMT", so we'd need to iterate the string again from the right. If nothing fishy like the number of M exceeds the numbers of T in both directions, then we are sure that there is a solution for sure. Prior to doing all of the above, I made sure that the number of T:s are exactly twice as many as the M:s.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You can just iterate over the string from left to right and from right to left and count Ts' and Ms'If at any moment counter of M > counter of T the answer is No
•  » » » 4 weeks ago, # ^ |   0 thats it ?? :)
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I just forgot to say to make sure count of M at the end = n/3
•  » » » » » 3 weeks ago, # ^ |   0 3ash ya broo
 » 4 weeks ago, # |   -6 Guys how to get started with DP ? Can we learn it before graphs,trees,and other such topics . Please help
•  » » 4 weeks ago, # ^ |   0 Yes obviously.. But make sure you know recursion very well
 » 4 weeks ago, # |   0 How to do problem C?
•  » » 4 weeks ago, # ^ |   +1 First sort the s_i in increasing order. Let us find dp[l][r] = the answer for the array s[l...r]. Clearly, dp[i][i] = 0 for all 1 <= i <= nNow look at the process backwards, and convince yourself that we must remove either the maximum or the minimum process from s[l...r]. This gives us the recursion,dp[l][r] = s[r] - s[l] + min(dp[l+1][r], dp[l][r-1]).
•  » » » 4 weeks ago, # ^ |   0 Can you please elaborate a bit on how you made this observation?"Convince yourself that we must remove either the maximum or the minimum process"Thanks
•  » » » » 4 weeks ago, # ^ |   +1 Maximum difference in any subarray will be max-min, so if you pick max and min in a subarray before you will add the maximum difference to the cost many times which is for sure not optimal.
•  » » » » » 4 weeks ago, # ^ |   0 Thanks for the explanation.
•  » » » 4 weeks ago, # ^ |   0 can you please explain how you reached the recursion expression?
 » 4 weeks ago, # |   0 These given test cases are made beautifully It will always pass for any logic. Then definitely fail for the next test when we submit. Div 2 C gave the same joy. LOL!!
 » 4 weeks ago, # |   +51 I have fucking brain damage
 » 4 weeks ago, # |   0 Hoping for a quick editorial!!
 » 4 weeks ago, # |   0 awesome contest guys thx
 » 4 weeks ago, # |   0 problems were nice! Good round.
 » 4 weeks ago, # |   0 https://codeforces.com/contest/1509/submission/113246060 What's wrong with my approach ? Div 2 problem B
•  » » 4 weeks ago, # ^ |   0 This test case drops ur code16TTMTMTThe answer is YES
•  » » » 4 weeks ago, # ^ |   0 Got it . Thanks
 » 4 weeks ago, # |   +9 Best round I've seen in a long period!
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
 » 4 weeks ago, # |   -40 MikeMirzayanov it's a bit annoying that during the round to check how many pretests are there we have to use m1.codeforces.com. Could you please do something so it's also visible in the main website?
•  » » 4 weeks ago, # ^ |   +54 Pretests Passed(X)Isn't X the number of pretests? It is available on the main website.
•  » » » 4 weeks ago, # ^ |   +14 Ops, strong habit, sorry then.
•  » » 4 weeks ago, # ^ |   +16 Is the number after "accepted" not the number of pretests?
»
4 weeks ago, # |
-66

# Is it rated for me

 » 4 weeks ago, # |   +12 Can we have a notification when editorials are out and your participated in that round? As it is quite tiring to check for editorials again and again.
•  » » 4 weeks ago, # ^ |   +16 Is up now!
 » 4 weeks ago, # |   +8 How to solve problem E? (I have a $\mathcal{O}(n \log^2 n)$ solution with HLD and treaps, but it TLEs :( )
•  » » 4 weeks ago, # ^ |   +18 So the first observation to be made is that is there's an answer, then you can obtain the order of the children immediately by sorting each node's children by its value.After this, I suppose you went the simulating way, but there's another observation that makes it much more easier: you can visualize the operations as pushing the label $u$ towards a leaf, and that leaf happens to be the node where $u$ is its post-order! (in other words, at the end where there are no operations to be made, the labels form the post-order of the tree). So you can additionally create the post-order of the tree, and from that you can do side-by-side checking.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 The Problem C in Div-2 doesn't pass in Python, please change the limits for python
 » 4 weeks ago, # |   +8 how did you guess that C is dp? i tried everything except dp
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 This may sound like cheating, but notice the constraints allows O(N^2) so you should think of DP. If a problem at this level(for example first half in div2) is greedy then it is likely that the complexity should be linear or NlgN. The fact that it allows O(N^2) highly suggests that naive greedy would fail on some edge cases.Not a good idea though. Try finding why your greedy(I assume you use greedy?) is wrong helps you improve.
•  » » » 4 weeks ago, # ^ |   0 The problem was tagged greedy for Div2C, would greedy work? I spent an hour implementing a greedy version, which seems like it would not work :(.
•  » » » » 4 weeks ago, # ^ |   0 The greedy tag refers to the fact that for dp(i,j), either i or j should be the last one to enter, so you don't need to try j-i+1 possibilities. Sometimes dp requires some observations (like greedy), but greedy can not solve this problem as a whole.
•  » » » » » 4 weeks ago, # ^ |   0 The greedy tag refers to the fact that for dp(i,j), either i or j should be the last one to enter, so you don't need to try j-i+1 possibilities Nice Observation, this statement makes a lot of sense. For a moment, I was left surprised when we only considered the min/max as the last one to enter, so we are definitely considering the choice of the last position as a greedy choice. I will take note of this!
 » 4 weeks ago, # |   0 Weebs' round. I love it
 » 4 weeks ago, # |   0 Can any of you help me understand the verdict for DIV2.D?Submission: 113250060Verdict(pretest 3): "wrong output format Unexpected end of file — token expected (test case 1)" Has it got something to do with array capacity/length? What am I missing here?
•  » » 4 weeks ago, # ^ |   +3 You didn't output anything.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 dorijanlendvaj yes, right.But, the confusion is, it did output for smaller inputs. So something must be wrong processing larger inputs (Breaks at pretest 3; n=99999)I couldn't still figure out why, only for large inputs, would it not output anything, .
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 5 0000000000 0000111111 1110101010Your code doesn't output anything on this test case.Test case 3 is very similar; the first string is 199998 0s, the second string is 99998 0s and 100000 1s and the third string is 50000 1s, 50000 01s and 49998 0s.
 » 4 weeks ago, # |   0 Please give small clue for Div2E or Div1B, through simulation I figured that total possible almost sorted permutations for $n$ length array was $2^{n-1}$, and there was some kind of pattern being followed but could not uncover it...
 » 4 weeks ago, # |   +7 So the Anime theme round ends with SUPERSONIC score distribution , rating changes and editorial. Thank you so much XD
 » 4 weeks ago, # |   +3 To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
•  » » 4 weeks ago, # ^ |   0 One question :: suppose you have found 50 cheaters and lets suppose my rank was 2500 and all the 50 cheaters were from 1-2499.suppose I have got +20 delta in my rating change. Will my rating be changed after removing the cheaters??If it is, then will my rating increase or decrease than before??
 » 4 weeks ago, # |   +55
 » 4 weeks ago, # | ← Rev. 2 →   +2 Can Someone give me test case for which my submission for problem D gives WA. LINK to submission You can also point out mistake in my code. It will be very helpful.
•  » » 4 weeks ago, # ^ |   0 foxface_ap, here's your break case: 1 3 111111 110000 001100 (Your code doesn't output anything)
•  » » » 4 weeks ago, # ^ |   0 Thank You. :)
 » 4 weeks ago, # |   -7 https://youtu.be/28njldrBEo4My easy explanation in python of problem A.Be ready for problem B too :)Tnks and don't downvote please
 » 4 weeks ago, # |   0 Hello, I am a new user of codeforces and I joined your contest today. I solved problem A and B and got 70 points in total. Did i do something wrong or is there something wrong with codeforces?
•  » » 4 weeks ago, # ^ |   0 no ,you are good enough,proud for you
•  » » 4 weeks ago, # ^ |   0 Why are you lying? Unnecessary comments to gain sympathy. I checked your submissions you have got 1058 points.
•  » » » 3 weeks ago, # ^ |   0 I’m not lying, check how many points i got from contests i participated lately. very low scores for some reason
•  » » 4 weeks ago, # ^ |   0 so weird!!! usually, u must gain up to +200 according to your rate
•  » » » 3 weeks ago, # ^ |   0 I know right.. i don’t know what to do lol
 » 4 weeks ago, # |   0 can some one explain problem c in more detail?i am not getting sorting and dp part
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 the aim here is to minimize discrepancies di, ans= d0 + d1 + d2 +.......dn-2, dn-1, for the last di , i.e. dn-1 , we are taking the whole array,we have no choice but to take min and max of array. so dn-1=maximum in array — minimum in array but with dn-2 , we have option to leave out ONE element, there are two choices 1. leave out max element (in sorted array the last element) 2. leave out min element (in sorted array the first element)for dn-3, we have option to leave out TWO element, there are two choices 1. leave out max element from remaining 2. leave out min element from remaining [1,2,3,4] / \ discarding min / \ discarding max / \ [2,3,4] [1,2,3] / \ / \ discard min / discard max\ discard min / \discard max [3,4] [2,3] [2,3] [1,2]
 » 4 weeks ago, # |   0 Why is this code wrong(Problem Div.2-D)? https://codeforces.com/contest/1509/submission/113266390
•  » » 4 weeks ago, # ^ |   0 my code are cleanerYour text to link here...
 » 4 weeks ago, # | ← Rev. 4 →   0 Emmm, I have a very mysterious problem about problem B of div.2!I surprisingly found that when I iterated string "s" by using "for(auto &i : s)",I got a WA on test 162nd.After a very long time's debugging, I attempted to replace "break" with "goto",and then got an AC. Could anyone explain the reason behind this?!Much obliged! My submission:using "goto" : 113285205using "break" : 113284849Sorry for my poor English..If there are any grammar mistakes,plz ignore it...
•  » » 4 weeks ago, # ^ |   0 The one using break doesn't skip the 2nd loop, use return insteadTry this: 1 12 TMMTTTTTTMMT ans is "NO" but yours prints "NO NO"
•  » » » 4 weeks ago, # ^ |   0 I see! Thanks a lot!!
 » 4 weeks ago, # |   +3 Had -114 in the contest can anybody feel my pain?
•  » » 4 weeks ago, # ^ |   +3 I wish my upvote for you could ease your pain a little^ ^
•  » » » 4 weeks ago, # ^ |   +3 Thanks buddy .I surely will come back stronger next time. With this comment I promise to be expert in next 50 days.
 » 4 weeks ago, # |   0 Can someone please tell on which case the code is failing? https://codeforces.com/contest/1509/submission/113229976
•  » » 4 weeks ago, # ^ |   0 try TMMTTT
•  » » 4 weeks ago, # ^ |   0 TTTMMT*
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot! I got it
 » 4 weeks ago, # |   0 Can anyone tell me why this solution of DIV2/C is giving TLE with Memoization? https://codeforces.com/contest/1509/submission/113300784 I really can't figure out the silly mistake.
•  » » 4 weeks ago, # ^ |   +20 You are copying vector v every time you run the function. Try using reference (i.e. vector &v).
•  » » » 4 weeks ago, # ^ |