Henlo Codeforces!

We are very glad to invite you to the Codeforces Round #754 (Div. 2), which will be held on Nov/12/2021 17:35 (Moscow time). This round will be rated for participants with a rating less than $$$2100$$$. For higher rated participants, we challenge you to solve problem F ;)

All the problems were authored and prepared by Ashishgup, the_hyp0cr1t3, ExplodingFreeze and me. We have tried our best to create an interesting problemset with clear statements. Hope you enjoy the round :D

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

We would like to thank:

antontrygubO_o for his amazing coordination and help in improving our problems.

Our army of testers: Um_nik, mhq, Monogon, _runtimeTerror_, Jeel_Vaishnav, AmShZ, errorgorn, ijxjdjd, Utkarsh.25dec, Dragnoid99, yash_daga, Vivek1998299, taran_1407, MagentaCobra, Retired_cherry, sinus_070, AC_007, talibmohd, KahanHai, Dragonado, Submit_Galactic_Algo, KeyurJain, tvcv901, ekanshi, Jellyman102, jimmy18, inferno14 for testing the round and providing valuable feedback.

MikeMirzayanov for the Codeforces and Polygon platforms.

**Good luck!**

Here's the scoring distribution of the round:

$$$500 - 1000 - 1500 - 2000 - 2500 - 3500$$$

**UPD**: Editorial is out

Also, congratulations to the winners.

**Div 1 + 2**:

**Div 2**:

Fuck off!

INDIA WALE MAA CHOD DENGE ISS ROUND MEINCKMKBCKMKB PKMB

PKMKBDamn an Indian Round, super excited for this :)

A round by Ashishgup to break the drought, I am excited!!

As a tester, I can confirm that problems are simply amazing.

Is it going to be tough ?

memeThey still have us in the second half

Codeforces round after a long time, sadly I can't participate due to my exam. :"(

All the best for your Exam

True,these exams are really giving us hard time!

skip your exam

SSC Exam Bro. :((

ok then come back after SSC.Good luck

Meme ;-;Fun FactIf they have added a newbie tester then testers army would have testers from every rating range

Then, if you could choose, who would be the newbie to also participate in testing?

I would choose you if someday I make a round but for that I need to be assured first that you won't leak my problems otherwise tdpencil or sus will be others whom I will approach

I guess I promise you I won't leak any problems for any contest that I test, not only yours. I would also be interested what problems you could come up with, it would probably take much creativity to get an original problem(Since there are already 1.6k problems).

You just competed 3 times and you already want to be a tester

To make it a bit fair for me, I've started coding with a bunch of different coding languages since at least 4 years ago

worse

"Brace yourselves for WA on pretest 2"At least we can expect strong pretests

Probably, all the problems have only two pretests...

or maybe, we have several pretests but the second one goes hunununununununu….

As a tester, the statements are short and the problems are great.

Finally...

Problems prepared by ashishgup, this round gonna be interesting

Incoming game theory problems!

Looking forward to this !!

Excited!!!

Now I dont care about rating. Let me see WA on pretest 2

"WA on pretest 2"no doubt problems are prepared by Ashishgup.As soon as i get better at coding, I'd like to test out these problems too. I like the creativity in each of the 1.6k problems up until now! (Yes it is considered creative even if it looks like one of those math problems from school)

Has this round the strongest second pretests:)

After a long time finally a div 2 contest .

With Ashishgup as problem setter, we may expect some problem on turn-by-turn game (Source: 5 out of 7 of his contest has such problem).

You are right

Prediction successful ,Orz

Ashishgup as an author, me ready to brick whole my contest on div 2A :P

Contest after a long time, Looking forward for it!

rainboy be like : challenge accepted! i'm gonna solve F first.

Hope i'll solve the problems in this round :(

well Good luck to all

Game theory problems loading

Finally another Ashishgup round!

(waiting for a constructive and a game theory problem)

SergiuS2003 will win the round

hoping to be green in this round

hoping to be green in this round

Good luck

Waiting to be downvoted on this comment

join me. reject cyanity return to green.

I did my best but only managed to get -18

hoping to remain green after this round

As a tester, I can confirm that the questions are really interesting and diverse. And Ashishgup rounds are always fun! ;)

upvote for the image

Hoping to make a comeback through this round !

All the best to everyone!

only mfs downvote

"Brace yourselves for WA on pretest 2", nothing new for me), haha

Hoping to get some increment in rating, too excited

