* "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:

- Sir antontrygubO_o for being an amazing coordinator; the round wouldn't happen without you ❤️
- Scrubpai, 1-gon, hugopm, tfg, dorijanlendvaj, xuanquang1999, 300iq, Mike4235, Luminal, QuangBuiYT, jamienguyen, Pichu, chctxdy68, neko_nyaaaaaaaaaaaaaaaaa, gamegame, MrDecomposition, TheDramaQueen, nor, and alimq for testing the round and providing valuable feedback.
- MikeMirzayanov for the amazing platforms Codeforces and Polygon!
- And of course, to all the participants of this round!

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:

- wannahavealife (solved all problems!)
- traxex2
- _su1sen
- I_love_Ilya_Krasnov
- 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!

As a tester, they shoved weeb propaganda down my throat. I recommend participation.

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.

As a tester, the problems are very elegant and you should participate in the round.

anime propaganda? i'll skip.

Round rotavirus skips -> good round

are the rounds, in which rotavirus participates, bad?

you've participated in his rounds so ...

The implication is one-directional: there exist good rounds you participate in. But if a round is bad, then you necessarily participate in it.

I'll participate in this one then

nah this is not interesting.

contrapositive geniosity

Anime is shit, change my opinion!

my waifu for aiur

u high bruh?

this was a wise decision....but XD

i totally agree

Wtf.Yagate Kimi ni Naru is a

Shoujo AiAnime. Shoujo ai is something related to yuri and yuri meansLesbian.So what? Its a piece of art.Change my mind.

I won't let anyone change your mind

So? It's

art, broEven better

I see you're a fellow capybara enjoyer

Now this is called a complete round, This round gives you anime recommendation(Yagate Kimi ni Naru) for dealing with post contest

depressionor celebration.These bleeding weebs lmao

i never expected a timeline where bloom into you is getting a competitive programming adaptation

Neither did I so I made it myself.

Adapt a "Kimi no Na wa" then, next time. Seems you're a fan of love.

completely shocked when I entered the main page, haha

Looks like anime will soon takeover the world :D

This post shows ,it already have

I like this round already

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

The problems will be very good so no bad memories will be associated :sunglasses:

I confirm that Yagate Kimi in Naru is a wonderful lesbian/yuri Japen comic, I highly recommend it too :(

Thanks for the early score distribution : )

nice contest~

WEEB IN!!!

otakus also in !!!

I think I need to code for counting the number of a's in neko_nyaaaaaaaaaaaaaaaaa

You say weebs, but all I see are people of culture. Respect!

Hope to perform my best till now, in this round!

So, when are we getting a round themed around AOT?

What about jujutsu kaisen ?

besto friendooo.....

As a Japanese otaku, this is why I cannot retired from CF!

I hope the tasks are as amazing as Yagakimi.

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.

NO_WORRIES

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.

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.

Didn't know Ari was Vietnamese :O

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

Almost copy-pasted part :)

Spoilerhttps://codeforces.com/blog/entry/82329#comment-692934 https://codeforces.com/blog/entry/81527#comment-682038 https://codeforces.com/blog/entry/81377#comment-680706 https://codeforces.com/blog/entry/79620#comment-655959

I see, people tag Ari unnecessarily after her comment

More like northern American authors

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.

I believe the registration page is not updated yet. I will contact to fix the issue :)

As a "noob" tester. This round is very "balance" and very good. Wish all the participants have a positive rating! :)

Imagine calling yourself a noob when you have got a privilage to test a round.

such a geniosity.....

Will I go green UwU?

Loved the suggestion,

"stay hydrated during the round", also the quote mentioned.Yeah but always take care to not to take out your stress by drinking a lot, overhydration is also not good.

.

A round with anime propaganda? I'm in.

up

I am very excited for this codeforces round because the Problemsetters are Ari and Kuroni.

Me too~

im trying to understand the blog & comments but i have no clue : (

Normiehope you don't feel the same way with problems

If you have no clue, then think of us:( May be an editorial over comment history be a new update:)

Hope the Aquaman in me wakes up for some time during the contest instead of

Aqua sama.sir why does contest have lessbyan cartoon theme?????

You should be judged by

KAMI SAMAfor addressing an Anime as a cartoon :DBeing an otaku , very excited for this round.

I hope we will get more episodes of these kind of round XD

Colorful testers :)

I love the quote.

From Vietnam ưith love!

ưhat's up :)

The comment is hidden because of too negative feedback, click here to view it

