#### Hello Codeforces!

ssense and I are very glad to invite you to Codeforces Round #726 (Div. 2) which will take place on Jun/18/2021 17:35 (Moscow time). The round will be **rated for participants with a rating lower than 2100**. Division 1 participants are also welcomed to take part in the competition but it will be unrated for them.

The round was originally planned to be a division 3 round so the problems might be slightly easier than average Div 2.

You will be given **6 problems** and **2 hours** to solve them.

We would like to thank the following people:

1-gon for amazing coordination of our round!

antontrygubO_o for testing, translating statements and providing useful ideas!

Maksim1744, Ari, qpwoeirut, magnus.hegdahl, PurpleCrayon, Brodicico, Omkar, DenjellBoone, Arsenie, Lost_Arrow, Etherite, asrinivasan007, nishuz, cringeworthyplayz, Nika_Tamliani, Vpurice for testing and providing invaluable feedback!

- MikeMirzayanov for great Codeforces and Polygon platforms!
You, for participating!

The scoring distribution is: **500 — 750 — 1000 — 1500 — (1250+1750) — 2000**.

**UPD:** Editorial

As a coordinator...

omg orz! monogon taking over cf!

Eventually I will fire Mike so I can be the real top contributor. (Don't tell him I said that)

monogonforces orz

As a follower of Monogon, I am obligated to upvote this comment.

At this rate, that day isn't far when...

WORLD WILL BE TAKEN OVER BY MONOGONIn the future, if you're gonna need an icon just contact me. I'll do it for

~~free~~just a few upvotes.Should I resume share or okay this?

Also,

The guy who looks 34-35% similar to Mike - memeOFZ

ORZ 1-gonforces

Congrats for the successful steal of Anton's Job.

whatever man just take my upvote :/

As an Upvoter...

in this contest i had solved problem A in first 8 mins and i was checking for the results and it was showing "in queue" so i thought to submit it on m1.codeforces so that it get tested fast but now i have seen that both of my solution got passed but the system have rewarded me the marks for the second one which i have submitted 2mins after and also it has given me -50 . can you plzz say something or do something on this plzzzz first time in 6 months i was able to solve 4 prblms in div 2

According to the official rules, only the last submission with pretests passed is considered for system testing. When your submission was in queue you should've just waited and moved on to read the other problems.

Hi 1-gon Can we do something for questions getting leaked before contest and answers getting posted on YouTube...?? That's what happened in the contest...

As a tester, I tested.

Just take my upvote

Yea we can see your name in tester's list,why say it again?

Yes, but how do you know what he did as a tester?

You must have tested problems. Right?

``oz

Well tested!! Strong tests were included in system tests.

I had the same fate, my friend. just changing s to s+s corrected it

newbie sens

As a participant, I hope to become purple in this round. Wish me luck !

All the best, as a participant I hope to get my confidence back

As a guy , I just want to be happy

I dont want to be hor*y anymore. I just want to be happy.

as a newbie I wish the same and I hope for all of us to get to that level and more hopefully :)

Good Luck! I hope you become purple after this round but I sincerely hope that it's not coming at my ratings' expense.

Seems the opposite happened lol, you got rating at my ratings' expense :O. Anyways, good show.

Hello ^^

As a tester, i'm proud of these guys.

Just take my upvote

Probably copying previous comments does not help. People who plan on doing this can probably take note. Hehe

CF can be ruthless haha

Damn ! Author of the blog Yur Heat Map is Very InSpiRational !!!

5 months later, I'm still annoyed that you didn't take kostia244's suggestions for your new handle :(

:(

The biggest scam of 2021

I_Love_SlavicG

When the author gets lesser upvotes than the setters.

Did all the testers downvote this? I guess it doesn't matter since Monogon will soon rule Codeforces.

As a tester, I_Love_YrNameCouldBeHere ORZ

PSinspirational

It really motivated me I_Love_YrNameCouldBeHere

what about

this guy?tenkei

RunTimeTerrorMotivation overflowtenkei retired

He already gave us so much motivation and showed us everything is possible if we try honestly and embrace hard work. Hope he enjoy his retirement. We will miss him. Orz.

Orz =))

Score distribution suggests that the contest is All-Killable

So blues are writing div2s now? whats next? greendians writing div1?