Lets see which Game are we gonna Play in this Round !!

I haven't had a positive delta in any Ashishgup round. Let's hope for a change in this one.

I hope you reach master in Ashishgup's round :)

The legacy continues...

Lol

In this round also, Ashish : 1 Priyansh : 0 hehehehe..........

Oh jesus, I am nervous. I'm only 27 points away from expert, I hope I can get them tomorrow.

I wish I could be green...

1 upvote = 1 less

WAon pretest 2Liked it only because of Ned Stark)

worrying :(

WR :(That image actually indicated that we can expect strong pretests

Hope that I won't choke again in an Indian round

.

you can downvote this also, cause you people downvote everything!

I am very excited to participate in this contest. Good Luck to everyone.

I am very excited about this contest. Hope so that everyone would perform well in contest. Finger crossed

Game Theory Problem for sure!

So many shitty memes in the comments of this announcement. Or it has always been like this and I didn't notice?

too many wrong answer on pretest 2 ngl

Spoilerplease don't do that again #(

speedforces

Participants whose Problem's solution got accepted in 1st attempt..( passing pretest 2)

Jury verdict after everytime I submitted solution C

i can see an avengers infinity war fan.

also an anime fan… XD

Damn True,....

Just one pretest of problem C was difficult, not difficult but out of context of our thoughts.... :_)

I believe everyone missed that Testcase for which the answer was 7.Sad

yes, that was a little distant from other

btw , u have an amazing username bro, XD

Lol,thanks! :)

我写不出来！

I had very high hopes of becoming green today but I could not solve problem B. So I didn't submit to problem A also as it would decrease my rating :(

https://www.youtube.com/watch?v=CbFNs_ZfG_U&ab_channel=LILSKOORB

F**k Div 2 Problems A

A is a bingo problem (a+b+c)%3

"For higher rated participants, we challenge you to solve problem F ;)"5 minutes left in round completion. No one solved F. Where is rainboy when we need him :')

Is F O(N^5) dp? I feel like i moreless got the idea, however it's impossible to implement. Maybe I'm completely wrong.

Thanks for the round and F is really challenging, Waiting for the editorial!

You don't really think I can't fight fakes, do you?

I am sorry but problem E requires no thinking at all. I wonder how this got accepted...

Also, should Problem F be in a Div2 contest? Even LGMs can't solve it, while 2Fs should have at-least 20-30 solves.

I think problem F was there only to satisfy their ego.

yeah E can be solved by looking at the pattern only, which feels wrong for div2-E.

How to solve problem C in O(n)?

The length of the substring is bounded by 8.

Can you explain how you made this observation?

First, lets understand that if there is aa, so answer will be 2. Then if this up statement does not work in our string, then we its obvious that i, that s[i] == 'a' are at least at distance > 1, because first statement doesnt work. Then lets see what we can get from here. We can see that if there is s[i] == s[i + 2] and s[i] == 'a', either way it will be our answer. Then lets find another case when there is something like that abca, acba answer will be 4 there. If these all cases doesnt work, then i that are equal to 'a' are at least at distance >= 2, and if we think little bit we can see that we have abbacca, accabba. Thats all. Sorry, for my bad english and may be bad explanation

How is an len=8 substring possible? For me its bounded at 7.

Same. Can the answer be anything other than 2,3,4,7,-1 ?

I kind of just searched these substrings.

Link to my submission

By bounded by 8, I meant < 8.

Wowww, you have progressed so much when we last talked.

There are only 4 cases: 1. aa 2. aba 3. abca 4. abbacca

And you can prove that if the gaps between the 'a's are greater than 3, then it is impossible to get a good substring.

tks everyone :|, I solved problem C :D

oh bummer, I didn't think about the 4th case. Seem to pass now that I added a few more if statements, thanks.

you can observe that you need only 1 operation, or none at all if it's already sorted, let's call X the number of 1's in the string, it's a binary string so you can tell if it's sorted by looking at the last X bits if they are all 1's then it's already sorted, if it has zeros then we choose those zeros with the ones that are not in this group. 0001111 (it's sorted because the last 4 digits have 4 ones(all of them)) 00110101 (here we can say the last 4 digits has 2 zeros in them, so we take those with the ones that are not included)

*if it's not clear 0 0 1 1 0 1 0 1 the last 2 ones are already in place (no need to do anything), the last 2 zeros need to be replaced by ones, the first 2 ones are the ones(all that is left) to be replaced it will always be non-increasing because the ones that we choose are always in the front