A round? I prefer two matches in Dota 2.

I prefer a positive delta change of > +50 in an Anime theme round XD

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

you definitely mean one match of Dota 2 with Techies

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

"

is div 2 round rated?

HAPPY ANIME DAY!!!(15th April)

YagaKimi is brilliant. Contest setter has good taste.

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?

Cool, it's still as toxic as always :)

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.

No I don't

Haven't seen this many upvotes for a contest blog in ages . This contest was great.

Monogon literally

justheld his contest...I think so

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!

can't wait to participate!!

Kuroni's stand be like

MemeA romantic contest ... I like it

Don't judge a book by it's cover.

SpoilerSame goes with

Yagate Kimi ni NaruI just started that anime ... Seems pretty good

Finally a contest with Div2 B = 1000 score! No Alan Turing level mathematics I expect!

maybe

Hope I remain EXPERT after this contest!.

why not

Score of Div2. D is scaring me !!

SpoilerD = 2250

How many problems are common between both divisions?

According to the score distribution seems that Div2 D = Div1 A

How can it be compared from score distribution?

The usual score distribution is:

500 — 1000 — 1500 — 2000 — ...in this round Div2 D = 2250 and Div1 A = 750

Div2 D = Div1 A

??

hlw guys plz tell me how to make a user my friend???

press on this star

ok thnx

thnx

ok

Hopefully I will become pupil after this contest.

You will man :)

you will~

Don't worry I am sure it will be easy :)

I wish i would solve atleast 3 to 4 problems in this contest ;-;

you can , i believe you~

A contest on Naruto also:)

Naruto Uzumaki~

All the best every one.

I am Sooooooooooooo Excited ❤

me too

Dmitry cdkrot Sayutin likes this post 'cause it's propaganda for two girls to participate in SIS.

I hope they make an Attack on Titan round when the last episode airs next year >.>

chapter 139 had me in tears ngl,eremika forever!!

Have a great Rating Change :)

i got

I also got, but my rating decreased XD

sdfoiSF

hi

WA on pretest 5

I can feel this comment.

Yeah, it's WAForces!

how to share photos?very grateful to you!

I got to say the pictures that explain the examples are lovely.

what the heck is pretest 5 of div2C

how to solve div2C?

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

It is the place where green's rest.

try 8 1 2 4 4 5 9 9 10

ans?

33 (4 4 5 2 1 9 9 10)

Thanks, this is where I failed

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

How to solve Div 1 A ( Binary Literature ) ?

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.

Oh! FU**!. Thanks.

Tried to did the same. No idea what went wrong ?

submission link

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).

My bad. Thanks.

I feel like I have been getting better and then I fail to Div 2C? How to solve D2 C?

DP

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

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.

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

Sort the speeds then compute the minimum cost to include racers with speeds si...sj.

I was able to upsolve that, thanks.

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

Can some one please explain how to solve Div2 problem D

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$$$

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`

.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

How to solve Div2B?

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

Yes, saw some solutions. But, why does this works?

while traversing from start..for every M..there must be atleat one T before it..similarly while traversing from back

I feel dumb now.

Sent you a message. Cause I am unrated , its not allowing to comment more than once in 10 mins

Thanks, I understand it now.

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.

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'

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.

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.

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.

agree with you,c is much easier to code

Read every submission from jiangly and your implementation will become CLEAN and FAST.

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.

can anyone help with div2 D? Couldn't get it working during contest.

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

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

Anyone can tell me why my solution for D/Div2 get WA?

113255849

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.

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))$$$.

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.

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.

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.

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.

EDIT: Found my mistake.

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...

I meant the exact idea for solution. anyway...

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.

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.

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.

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.

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.

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.

That doesn't sound right at first glance.

The hardest part of Div2-C is

SpoilerFiguring out it's dp

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.

So you are saying that you can know whether a problem is brute force or dp by just looking at the constraint.

No, but we can give few minutes to think if this problem can be solved by DP or brute force.

Have u even attempted this question , cuz i can't find any submission

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.

Nice round! Love the animated sample explanations.

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" (-_-)

I can feel you bro :/

When you know it's a dp problem but just can not figure out the solution.

LOL

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!

Towa Maji Daitenshi

Towa Cute Angel

Div 2 B Video Tutorial: https://www.youtube.com/watch?v=NrZH8kuIcQk&t=2s

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)

you should try dp

Can anyone tell what bug is there in this code ? div2D/div1A (Binary Literature)

Code Link

Is it just me or B's are getting harder these days? its heartbreaking after a year of hard work T_T

Why problem C use dp ? I think it should be greedy。

greedy is used also in dp solution

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$$$

if $$$x <= n$$$, the string printed above has $$$length <= 3*n$$$. It can be proved. Getting WA on pretest 5 :(

0101

1010

Your algo will print 01010101 (length 8 and 3*n = 6)

~~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.I think your algorithm fails on the following test case.

Yes, was trying to find this during the contest. Thanks!

000111

011100

101010

Try this, (1,2) will give 0010110101 (length 10)

(2,3) will give 0101101010 (length 10)

(1,3) will give 0100101101 (length 10)

Can you please tell me where this noob solution fails https://codeforces.com/contest/1509/submission/113241451

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!

is true in div2C? each number is all either the maximum of the remaining or the minimum

right

How to solve B ? I took lot of time coming up with right solution. I want to know if there is some better method.

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.

Thanks, Now i think i really complicated it.

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.

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

thats it ?? :)

I just forgot to say to make sure count of M at the end = n/3

3ash ya broo

Guys how to get started with DP ? Can we learn it before graphs,trees,and other such topics . Please help

Yes obviously.. But make sure you know recursion very well

How to do problem C?

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 <= n`