Chup chapri. Dont write these useless messages.

keyboard_warrior Another bluedian defending your blue buddies? Hope even you get to write a contest next.

even if the problems were not worth it,the testers and coordinators and other people involved with this contest (a lot of whom have a ton of experience with contest-making i'd assume) would have caught that and we wouldn't even be seeing this announcement.at all...(edit: fixed some grammar mistakes)

What about purples/blues(not me) who have really good problem ideas and not able to propose a contest because of the rating barrier and end up in submitting them in less kown websites or just moving on with dissatisfaction.

make unofficial round.

I have a dream, that one day authors may be judged by the quality of their problems, rather than the color of their handle.

As a tester, I can say that the problems are nice, and I recommend participating :D

THIS IS SPARTAAAAA

Well, if you look at their number of solved problems you can easily say they solved enough problems to make their own problems. Also some red coders tested/coordinated it so there is no reason to not make a round. And those "greendians" are better than an unrated person with -53 contribution.

mad?

And what is your rating, mister alt user?

As a tester, I couldn't help much with review of problems except in the initial div3 phase. The round is well balanced and may positive delta come your way :blobheart:

Upvoted! Hope your Blessing Comes true...Pupil, I am coming BACK!!

All the best to all the participants,

may there be a positive delta... The scoring distribution is quite interesting.

Awesome 1-gon starts coordinating the round.

Moldova power!

As a tester, I highly advise you to read all the problems!

As a tester, I assure you that all problems are very interesting. Please do participate. All the best!

I often see this comment whenever we have a problem which is divided into two( easy & hard) versions . Let me guess E1 is a bit easy than D :) and one more thing we have to do a bit more reading :)

I got it right , E1 was easier than D :)

Don't they all suggest the same thing. I think the trick to acing the contest might be to

notread all the problems and not get depressed to try the problems.These rules changed?

Problem setter requirementsI guess they can be count as a writer in the past because they made 2 unoffical div 4 contests and those rounds had a good amount of participants.

No disrespect, but they are a bunch of some easy problems. So how do they count?

they said this meant to be a div3 round,so those problems were enough to give them a chance to write a round.

To reds, a Div. 2 is a bunch of easy problems. To oranges, a Div. 3 is a bunch of easy problems. So how do they count?

Honestly, I think the current rules were just a way to limit the amount of contest proposals without disenfranchising anybody. So if you were lucky enough to get something in before the new requirements, then you basically get grandfathered in.

Div 2 is not rated for oranges and above. Div 3 is not rated for blues and above. But this round is rated til 2100.

And since it was reviewed, coordinated, and tested by a bunch of people high rated, it should be reason enough to believe that the contest will have good enough problems for it to be rated for participants with rating upto 2100.

Probably, still I'm also somewhat dubious about the ability of people to come up with the problem and solution ~500-1000 points above their own rating, and the hardest problem of the round should be at least that difficult

No offence, it's just peculiar

Rating doesn't measure your overall problem solving skills.

A more accurate explanation is probably that it is quite possible to make a problem that is 1000 points above your rating by making a problem from the solution, instead of actually solving a problem you came up with. And, even for problems that you came up with, you have a lot more time to try to solve them than when in a contest, and you also probably have more chances to solve a hard problem(the participants can't notice all of the hard problems that you didn't solve when problemsetting).

Btw, all rounds have coordinators, but not all of them are equally good, so it doesn't really mean anything, just saying

Well, I didn't want to drag this on, but let's do it.

What is a good round / contest? one where you can solve 3 or 4 problems? you feel good after the contest, that maybe you solved every problem that you read during contest? Sorry to disappoint you that not every round can be good for you.

Tbh, have you ever even thought about what it takes to prepare a round, or the effort put in by coordinators / testers. All you see is the "Codeforces Round #XYZ" blog on CF. Although, I have never authored a round myself, I want to make problems for a while, but I can't even think about them. Forget about preparation of statements, constraints, test cases, and many other things that I might not even know about right now. Even though some rounds are not well recieved by contestants, it doesn't trash all the effort that was put into it, nor does it mean that problems are shit. Hell,the problems were accepted by anton, and even as a joke, it is popularly known how high a bar he has set.

Nah

Rly, do not assume that the other person is stupid. Whether my performance is good or bad has nothing to do with the round being good or bad. Say, LATOKEN round was quite good even though I got -50