I dont like very much that style of problem statements, where there are a lot of details explained, and then in the last third of the text some more or less related question is asked.

Better give a first sentence to understand the idea of the problem, then come up with the details.

I rather prefer this type

I think they could just highlight the most important words

For problem D, was the idea based on placing numbers according to their most significant bit (using the fact that a tree is bipartite)?

at the starting of system tests everyones A failed system testing ...

For D, the final idea that came in my mind was that we will try to end the game at every node itself. Which summed up that there cannot be neighbours with their MSB equal. But no clue how to solve this construction. Any hints?

Yes, the idea is correct. We can try to end the game at every node. For every node, try to make sure that all neighbors have an unequal MSB.

Color the graph white and black (such no two nodes are the same color).

Notice, number of numbers with MSB at Position 0 = 1, number of numbers with MSB at Position 1 = 2, number of numbers Position 2 = 4, and so on.

Let number of white nodes be w and black nodes b. Consider min(w, b). Consider the binary representation of min(w, b) For now, assume w<b. Let's say w=5. In Binary it is 101. So take numbers with MSB at position 1 and 3, and use those to color the white nodes. Use the remaining numbers for black nodes.

How to solve problem B ?

I thought of a O(n) solution but couldn't solve it.

Then I later saw that that n<=1000. By that time 1hr had already passed so I gave up :(

find the

`1`

s that are in the wrong place.This was my idea of D —

First, the condition u^v<=min(u,v) meant we can only go from u to such v that their MSB is in same position. Eg 4 to 5 ,6 ,7 etc. Then we need even path lengths (length = no of edges) to make those nodes optimal. After this I was kinda stuck. Is this approach correct?

P.S I liked C. Nice observation required.

rip rating -122

spammed 1.5h on C and wrote a BIT and a monotone stack. nothing worked so I got frustrated and started writing garbage. HA HA HA HA HA HA!

I tried to submit some curse words but the contest ended :(

good problems though. My bad. D was pretty okay, but I didn't solve it on contest :(

for almost 1 hour i was thinking that In problem C ,they were asked to find largest string

I abandoned my ape instincts and spammed submissions.

Loved problem D !

what a problemset. take a bow lord Ashishgup

Question F is so strange that I thought of three false algorithms!

And now i have delta

-108instead of-3:(sad :<

orz

the answer will be smaller than 8, just look at this string: "abcabca"

When will the explanation be available?

Where can find the Problem-solving ideas?

Can we use binary search in problem C?

int l=1,r=n; int mid = l + (r-l)/2;

Iterate over string to find if there is a valid substring having length mid. If this condition is true, then right = mid-1 else left = mid+1;

Will this approach work?

Probably you will be quite surprised by this this solution.

No binary searching won't work. You can consider S = "aabbaa" for example. Substrings with length 2, 3 or 5 that satisfy the problem conditions exist, but there is no valid substring with length 4. The key to this problem is observation: The smallest possible lengths are only one of [2, 3, 4, 7] or -1 if there is no valid substring.

I didn't take that meme serious, and then...

sad short story :)

during contest:

https://codeforces.com/contest/1605/submission/135163837

after contest:

https://codeforces.com/contest/1605/submission/135174883

i had the case written in my paper but forgot to type it

Really nice D.

:)Congrats on CM!

lol

Sums up my today's contest.

Meme...

Problem C Editorial :- https://www.youtube.com/watch?v=EWhmvHCB19k

Problem C was a mess

if you couldn't solve problem C it doesn't mean it is a mess

why cheaters are not being removed either in this round and in past div3 MikeMirzayanov

Problem A should be rated at least 1200. Even though it's a one liner it takes a lot of effort for beginners to deduct the answer. Especially with weak mathematical background. Some of the 1200 problems are easier to solve just by working through the problem. The problem is very good but it should be rated properly. It's definitely not 800 and 900.

I had the correct solution of problem C when I saw it last night. However, due to some mistakes on coding, it took me one extra hour to work it out, which made my rank only 3000+, I should have been in the top 1500 :(

Thank you so much for making this round, really enjoyed competing.

I couldn't solve any problem

WA on pretest 2 was my close friend in this contest. I don't know why it didn't leave my side.

I want to know what the difference is between these two WA and AC

please help me

Thanks for such a competing contest :D

Problem D was nice I really enjoyed it while upsolving but it doesn't seems to be a 2100 rated problem