Now 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])`

.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

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.

Thanks for the explanation.

can you please explain how you reached the recursion expression?

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!!

I have fucking brain damage

Hoping for a quick editorial!!

awesome contest guys thx

problems were nice! Good round.

https://codeforces.com/contest/1509/submission/113246060 What's wrong with my approach ? Div 2 problem B

This test case drops ur code

1

6

TTMTMT

The answer is YES

Got it . Thanks

Best round I've seen in a long period!

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).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?

`Pretests Passed(X)`

Isn't X the number of pretests? It is available on the main website.

Ops, strong habit, sorry then.

Is the number after "accepted" not the number of pretests?

## My rating is 672 i am a newbie. I participated in Round 715 Div2 .

## Is it rated for me

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.

Is up now!

How to solve problem E? (I have a $$$\mathcal{O}(n \log^2 n)$$$ solution with HLD and treaps, but it TLEs :( )

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.

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).The Problem C in Div-2 doesn't pass in Python, please change the limits for python

how did you guess that C is dp? i tried everything except dp

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.

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 :(.

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.

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!

Weebs' round. I love it

Can any of you help me understand the verdict for

DIV2.D?Submission: 113250060

Verdict(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?

You didn't output anything.

dorijanlendvaj yes, right.

But, the confusion is, it

didoutput for smaller inputs. So something must be wrong processinglarger inputs(Breaks at pretest 3;n=99999)I couldn't still figure out

why, only for large inputs, would it not output anything, .5 0000000000 0000111111 1110101010

Your 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.

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...

So the Anime theme round ends with

SUPERSONICscore distribution , rating changes and editorial. Thank you so much XDTo not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

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.

foxface_ap, here's your break case:

(Your code doesn't output anything)

Thank You. :)

https://youtu.be/28njldrBEo4

My easy explanation in python of problem A.

Be ready for problem B too :)

Tnks and don't downvote please

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?

no ,you are good enough,proud for you

Why are you lying? Unnecessary comments to gain sympathy. I checked your submissions you have got 1058 points.

I’m not lying, check how many points i got from contests i participated lately. very low scores for some reason

so weird!!! usually, u must gain up to +200 according to your rate

I know right.. i don’t know what to do lol

can some one explain problem c in more detail?i am not getting sorting and dp part

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

Why is this code wrong(Problem Div.2-D)? https://codeforces.com/contest/1509/submission/113266390

my code are cleanerYour text to link here...

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" : 113285205

using "break" : 113284849

Sorry for my poor English..

If there are any grammar mistakes,plz ignore it...

The one using break doesn't skip the 2nd loop, use return instead

Try this:

ans is "NO" but yours prints "NO NO"

I see! Thanks a lot!!

Had -114 in the contest can anybody feel my pain?

I wish my upvote for you could ease your pain a little^ ^

Thanks buddy .I surely will come back stronger next time. With this comment I promise to be expert in next 50 days.

Can someone please tell on which case the code is failing? https://codeforces.com/contest/1509/submission/113229976

try TMMTTT

TTTMMT*

Thanks a lot! I got it

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.

You are copying

`vector<ll> v`

every time you run the function. Try using reference (i.e.`vector<ll> &v`

).