Model good round is a round with good problems, balanced problems, diversed topics, good problem statements and good editorials. Also without long queues and other technical issues but that is out of control of coordinators.

It's all nice and everything. Yet again, some rounds are better than the others despite all the hard work of the authors you mentioned

Have you realized that the first 5 requirements you stated are completely subjective? Sorry, this website doesn't cater to each and every one of your individual needs. The round is good, it was tested by a wide variety of colours, it was coordinated by reds and approved by Mike, I'm not sure what else you could ask for.

Well put, I couldn't have said it better.

They're not so much subjective as you're trying to make it sound

Say if the statement is long and confusing for a lot of people, it is a bad statement and there is little subjective about it

If one problem has difficulty 1000 and the next one is 2200, it is unbalanced round

Etc

Also I don't quite understand what you're arguing about, Do you disagree that some rounds are better than the others? Because that is pretty much the sole point of my messages here

As the round has neither started nor you are a tester, then how can you say anything about a round when you literally don't know anything about the round

I don't know if you read the testing part, but the round has testers from almost every color from pupil to LGM.

So, it would be better if u shut up now and give your opinions after the round has ended.

There is a comments section in editorial also

Lets just end this thread by a

well known standard result: Quality of contest depends on your rank in that contestQED

What actually happened was some combination of Mike liking the problems but not thinking it was Div 3, and having Anton and Monogon coordinate.

They wrote an unofficial div4 contest on gym before, so it isn't a violation of the rules really. They had experience in problemsetting and messaged me (who started coordinating after that blog) about it, as it says in the last paragraph.

As a tester, I can certify this is a great round with interesting and clear problems. Best of luck to all who are participating!

Nice bro

Both the problemsetters have a highest rating of expert. So how did they propose this round, as you have to be a master to write one?

I guess they were

writer in past.And 1-gon also mentioned that they have organised a unofficial div4 round in gym in past . Apart from that there are many high rated people who are coordinating the round , if they have no issues then you shouldn't have .You can suggest problems if you are an expert. I don't know if it's any different than proposing contests.

As a participant I hope to get past C this round

I wish I could be expert. People how to get expert batch within a short time? Is it their outcome of lot of practice, How can I get expert batch? Please suggest me. (Sorry for unnecessary comment. But I need to know to develop my problem solving skill)

Literally just solve questions that are challenging enough, so basically problems that are rated +200 ish from ur current rating and try to understand and apply new concepts u encounter from editorials n blogs then u should be set.

I didn't knew that Blues can also host contest at codeforces.

Blue power exists. :)

are the problem statement short mainly first 2 as i am unable to do after that in last rounds hope that i will be able to solve a,b,c this time.

As a tester I think that reading all problems in 2 hours is very well doable.

So we can assume there can not be much more than 1000 words in each statement. Very reassuring

Yeah but tbh I've never found a contest where I wasn't able to read all problems. Reading them is not taking a large amount of time compared to solving them, regardless of the number of words

If 1-gon can write a good 3500, which is 900 higher than his rating, then can't I_Love_YrNameCouldBeHere write a good 2600?

2600 is the upper end of div2 difficulty. I think this will be an excellent round!

I have no idea who Zoroland_ is, and how he/she copied my code for A,B,C problems. It maybe because i used idone in public settings during this contest. I will stop using idone at all after this.

Motivational speech:

The round was originally planned to be a division 3 round so the problems might be slightly easier than average Div 2.In other words, if you perform badly then you're even worse than you thought.

Might be another speedforces coming up!!

Ah I see, the tables have turned now!

Thanks, and I hope the statement will be short and clear.

omg finally ssense ans slavic round, cant wait to participate!

Hope to solve problem C this time.

I wish I was never born

Ban radewoosh,he is racist.

OMG! What happen to Radewoosh?

Anyone noticed that when you move your cursor to testers' handles, you can see text "Tester" or "orz Tester"?

I see 1-gon >> yoyo master.

This is how it works-

<a class="rated-user user-red" href="/profile/1-gon" title="monogorz">1-gon</a>

and without actually tagging the person-

<a href="https://codeforces.com/profile/1-gon" title="master yoyo yoyo master master monogon monogon master 1-gon orz orz orz testing feature orz" style = "color:red; font-weight:700;">monogon</a>

Result: monogon

~~I hope 1-gon didn't recieve a notification for this.~~I didn't get a notification

Thanks! You never disappoint me, my lord. And you are fast.

As a commenter , I wish +2 :) I_Love_YrNameCouldBeHere

I'm also in desperate need of +2

I think 1-gon is gonna takeover codeforces completely !

This is gonna be my first contest. Wish me luck guys :)

All the best bro! Mistakenly I downvoted your comment so the best I could do is wish you luck!!

Haha im already into negative karma ;-; Is all good tho

As a participant, "As a + something" jokes are not funny anymore...

That's not true. "Anymore" implies there was a time when they were funny.

So you're testing if they will keep upvoting those I guess

I want to be a tester. But I don't know any of the problem setters, and I don't just want to be friends for benefits just to become a tester. Is there any hope?

i want to speclist

Score distribution says the total score of E is 3000, whereas the score of F is 2000. Does this mean E2 is harder than F? Interesting.

Not necessarily, it could also mean that the 2 subtasks of E aren't related, like 1092D1 - Великая Вовина Стена (Версия 1) and 1092D2 - Великая Вовина Стена (Версия 2)

Oh, that makes sence.

The day is not far when MikeMirzayanov will sit and rest and 1-gon and other GMs and LGMs will take over Codeforces ...

The person wrote this notice got lots of contribution :)

when you give monogon contribution, he repays you with contribution as well

I hope that all those who work hard will get good rating

I_Love_YrNameCouldBeHere Guys just have a look at his profile .... Respect ++ man :)

also the cool profile pic !

.

Im so proud of you guys for making this round !!! Way to hyped for tomorrow :yayy:

It's coinciding with WTC Finals ToT

No one cares

Did cf change their rule? I thought yellow was necessary to set problems!

I think either D or E is going to be an interesting game problem.

Well done myself!!

Anyone here who wants to get a prediction of their future cf rating??ASk me!! (or better, I should write a blog abt it :D)What about mine

Around 1450 after this contest and then you're gonna reach expert in a month or so.

What about mine.

How do you say this confidently?..what,s logic behind that?

Can you please predict my future?

:D

thanks for div3)

I am curious to know 'who invented

orz?' tag that person :oAnswer: orz's parents.

And if you want to know about them just ask orz. Maybe he'll ask them to join codeforces (just like SecondThread asked his mom) and then you can tag them. ✌️

answer is better than expected :p

Hello! I would like to propose the next Div. 1 please. I know I am unrated and have not given any contests but please do not judge me by my rating (or the lack of it lol) and give me a chance to write problems for an official contest. Thank you.

Tagging 1-gon for better reach.

You should either get the required rating to propose it, or demonstrate that you have sufficient problemsetting experience.

expecting my first codeforces contest!

i hope i can solve atlest 1 problem todaY all right i solved a and almost b.thank you for this contest author.boosted my confidence

wtf bro!! why you just didn't upvoted me

Hi All, My rating is 1309, Am I not allowed to appear in this contest.

no

Long Queue?

Queueforces :(

I have submitted problem A 4 minutes ago.It's still in queue..

Omg already fear of WA plus this queue making me go wild and nervous

waiting for my submissions to deque :)

In problem A is each appended number also limited by $$$10^4$$$ or any non-negative numbers are okay?

In Problem B, can Anton entre the same room twice?

(According to the Visualization, he can't, but the problem didn't say it.)

@I_Love_YrNameCouldBeHere

There is ask a question section where all problems are shown...Ask there

can you er-open the registration pls ?

As a loyal antontrygubO_o supporter, I upvoted 1-gon . Have you?

my upvote only to 1-gon sir

wa2forces...

I think this round should be unrated.

The reasons:

queue forces.

F is similar problem ,it was solved 200+! (include Low level players (like me).).

lol what

The same problem should be banned from such kind of contest!Strongly support this proposal.

actually it should be the other way around

How? Its pretty intuitive that the optimal string you use in E is going to be a repetition of prefixes, so just try all of them, felt as easy as A-C at least in my opinion.

D is to realize the "good" and "bad" states — if you just throw out some prime factorizations on paper you'll realize that as long as you have an even power of 2, or at least 1 "2" and another number, it's a good state and Alice wins. (if i get fst, rip)

Else bob.

Anyways for E, im bad at cpp so I used java and had a bunch of stupid bugs

Finally, I think C is the hardest problems :P

Yes, and I brute first 1000 values of D and solved it the same way. But it actually took time to do that. At least for me E1 felt far more obvious.

C would actually be tricky if they didn't give away both the cases in the samples lol. In terms of difficulty I'd say:

B < A < C < E1 < D < E2 < F

geniosity orz, thinks B is easier than A

My solution to B was just printing "1 1 n m", sure it took me a tad bit longer than A, but even I found it easier :P

How did you solve E2 , can you just give a basic idea

I gave the rough idea in this comment

Can u please explain how u even brute forced D,I tried but i couldn't.

logicLet's call a position good if the played playing at that position win.

dp[i]=1 // if position i is good base case dp[0]=dp[1]=dp[2]=dp[3]=0; because if some player lands into these positions he, don't have any divisor to subtract.

now, loop for all i's in the range 4 to 1000

suppose currently i=12. check for all divisors of i which we can subtract and the new number we get after subtracting is:

new_no = i-divisor_that_we_subtracted.

These new numbers that we get after subtracting are the position we can send the other player to. if any of the new positions is bad, we will send the other player to that position and he will lose. So, dp[i]=1 if any of dp[i-divisor(i)]=0;

now to check for any n in range 1-1000

if dp[n]=1 // alice wins

else bob wins because alice is starting the game

codehow did you brute force 1000 values? logic?

refer this

Thank you

I still don't know how you're supposed to reach the solution of D, I just brute forced for small values and observed the general and edge case (and then proceeded to submit only the edge case, not the general one and get confused when it got WA)

I think the general idea is: plot out some initial values, make a conjecture, then try to prove your conjecture.

Conjecture: For any $$$n \gt 0$$$, the first player has a winning move iff $$$n$$$ is even and not an odd power of 2.

Proof by strong induction. The base case $$$n = 1$$$ is obvious. For the inductive step, let $$$n \gt 1$$$ and suppose the claim holds for all $$$m \lt n$$$. We can show the claim is true for $$$n$$$ by case analysis:

Case 1: $$$n$$$ is an odd prime. Then there are no moves and the claim holds.

Case 2: $$$n$$$ is an odd composite. In this case all divisors of $$$n$$$ are odd. Suppose the player plays some divisor $$$a$$$, and let $$$b = n / a$$$. Then the new value is $$$m = n - a = a \cdot (b-1)$$$. Since $$$a$$$ and $$$b$$$ are odd, $$$m$$$ is even but not a power of 2, so by our inductive hypothesis $$$m$$$ is a winning value. So $$$n$$$ has no winning move and the claim holds.

Case 3: $$$n$$$ is an even number, but not a power of 2. Then $$$n$$$ has an odd proper divisor $$$a$$$. Let $$$b = n / a$$$ Then $$$b$$$ must be even so $$$m = n - a = a \cdot (b-1)$$$ is odd, and by our inductive hypothesis a losing value. So $$$a$$$ is a winning move for $$$n$$$ and the claim holds.

Case 4: $$$n = 2$$$. $$$n$$$ is an odd power of 2$ and there are no moves, so the claim holds.

Case 5: $$$n = 2^k$$$ for some $$$k \gt 1$$$. Then any valid move is of the form $$$a = 2^i$$$ for some $$$1 \le i \lt k$$$. Let $$$j = k - i$$$ and let $$$b = n / a = 2^j$$$.

If $$$j = 1$$$ then $$$m = n - a = 2^{k-1}$$$, which by our inductive hypothesis is a losing value when $$$k-1$$$ is odd.

If $$$j \gt 1$$$ then $$$m = n - a = a \cdot (b-1)$$$ is even, but not a power of 2, so by our inductive hypothesis this is a winning value and $$$a$$$ is a losing move.

So when $$$n$$$ is an even power of 2 then $$$a = 2^{k-1}$$$ is a winning move, otherwise there is no winning move, and the claim holds. This completes the induction.

That's obvious coz

`D:1500`

and`E1:1250`

i was solving e1 and e2 for an hour)

lot's of FST's coming :(

Weak pretest in E1 — my AC code fails on n=8,k=8 [dcdadcdb]

FST coming :(

What is the answer of this test case?

`dcdadcda`

Can you explain, how?

Remove the last 4 characters (

`dcdb`

) using operation 1 four times. Concat the rest of the string (`dcda`

) twice using operation 2.Yeah, my bad! I am getting

`dcdadcda`

What's the logic for D? I just observed the pattern from a brute-force solution and got an AC without any logic.

Due to induction. For numbers > 9 and not power of 2, you can see that it if it's even then Alice will win else bob. If even number has odd factor, then we can subtract odd factor from it and resultant number will be odd and use answer of previous numbers.

rananjay23 Can you explain a little bit more the logic of D?

I started writing down numbers from 1 to 21 and found following : Bob wins for 1,2,3,5,7,8,9,11,13,15,17,19,21 Alice wins for 4,6,10,12,14,16,18,20

For even n, if it's not power of 2, then there is some odd divisor say o>1. Hence n-o is odd and we know result of it . Example : n=22, then 22-11=11 and we know who wins if n is odd and less than 21.

Similar reason you can find for odd numbers > 21.

For even numbers with power of 2, It's always alternate i.e for 8 bob will win, for 16 Alice, for 32 Bob. Here also explain (just subtract divisors and see) in similar way.

I wrote out a proof here: https://codeforces.com/blog/entry/91835?#comment-805791

The pretests for E1 are trash!

I kicked myself for spending 1 hour on C :(

F is a easy version of https://www.luogu.com.cn/problem/P6185

Line graph version of F also appeared very recently in https://atcoder.jp/contests/arc119/tasks/arc119_c

I feel like the operation of adding x to two adjacent cells also appeared on many other CF problems before. They are almost always solved by two coloring.

Nice Round. Thanks for this :)

Not good for me. Solved E1 after 4 WA's just because of min/max string silly mistake. Rank dropped from 500 in first half to 1400 till end. And left with no time to try E2

Moral:- Don't submit again and again by changing small part just erase whole solution do that again. Hopefully that silly mistake will be resolved.

B failed in system testing..

Reason — 1 "=" sign

My bad

The problems are cute, but don't you think this is closer to Div2.5 than Div2? My first full solve of a Div2 and its around what I would have got for a fairly fast n — 1 problems in a Div2 normally.

Yess, the authors have mentioned in the above blog:

The round was originally planned to be a division 3 round so the problems might be slightly easier than average Div 2.which is probably why it felt easier than the rest :)

Found the OEIS sequence for D in the last 3 minutes. Completed my code 10 seconds after the contest got over due to a stupid mistake.

Now I feel sad.

Wait same, but I got when $$$\omega(n)^{\phi(n)} \equiv 1 \pmod{n}$$$, which is apparantally wrong.

I got this one

OEIS

That one doesn't seem to be the answer though. I'm not sure but I get that the answer is

Odd -> Bob win

Even we have two cases

2^k with odd k -> Bob win

Otherwise -> Alice win

This passes the pretest but I need to wait for the system test for confirmation.

Odd -> Bob win?

What about n=9? (Given as an example in the problem). Also, 25. Or are those just a special cases?

n = 9 is not in the example.

Also, check this! https://codeforces.com/blog/entry/91835?#comment-805566

whoops... guess my brute forcer was borked.

n=9 was in an explanation and it was Bob's turn to move, and he lost. So n=9, Alice's turn, she'll lose.

I didn't get A for most of the contest because I'm an idiot, but this was a fun contest!

For E, what you do is take some prefix and concatenate it until it's at least length $$$k$$$. In E1, you can brute force every prefix. In E2, is the approach some kind of z-function thing?

Weak pretests for E1. :( . whereas good pretests for E2 :( .

Test case on which your E1 might fail

12 30

dbdbdadbdbdb

Correct Output

dbdbdadbdbdadbdbdadbdbdadbdbda

Was E2 = E1 + suffix array for the reversed string?

I thought to do that, but then I passed pretests by greedy...

And now it failed. lmao.

I used rolling hash values in combination with binary search to find out which part of the subsegment of the string is different from the prefix string.

Not really, its a simple greedy.

Clearly as we proceed from the starting of the string (after the first character) its optimal to take any $$$s_i \lt s_0$$$ since it will lead to a lexicographically smaller result than appending the string which will add $$$s_0$$$ again at that point.

But what about if $$$s_i = s_0$$$? Then we have to check further characters. We can see that it will produce a better answer if in the first position where $$$s_{i + k} \ne s_{k}$$$, we have $$$s_{i + k} \lt s_{k}$$$.

We can maintain this by just keeping a counter for this k when we reach an equal element and resetting it when we get a smaller character (or breaking if its a larger character). Additionally we have to be careful to store this temporary string during the equal part somewhere else and only add it once we reach this k-th position.

Code — 119871715

"We can see that it will produce a better answer if in the first position where si+k≠sk, we have si+k<sk"What about the prefixes which are ending between i and i+k? Should we not check for them as well and figure out the best prefix in this window? What's the reason behind claiming that repeating (i+k)th prefix is the best option?

https://oj.uz/problem/view/BOI13_pipes

I often take Virtual Practice on CF and am used to facing a lot of hack tests. So since I saw the small number of the pretests, I have been very worried to be hacked!

How to prove for D?

I think in most case the number will be (odd->)even->odd....->odd.

But when $$$n=2^k$$$ it is special.

yeah, in particular when $$$n$$$ is odd, Bob has a symmetry strat (always pick the same divisor to subtract that Alice does, and things work out bc of parity)

I wrote out a proof here: https://codeforces.com/blog/entry/91835?#comment-805791

I solved E (E1+E2) using 2 Pointer approach. 119902053 Edit :- Got WA on Test 93, Weak Pretests :(

why didn't you just

``n=min(n,k);``

instead of``if(k<=n)do(k);``

`else do(n);`

A lot of plagiarism happened in Round; Many posted solutions on youtube. Better to make round Unrated.

give link

After seeing this comment, I searched and look what I found https://www.youtube.com/watch?v=e9i8c6JKmXs here you go :)

Went through the linked video, the guy is an absolute legend

This guy trying to hide his username be likexD

This is the solution video of problem A which was uploaded when the contest was still running. Link

The user goes by the name Blunder_AY and his submission for the problem A can be found under 119812636

Then every round will be unrated :(

Missed E2 by 1 sec :(

How to solve D ?

i actually wrote a recursive solution and then i could see the pattern of even odd.

Next i just validated for even odd. Found that for power of two that are odd , answer is false.

Hope that helps

SpoilerResearch again ) Nice approach.

meet a new cheater This is how kedos123 bypasses Plagiarism testing.

I am watching him from so many contest , He has done this today and in previous contest, and I am sure he must have done it multiple times before as well. People like kedos123 are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible . MikeMirzayanov sir pls ban him and skip his solutions .

todays submission[submission:119865102] 119855748 saw his submission time vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++; vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++; vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;vikings++;bb--;vikings--;bb++;

Biggest template I have ever seen

Looks like he took the template of every LGM (including Benq, he has a huge template) and mashed it into one.

hello kedos123 , everyone ask about you code snippet , can you also copied it from somewhere ..... lol mf

What's the idea behind E2? Can it be solved using Z function?

Rolling hash with binary search got me pass the pretests

I used same idea for E1 and E2. I just checked for the character which exceeds any character in the prefix.

Was the TL for E2 really tight? My O(N) soln kept giving TLE on case 12.

https://codeforces.com/contest/1537/submission/119909827

Try this input: 50 100 zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfeda

Spent 1 hour on B due to my stupid mistake . It was a nice round

Can E2 be solved without suffix array??

I solved it without suffix array. Waiting for the system test.

Can you please explain your solution?

I took a random string. Let's say-"pabccepabcdf" I ran a loop over the string length. At the instant, where the character is greater than the 1st character ("p" in this case), I printed the string till the last character. At the moment, the character is equal to the 1st character, I checked further characters, if any of them is greater than the corresponding character in the prefix of string, I printed the string till the point I found a matching character for the first character.

For example:- In the example, I have taken, the moment I found the 2nd p, I started checking the further characters with the corresponding character in the prefix. "a" with "a", "b" with "b" and so on. I found that in the d in pabcd is greater than the corresponding c in "pabcc". So, I stored the prefix "pabcc" and printed it required number of times.

UPD: It passed. Submission

So overall you figured out that "pabcce" is a better prefix than "pabccepabcd" and then you broke the loop.

But what about the prefixes in between this matching window? "pabccep", "pabccepa", "pabccepab", "pabccepabc" Why are you not comparing with these as well? to figure out the best prefix in this window

"pabcce" is lexicographically smaller than "pabccep".

In this case, yes. But you are not comparing these prefixes in your solution in general(you are just ignoring them). I guess there is a way to prove that all these prefixes will not lead to a better result as compared to the current prefix.

Yes, it can be proved that those will not lead to a better result. I can't give you formal proof but I will try as much as I can.

It is sure that there isn't a character greater than "p", else we would have used

`break`

and printed the loop with prefix just before that point. So, those prefixes must have a second occurrence of "p". The character just before "p" will be surely smaller than "p". So, that prefix will be lexicographically smallerProblem D have some ideas in common with a problem which was part of the recently first round of the Tournament of Towns Mathematical Olympiad

Moreover! Problem D was Problem 6 Argentian TST Cono Sur Mathematical Olympiad 2019

D is very similar to MIT PRIMES 2019 G5

Even the names are the same...

AE1BE2DC would have been a nice ordering (for me, at least).

I think that's weird, isn't it?

A,C,B,E1,E2,D :')

Ah! That hurts.

In B, we just had to print

1 1 n m:)Oh, I checked for (1,1), (1,m), (n,1) and (n,m) :'(

It was a cool round.

Sometimes Java is worse.

problem C . I used LinkedList. Costs me TLE . like seriously dumb Changed to ArrayList and AC . lol

Problem D . Create a set of long for checking powers. Got WA — because i was comparing int with the long values in set Took me hell lot of time to bebug what went wrong

Good problems. Sadly i coudnt perform well :(

Only solved A T_T

Get the logic of C but TLE, my approach is sort the array in ascending order and rotate the array while the next rotation make |H1-Hn| minimum.

E is a standard application for Z-array.

i tried using lps as in KMP, by i guess was missing some cases.

Try to append z character n times in the given string and then apply the same thing. This worked for me but I used Z algo.

My Sol. for B is (1 1 n m) But i see large codes of ppl?

It's correct,

how? can you please explain?

The maximum number of steps would be 2*[(n-1) + (m-1)] (first testcase was a hint). No matter what the starting position is, If the yo-yo's are at (1,1) and (n,m), You will always get maximum number of steps.

Proof-

There are only 2 ways

1. (i,j)->(n,m)->(1,1)->(i,j)

2. (i,j)->(n,m)->(i,j)->(1,1)->(i,j)

Calculate the number of steps for these, you will always get maximum number of steps.

brilliant thought process!

How did you think of or get 2*[(n-1) + (m-1)]. Sorry to ask but i am a newbie.Also thanks so much for the solution. I get it.

During the contest, I thought of the following problem-

In a n*m grid we have to go from point A to B and then come back to A. Maximum number of steps would be 2*[(n-1) + (m-1)] for A=(1,1) and B=(n,m). This is very clear I guess.

Now if I throw in a point C in between, you can see (1,1)-C-(n,m)-(1,1) will always return in 2*[(n-1) + (m-1)] steps. I then verified the claim against sample test cases.

Thanks a lot!

same as my solution! it also can be n,1 and 1 , m it will also produce same answer.

After bricking C and getting it in the last 4 seconds, read D. These alice and bob problems always get on my nerves. Any suggestions on how to improve on game theory?

Lol same, im not too good in game theory but here i just brute-forced and coded the pattern

can you please share your core on brute force -><- I tried writing it but i'm not getting the expected output. Edit: got it :)

In problem C, what should the answer be for the test case below

Given =

`1 1 3 3 6 6`

Shouldn't the answer be

`3 6 1 6 1 3`

, coz the absolute diff b/w first and last is min`=0`

and also the difficulty level is`3`

1 3 3 6 6 1

My bad, i didn't count the equality.

It becomes tricky if the author changes the condition from

`h[i] <= h[i+1]`

to`h[i] < h[i+1]`

.Then for the test case i mentioned, your sequence will give

`difficulty = 2`

whereas mine`difficulty = 3`

. Am i sounding naive ??Yeah, I made the same mistake. I was trying to solve the h[i]<=h[i+1] problem.