Hi, Codeforces!

I'm glad to invite you to take part in Codeforces Round #721 (Div. 2), which will take place on 20.05.2021 17:35 (Московское время). The round will be **rated for the participants with a rating lower than 2100**. Participants from the first division are also welcomed to take part in the competition but it will be unrated for them.

You will be given **2 hours** to solve **5-6 problems**. Problems were created by members of Club of Programmers IIT (BHU)- rivalq, sharabhagrawal25, loud_mouth, DenOMINATOR, Bignubie, mallick630, shikhar7s, CoderAnshu and Me.

Huge thanks to those who helped make this round possible:

- Aleks5d and KAN for their excellent coordination and for providing priceless feedback during contest creation.
- 1-gon, ajit, kassutta, namanbansal013, Qualified, 4qqqq, Ekler, Rajdeep, m371 and rkm62 for testing and providing invaluable feedback.
- MikeMirzayanov for Codeforces and Polygon platforms.

We tried our best to create interesting problems and simple-to-read statements and we hope you have fun! Happy coding :)

**UPD**

Scoring Distibution:- **500 — (750 — 1500) — 1500 — 2250 — 3000**

**UPD**

**Congratulation to the winners**

**Global**

**Div2**

**UPD** :- Editorial

Hope this won't be similar to the math contest that was prepared by you guys (IIT BHU) earlier.

deleted

No JEE maths please

Yes please!.please No trigonometry,geometry only based problems or maths exam like that bad round.

This time it's a case-based round lol.

Seeing MEX in D, I don't think B1, B2 were meant to play this way.

A contest by Indians after such a long time! Very Excited!!

IITians !!

As a tester, I want contribution. Problem set is great.

How about some negative contribution?

It's totally your wish!

This round may become a disaster as kassutta is a tester

well you got it ¯\_(ツ)_/¯

op

why downvoting here, what is so wrong in the comment, It Is still not edited, that it looks absurd here. This is the problem with the CF community . Hope these downvoters or haters realise it.

Nice work COPS-IIT BHU team.

Happy to take part in testing for the first time!!! As a tester, I recommend you to read all the problems.

C was easier than both B1 and B2. Probably C should have been B .

I cracked B1 and B2 but was not able to solve C.

How you approached C ?? I was struggling with both B2 and C :(

That's why I gave that suggestion.

yeah thanks :)

I think different problems worked well for different people. I got A, B1, and B2, and I ran out of time on D, but I didn't know what to do for C.

You can think about each pair（i,j）(i < j),which satisfied that a_i = a_j,then,it can denote to answer (n — j + 1) * (i + 1) So you can used MAP from left to right,let f[u] denotes the sum of (n — i + 1),(a[i] = u),and add (n — j + 1) * f[u] to answer when the element a[i] you now deals equal u (I'm sorry that my English is so poor)

your's explanation is pretty nice as it compelled me to think in right direction. Thanks!!!

As a tester the problems were great and I recommend everybody to participate.

Since, Qualified has given his stamp of approval, the contest is Qualified to be a great one.

Qualified orz !

Yes that's Why this is my last comment as PUPIL...Bye Bye PUPIL

omg Indian round

As a tester, I wish you good luck!

I hope the round is nothing like your username.

God knows :p

For me it was.

Hope to become pupil this time...

vashuchauhan9897 Congrats you did it.

Your rating graph is quite motivating!

Well not a great results but I will keep trying I started well at the beginning and could reach expert but then bad stuff happened and I completely stopped practicing because of that now I should be able to improve I think

Wishing you luck for today's round.

I think, somehow, you and I have the same situation. I peaked Expert 3 times in 3 different years. But I stopped for a period of time. Do you think that Codeforces problems are more and more difficult? SupaHotFire

I think we used to try harder .. when I first started I would sit and think about a problem for hours now I am not like that... I don't think contests became harder there are so many people I know improved their rating a lot so it's our fault we should just try harder as before

Hang in there! I added you as a friend. See you again in Blue or Purple.

I predicted the future

Press F

Kudos to the team for compiling a much awaited contest for us. I hope that the problems are indeed as simple-to-understand as they are to-read. :D

gyrating cat UwU

Kudos to the team for compiling a much awaited contest for us. I hope that the problems are indeed as simple-to-understand as they are to-read. :D

Hope everyone who read this comment(also me) have a rating increase in this contest

Why isn't HealthyUG part of problem setters team.

i think he isn't part of that team that's why

I'm thrilled to take part in this contest. As it's prepared by one of my college senior of one and only IIT (BHU) Varanasi :).

[deleted]

https://ibb.co/n1qqWfg

Auto comment: topic has been updated by the_nightmare (previous revision, new revision, compare).[deleted meme]

Its a relative thing, if everyone was good, then cutoff for pupil would have been 4000 rating. Nothing more.

can you plz elaborate what cutoff ?? Do you mean to maintain delta rating to zero, as a pupil you need to rank at least 4000 in this contest ??

Can I become pupil?

y_e_s_w_h_y_n_o_t

oh welcome back indians setters

Cheater becoming tester for the round strange!

They even deleted a previous comment in which someone pointed this out

Yeah i think this round was prepared before the blog post came out. Else they will not have considered him i think.

i am not aware of what is going on. Mind sharing some details. like which cheater. you know u can always drop a personal message if u don't wanna share here

Maybe he has already leaked some of the problems in his groups!

Everybody deserves a second chance don't judge him like that

Edit: after reading the blog I changed my mind ..making a YouTube channel and telling people to not cheat then do such a thing is a shame .. I thought it was just a one time thing and he won't do it again

Who is it?

kassutta

https://codeforces.com/blog/entry/90230

Whenever there is an Indian contest Every Indian Contestant

I hope this Indian contest to be great the same as the greatness of the Indian educational videos on youtube that saves us in the nights of the quizzes XD

others: u need css to make websites look good.codeforces: hold my html links..People (companies) who are good with CSS, are not doing that good except for good promotions..

If you know, you know:)Better & Strong System Should be there not always CSS done their work.

[deleted]

I can't wait! Good luck to everybody!

WowGood！Regardless of the difficulty of the question, I really expect this "simple-to-read statement"!

All the best everyone, hoping to learn some new concepts.

As a participant, I will read all the problems.

And I would try to solve also! :P

I hope this time its a codeforces round and not a jee round

IIT BHU giving the best coders of INDIA. One of the best Example HealthyUG sir.

Not saying about college. I know its there own hard work.Just telling the fact That most best coder of India are from there

lol college is doing nothing for good to student atleast in India,its all about their own labour and btw HealthyUG dont even felt good to join college coding club cause he know colleg club is also good for nothing ,they are one of best cause they have done labour,Dont give credit to Indian colleges ,they are just big names from which noone learn thing of their own benifits

Talking about colleges in India, it's okay if they do nothing for students to improve their skills. But there are some colleges (like my college) having too many assignments, classes, vivas and exams and there won't be much freedom.

Indian Round,excited❤️

Best of luck to all the participants :)I am expecting lot of combinatorics because IIT.

Strange 1-gon did not ask for contribution this time :( Feeling unlucky already :((

1-gon never asks for

contribution, contributionasks for1-gon.1-gon > gyrating cats.

Zlatan Agrees...

Hope I become a pupil this time

All the best...Fateh karo laksh ko!

Any update on scoring distribution?

UPD: addedI hope I can solve only 2 problems...as a newbie...

hope I can solve more than 2 problems this time. hope you achieve your goal.

thanks bro

Will B have a subtask? Asking due to the scoring distribution?

There are 5 problems, One problem has been further divided into subtasks

by looking at the number of people who registered , reminding people that you would have to use m1.codeforces / m2.codefores / m3.codeforces

Hope this round don't become like that previous div3 round(10 mins queue time)..Let's hope for best..and All the best to you

Thank you!

what are subtasks? can anyone tell

Scoring Distibution:- 500 — (750 — 1500) — 1500 — 2250 — 3000

means 2nd question has 2 sub task ...750 and 1500

basically they are the same problem with different constraints

Subtasks are like The problem statements are almost same, there is one easy version and one hard version of the same problem. They can make the problem harder by changing the constraints or adding more things to print out etc.

Second question having a subtask seems scary.

Maybe it's combinatorics :o

Hoping this tym my rating will increase a bit.

Bruh, what is going on with that scoring distribution.

i can not register please . help the_nightmare

sorry, can register after 10 min

:|

Are these guys MATH FREAKS?

Yes, actually. You have to be above average in maths to get IIT BHU

Aren't you supposed to be Mr. Incredible?

"Math is Math" — Mr Incredible , 2018

I m trying to be incredible

Goodbye Specialist.

For me goodbye Pupil..

Goodbye expert ):

Goodbye codeforces!!!

Welcome specialist!

Welcome pupil!

Welcome expert!

rainboy orz !

There is not even a single question having tag "Maths". Idk how have you found maths in the contest.

Problem C was combinatorics

Fight hard till end. Other option would be still valid after contest

Whoever prepared problem B2 is an evil person

it took me until 1:59 to solve B2. I was planning on at least tackling problem D when I first saw the scoring distribution lol

yeah, I too solved it in the last 30 seconds...

I suggest that every writer's first contest should coordinated by Anton in order to improve the quality of the contest(and avoid boring or classic problems like D,E).

And other coordinators should learn how to reject some problems?

Can you explain how to solve D in detail?

I thought I would become expert today :|

Same.

My reaction after knowing the solutions is like your profile picture

Quite unbalanced problems

Lol, $$$B$$$ is harder than $$$C$$$, $$$D$$$ and $$$E$$$.

Are $$$C$$$, $$$D$$$ and $$$E$$$ known Algorithms/Ideas?

I managed $$$B$$$, the hard one could be solved with straight forward

game theoryanddp(was a bit ugly to implement though. The dp depended of 4 variables. 1. The amount of zeros coupled with a zero. 2. The amount of zeros coupled with a one. 3. Whether there is a central 0 in case of n odd. 4. Whether last turn a reverse was performed.).But for the love of God, I couldn't come up with anything for $$$C$$$ and didn't get to think about $$$D$$$ and $$$E$$$

$$$E$$$ is D&C DP optimization

$$$D$$$ is case analysis + implementation

$$$C$$$ is just easy and described somewhere below

E has a much simpler solution involving segment tree range updates. D is tree traversal and basic analysis on it C is simple, just think about the contribution of each element in the answer. The detailed solution will be given in editorial

Can you explain Soln of D in detail?

Ok, now: I finally did implement $$$D$$$: 116963680. And I absolutely positively can say: There's no way I would've managed this task in the contest. It is just plain more difficult than $$$B1$$$+$$$B2$$$ for me.

I thought about the task yesterday in the evening and did come up with a solution. I sat down today implementing it: there were so many cases and implementation details. I did two logical errors which I had to find and fix (the message "wrong answer 1923rd numbers differ" on test case 5 (!) nearly gave me a heart attack. How was I gonna find that?). And the editorial doesn't look much simpler to me.

So I state $$$B<D$$$.

Spoilertotally for me at least :) And I guess thats ok. People learn different stuff. I had a game theory course once. So I guess $$$B$$$ was like "sure! ideal gamestates and transitions, let's make a dp out of it!" for me.

I don't know if it's too much to ask for, but I simply can't spot anything wrong with my solution for C. Please do have a look, chief

SpoilerYou have a really minor error.

The sz is wrong. It should be:

See 116995339

Thanks a lot and shiiizzzz (sorry for the trouble)!

C has a common idea with many "over all subarray" problems. Instead of counting weight of every subarray, you can count amount of weight an element adds to the final answer.

Then it was just some mathematics to calculate the number of subarray an element contributes to.

Keep track of index of each element, say $$$1$$$ occurs at indexes $$${1,5,8,10,...}$$$, then the contribution for this can be calculated as,

Well funnily I already did split the indices into seperate vectors. And I tried to do some dp then, by somehow counting the amount of "subsequences with n times the same number".

It just wouldn't come to my mind searching for the pairs only. With your hint implementing it was done in 5 minutes. Oh well! Thanks! :)

I agree. I solved B at the end of the contest.

I also solved B2 in the last 30 seconds. Overall, It was a good experience.

I hope everything passes system tests. Fingers Crossed.

How to solve E?

Bruh how to solve C ?

how to solve C?

116826819

i am getting TLE on pretest5

For any

`(i, j)`

such that`a[i] == a[j]`

, number of subsegments that contains the pair is`(i+1) * (n-j)`

. This is basic idea and then we need to optimize our code, check my AC submission.Optimization->I used Hashmap (

`unordered_map<int, vector<int>>`

) through which I add all the indices in a vector where the values are equal. For eg-> let's say in`a`

of size`n=10`

, value`3`

is at`{0, 2, 4, 5, 8}`

.Now using the above expression => let's say

`j == 5`

then subsegments which have index`5`

and`one of any previous index(0, 2, 4)`

in it are =`(1 + 3 + 5) * (n - 5)`

and this is where we can use prefix sum and get time complexity of O(N).thanks

Can you please explain how you get to (i+1)*(n-j)?

Edit — Nevermind got it. I misread subsegment as subsequence!

let i = 2, j = 6 and n = 8. then every subarray with start as any of

`s1 = {0, 1, 2}`

and end as any of`s2 = {6, 7}`

will contain the pair. Ways of choosing from s1 and s2 = 3 * 2.Consider the array indexed from $$$0$$$.

Any range that starts at $$$i$$$ or before it and ends at $$$j$$$ or after it, has the pair $$$(i, j)$$$. There are $$$i + 1$$$ possible left endpoints and $$$n - j$$$ possible right endpoints for the range containing $$$(i,j)$$$; thus the pair $$$(i,j)$$$ is inside $$$(i + 1)\cdot (n - j)$$$ ranges.

how are the number of possible right end points (n-i) ?

Sorry, that was a typo. I’ll fix it.

Can you explain what is the prefix sum for and why do we need it?

I don't get what you're asking. I don't mention prefix sums at any place in the above comments.

https://usaco.guide/silver/prefix-sums

thank you

We will soon upload the editorial for the contest.

how long is this soon exactly ?

SOON

Very soon :D

This contest was a nightmare for me!!

I could have become expert if i had not made the silliest mistake on problem A which will make my solution pass the pretests but will fail at higher values.

i used log function which gave wrong answer

Simply,take the n-1 value where n is the number which has the most significant bit only.

## include <bits/stdc++.h>

using namespace std; int main() { int t; cin>>t;

}

Coordinators should take the blame for not rejecting this shit.

I didn't like the problems at all. A and B were just stupid observations. Also, difficulty of C was probably overestimated.

You wanna see observations in problems though. Those observations are nice.

They should've swapped C with B though.

Well they aint gonna take the blame anyways. You know the contest will be a gamble when you see B to be worth 2250 points.

Feeling sad with many many others.

Why DP failed on problem C. State:

`dp[i][j] = weight of subarray from [i,j]`

Transition:While adding the weights of every subarray.

Submission: 116828863

Considering the range of values can be 2x10^5 using 2-D dp may not be a good idea IMHO.

Can you give some idea on how to solve it?

I don't want to give a spoiler here :) But here are some hints based on my solution:

Hint 1if at position i, you kind of know all the previous positions with value a[i], then you can actually calculate what i contributes to the weight sum.

Hint 2Suppose one previous position of value a[i] is j, i.e., a[i] == a[j], this pair will be added to all the segments (a, b), where a <= j and b >= i.

Hint 3try to make the dp associated with the value instead of the position.

Thanks, I'll try. _/_

the answer can be very large so change int to long long. Also i don't think your (N^2) will pass the time limit restriction.

Although this is O(N^2) and won't get AC.

`dp[i][j] = 1 + dp[i+1][j] + dp[i][j-1]`

, if I am correct, this will count weight of (i+1, j-1) twice in dp[i][j].it can be

correct me if I am wrong!!

I did it without dp, submission

I did exactly this it was showing runtime error on 5th test case yeah I got my mistake tho you cant generate a 2-d array of 10^10 size

.

How to solve B??

Here is my solution. Let's call $$$f(i)$$$ to the symmetric position to $$$i$$$ if we take the center of the string as symmetry center.

Now, the state of the game depends on:

`s[i]=='0'`

and`s[f(i)]=='1'`

. Let's call this $$$C_{0,1}$$$.`s[i]=='0'`

and`s[f(i)]=='0'`

. Let's call this $$$C_{0,0}$$$.reverseor not. Let's call this a Boolean variable`rev`

.`0`

or`1`

, (if the string's length is even we consider it as a`1`

). Let's call this a Boolean variable`mid`

.`turn`

.So, the state of the game is the tuple $$$(C_{0,0}, C_{0,1}, rev, mid, turn)$$$

Now consider

`d = score(Alice) - score(B)`

. We can interpret the game as the following: Alice wants to minimize`d`

and Bob wants to maximize`d`

. So, we can have the followingDPsolution:$$$Dp(state)$$$: for the current state, if it's Alice's turn, what's the minimum possible value of

`d`

, and if it's Bob's turn, what's the maximum possible value of`d`

. The transitions are straightforward. The time complexity is $$$O(n^2)$$$, and so it's the space complexity. Since this Dp doesn't depend on the input string, we can precompute this Dp (or do it recursively with memoization).Now, for the initial state of the game, if

`Dp(state) < 0`

, then Alice wins; if it's`> 0`

, then Bob wins; otherwise it's a draw.caseforces xD

.

I blame

kassuttaI don't understand how you can speak so disrespectfully of the efforts of other people who have made significant efforts to prepare. Oh, I see you prepared a lot of rounds and they were all great. Sorry, no.

You probably didn't like the problems. You may not be alone in this. AND? people tried. The writers tried hard. The coordinators tried hard. Testers helped with testing. There were clear statements in the round, there were no mistakes in solutions and tests. You don't pay to participate. Enthusiasts put their energy into making you happy. They have failed to please you. Any set of problems — some like it more, some less. I urge you to maintain respect and express your criticism in a balanced manner and without harsh or offensive forms.

Totally agree with you!! Please don't get disappointed due to such comments, you have made the best coding platform for us. I am very grateful to have this free of cost.

Sorry for this comment, I was really impulsive that time.

First time solved 4 Qs in div 2! Practicing DP for the past few days really worths it.

from where are you practicing?

https://codeforces.com/blog/entry/90293 A great post

Problem B ruined the contest for me , I couldn't find any mistake in my code ,tried till the end but failed .:(

Problem B was more of a strategy question than a programming question.

Yeah it was an observation based question to be precise and a bit of game theory i guess but couldn't able to notice that during the contest xdd

Finally getting to 1500! Ideas for A,B1 and C :

ASimple observation. Notice 100000&011111 pair always give 0. So if we calculate highest power of 2 less than or equal to n and then set k to that power-1 then that will be our max answer.

B1If n is even then bob always wins because parity difference always favours bob and if n is odd then we need to check if s[n/2]=='0', if so is the case then alice can turn the odds in her favour and reverse the parity difference. Check for edge cases too.

CMake a map of vectors each storing a indices of a particular number. Then use contribution technique to find how many subarrays does a particular pair contribute to. If you calculate it then it will come out to be : $$$\sum\limits_{i=1}^{k-1}\sum\limits_{j = i+1}^k(n-c[j]+1)c[i]$$$ where $$$(c1,c2,c3,...ck)$$$ are indices where a particular number x occurs at. This can easily be done in O(n) using some prefix sum simplifications.

C-codeOn C if all the number are equal your solution is (N^2) and i dont think will pass the system tests

Nope its O(n) because the map loop will execute only once and the inner loop is linear.

you are right about that it shouldn't TLE ! I did the same thing as you and i got TLE in pretests. ;_; Really not sure what went wrong. https://codeforces.com/contest/1527/submission/116811751

I guess its because you are initializing vector with max constraints for every test case and also running loop till max constraints for every TC. Also I thought of doing coordinate compression like you did but then just went ahead typing fast and mindlessly took a map of vector lol.

You are right, it's the initialisations ;_; ;_; I'll cry myself to sleep now ;_;

It happens :( try to stay calm maybe next time xD.

For B2 check the case if it is not a palindrome,then it will favor Alice completely, except in the case when the string length is odd with 0 at the mid position and the total number of zero's are 2, then it will be a draw.

Thanks! I was completely blanked by B2, was thinking of some dp with differences of scores of A and B then breaking down into some transitions, but got me nowhere. I wonder if there is a dp solution to it.

dp solution to B2 by awoo solution's link

In B1, for the case "100001", n is even but I think it is a draw.

Alice Move- 101001 Alice-1 Bob-0 Bob Move- 100101 Alice-1 Bob-0 Alice Move- 101101 Alice-2 Bob-0 Bob Move- 111101 Alice-2 Bob-1 Alice Move- 101111 Alice-2 Bob-1 Bob Move- 111111 Alice-2 Bob-2

Nope because

0000 -> A***

1000 -> A**B

1001 -> AA*B

1101 -> AAAB

1111 -> All 1's break

so Alice score is forced and is 3 and bob score is 1. So bob wins.

Thanks!

Can't Bob reverse the string after alice converts first 0 into 1 since its no longer a palindrome?

Reversal of the string doesn't have any effect on the game as we are trying to turn the string into a palindrome.

The second operation is just a dummy move.

One winning scenario for Bob:

100001 (Alice +1) 101001 (Bob + 1) 101101 (Alice + 1) 101111 (Bob rev) 111101 (Alice + 1) 111111

Final : Alice 3 Bob 1

Yeah missed this :(

Please check this submission :- https://codeforces.com/contest/1527/submission/116820959

badly missing antontrygubO_o.

Strongly agree. My favourite coordinator (he also was the coordinator of my previous 672 round too).

D and E are boring ,and B is hard .

How to solve E? Couldn't get any idea for an hour.

$$$dp[i][j]$$$ is the answer of dividing the first i elements into j segments .

And use a segment to maintain it.

Works in $$$O(nk\log n)$$$

you can do the same dp but with DC

DC?

nvm got it

How to calculate the range cost in log(n). can you explain?

Extend right endpoint r.

When r+=1 , find the last position $$$i$$$ that $$$a_i=a_r$$$.

And the cost of $$$[l',r]+=r-i+1,(l'<=i)$$$,and $$$[l',r],(l'>i)$$$ doesn't change .

Use a segment tree to find the minimum element in a range.

Holy smokes, what a nightmare.

Nice problem D! liked it.......

For E, I wonder how calculate cost(i, j) fast? Got tle in case 13 due to n^2 init

I got accepted in

O(n. Take a look at https://codeforces.com/contest/1527/submission/116859222^{2})understand, the same divide & conquer dp, with second dimension compress a bit. nice idea.

Divide and conquer dp is a bit overkill for this I thought.

My solution went like this: int ans = 0; First we will store cost(1, i) in DP[i] for all 0<=i<=N. DP[0] = 0 ans = DP[N]

Now we will do the following sweep (K-1) times: Keep a RMQ (min) segment tree. Initially, the array represented by the segment tree at index x (1<=x<=N) stores DP[x-1]. Now, we'll sweep from left to right. Let prev(x) denote the maximum i such that i<x and A(i) = A(x). When we reach index x, we will add (x-prev(x)) to range (1, prev(x)). We will update DP[x] to min_query(1, x) now.

After each time we do this, we will update ans to DP[N].

It's easy to see why this works.

Submission link: https://codeforces.com/contest/1527/submission/116857074

delete

I think it is n*k*logn*20 ？ standard d&c dp with 20 to calculate the cost for each necessary state

oh,sorry.

Yes, you're right. It's

O(nfor pre-processing the cost matrix and then^{2})O(n * k * log(n) * 20)for calculating the minimum cost partition.The

`20`

is needed because we can't storeO(nvalues within the memory limit. We could compress it further to reduce it to^{2})`10`

or`5`

but that is not required.I see that many people in problem B have checked if count of '0' is odd and not 1 then its alice . But I dont understand. lets say its of size 5.

1000001 (starting string)

1100001 (alice = 1 , bob = 0)

1000011 (alice = 1, bob = 0 )

1100011 (alice = 2 , bob = 0)

1110011 (alice =2 , bob 1)

1100111 (alice =2 , bob = 1 )

1110111 (alice = 2 , bob = 2)

1111111 (alice = 3 , bob = 2)

hence bob wins.

could someone tell me what I am thinking wrong

What if alice choose the middle 0?..then its alice who wins

oh ryt thanks!

Alice's first move is not optimal, she should try to make the string palindrome so that Bob cannot reverse if the next step. So the optimal first move is making the third 0 to 1. Then Bob would be bound to pay $1 as he cannot reverse.

Thanks!

1001001(Alice), 1101001(Bob), 1101011(Alice), 1111011(Bob), Alice's reverse, 1111111(Bob), Alice wins

Thanks!

If count of 0 is zero then Draw.

Else if Count of 0 = Even :- Bob Wins.

Else if Count of 0 = Odd, then 2 Cases :- 1.) Count of 0 = 1 :- Bob Wins.

2.) Else :- Alice Wins

It is given there is atleast one 0

Ok then it will not enter in starting if-condition.

Always go in else part & Game can never be draw.

1000001 (starting string) 1001001 (alice = 1, bob = 0) 1101001 (alice = 1, bob = 1) 1101011 (alice = 2, bob = 1) 1101111 (alice = 2, bob = 2) 1111011 (alice reverse the string, alice = 2, bob = 2) 1111111 (alice = 2, bob = 3)

Alice Wins. The strategy is as follows: If we have a string with number of '0' larger than 1 and odd, that means that the middle character is '0'. So, alice takes that first and then forces Bob to make a '0' into '1' every time. Alice will always place a '1' in the mirror of were Bob placed his so the string still remains a palindrom. In this way, when there is only one '0' left, the score is equal and alice can reverse the string and make Bob Lose. Hope this helps and you understood!

thank you much I was so confused in this test case.

That hot chick is your girl?

Yes, bro, isn't she beautiful? =)

yes, you guys look lovely together..<3

I think B1+B2 can be solved by greedy: denote

`a`

as the number of`0`

at some index`i`

such that`1`

at index`n+1-i`

; and denote`b`

as the number of other zeros. If`a = 0`

(here is the easy part): if`b = 1`

or`2`

then Bob Win; otherwise, Alice wins if and only`b`

is odd. If`a = 1`

: Alice wins except case`b=1`

(draw). If`a \ge 2`

: Alice wins.the most weird contest I have ever seen

The most stressful one as well, at least for me.

What is the idea for A ?

The first bit of

`n`

must be`1`

, suppose that it is on index`t`

from right to left, so in the expression, you need to have a number with bit`0`

at that position. And the maximum one is`011...1`

with`t-1`

numbers of`1`

.I overkilled it with binary search.

Spoiler...If N is a power of 2 then Answer is

N-1; Else Find the next nearest power to N(let's say K) and Answer isk/2 — 1;This worked for me I guess there maybe many more logics

how to solve B2? it's harder then E for me.

If the string is already a palindrome, then you can use your B1 solution and if not then ALICE always wins except in one case that is if the string length is odd and it has a zero at the middle and has only one position i such that s[i] != s[n — i — 1];

Can you explain the thinking/idea behind this?

Just tried all the cases on paper

SpoilerLet $$$f(s)$$$ be how many dollars you will spend lesser than your opponent if you start your turn on string $$$s$$$. The case where $$$s$$$ is not a palindrome:

Suppose there is a

`0->1`

move possible on $$$s$$$ such that you will win or draw from that. Then you can do that and hence, $$$f(s) \geq 0$$$. If every`0->1`

move is a losing move, then you can reverse and give the string to your opponent, Thus $$$f(s) \geq 0$$$ always. ie. Either Alice wins or draws.Suppose $$$f(s) = 0$$$. Then no matter if you can reverse or not, for any

`0->1`

move you make here, we have $$$f(s') \leq -1$$$ (Alice already spent 1$ on his first move), where $$$s'$$$ is obtained after the move, From the above para, this means all such $$$s'$$$ are palindromes,as otherwise $$$f(s') \geq 0$$$. This means $$$s$$$ has to be just 1 character different from a palindrome(and only one such character). This is possible only when either (i) $$$s$$$ is odd length and has just two`0`

s and one of them occurs in the middle or (ii) $$$s$$$ has just one zero. The (ii) case is extra and Alice can still win that. However (i) case will be a draw, and this is the only case where a draw is possible.Alice wins in all other non-palindrome cases.

Isn't Problem B misplaced? It should have been C or D according to the scoring distribution.

In B1 probelm who should be winner for 10000001 case and please mention the moves also

Bob will win. First, Alice replaces some zero, suppose that

`11000001`

. Then Bob does the same, replace by the opposite position`11000011`

. Continue for two more steps:`11100111`

, now each one costs`3`

and here is turn of Alice, she makes`11110111`

, now Bob just reserves the string, and Alice costs`2`

more than Bob.yep got it thanks

Bob Wins. (10000001) (position = 1 to 8)

It is palindrome with 6 0's.

In first move, Alice can choose any 0 (at position=i) then bob choose 0 at position (9-i).

Similarly happen one more time.

Then only 2 0's are remaining, then bob chooses some '0' and now string is not palindrome , then bob reverses it and then Alice again chooses some '0'.

yeah got it thanks for clarification

Whoever that is able to mirror wins. Example:

1001001

Alice does whatever: 1101001

Bob mirrors Alice: 1101011

Thus forcing Alice to not have the reverse option: 1111011

When one zero left, Bob does reverse and let Alice fill in the last one. Bob wins, in fact, if there are 2n numbers of zero, then Bob always wins.

If there are odd numbers of zero, Alice fills in the middle one, like 100010001, and wins by using the same mirroring strategy as the above example when Bob does whatever like 110010001.

got it thanks

The contest was amazing. I think the most interesting problem of today's contest was B2. Thank you very much the_nightmare

Video Tutorial A:https://www.youtube.com/watch?v=zTWpRUDk29U

Video Tutorial B:https://www.youtube.com/watch?v=PcuGtfPqLLQ

A recursion based solution for B2:

U = number of 0s in position S[i] such that position S[n-i-1] = 1 (call them 'unbalanced' zeros)

B = number of 0s in positions S[i], i < n/2, such that S[n-i-1] is also 0 (call 'balanced' zeros)

Mid = 1 if n is odd and the middle position is 0, otherwise 0

Rev = True if last move was a reverse, False otherwise

Then rec(U,B,Mid,Rev) is the minimum possible score from that state.

If U = 0, B = 0 and Mid = 0, return 0

Otherwise, let best = INF

If U > 0, best = min(best, 1 — rec(U-1,B,Mid,false))

If B > 0, best = min(best, 1 — rec(U,B-1,Mid,false))

If Mid > 0, best = min(best, 1 — rec(U,B,0,false))

If not Rev and U > 0 (i.e. not a palindrome), then best = min(best, — rec(U,B,Mid,true))

These are the only possible transitions. If the score comes out positive, Bob wins, if it's negative, Alice wins, if it's 0, Draw.

what will be the time complexity of this approach?

U <= N/2, B <= N/2, Mid is from {0,1}, Rev is from {0,1}.

The theoretical maximum complexity is N^2, but the constant factor reduction is very significant, since U+B <= N/2. Even if we ignore this bound, we have 500*500*2*2 states = 10^6. But we can also use memoization across the 10^3 test cases, so we will only evaluate at most 10^6 states over all test cases.

If not Rev and U > 0 (i.e. not a palindrome), then best = min(best, 1 — rec(U,B,Mid,true)) can u plz explain this?

Typo there. I've amended — apologies.

The line represents the fact that if the string is not a palindrome (U > 0) and the last move was not a reversal (Rev = False) then we can flip to the other player.

Can you please share your submission

Sure

Ignore the comments. That's me thinking during the contest.

great solution

why didn't I think abt recursion , it makes thinking so easier

Glad to see this, I also followed a similar approach. I took $$$\mathcal{O}(N^2)$$$ time to precompute the memo, and then answered all queries in practically $$$\mathcal{O}(1)$$$ time (apart from having to read and process the input strings, of course).

Submission link

Short explanation:

`coz`

= count of positions such that it's a 1 on the left side and 0 on the other (asymmetric)`czz`

= count of positions such that it's a 0 on both sides (symmetric)`coo`

(count of positions such that it's 1 on both sides) because participants can't play on those positions.`mid_set`

whether the middle bit is set or not.`mid_max`

— the maximum value the middle bit can take. it is zero if the middle bit does not exist ($$$n$$$ is even).`prev_rev`

whether the previous operation was a reverse operation.Note that all these parameters uniquely define the state of our game and the transitions that can be taken from such a state. I think now, the rest of the operations in the code are relatively straightforward. The total time complexity is $$$\mathcal{O}(N^2 + TN)$$$. Of course, this solution is an overkill imo :P

But, jimm89 why do you not need to precompute the memo? Without precomputation wouldn't it blow up to $$$N^2$$$ in some worst case. Because of this I think I had got TLE in test 2 earlier with similar approach.

Yours TLEs because you’re initialising the DP vector for each test case. You need to memoize over all test cases, which achieves the same time saving as precomputation.

Thanks, haha, I completely forgot about that! I have resubmitted with clearer code now: link.

Nice code. I didn’t think to memoize in a 4d vector — my code is slower because I used a map. Fortunately it’s still only 311ms!

Could you please explain a little why your transitions are 1 — rec(). Why minus? I'm curious about learning this approach. It seems to be helpful in many game related problems! jimm89. Sorry for unnecessary tagging, but I really wanted to know your thinking process in this recursion!

Sure: I’ve reframed the problem to say that both players are trying to minimise the value of their own score minus the other score, so when they make a move which is not a reversal, we add 1 to their score, and then gameplay transitions to the other player. Anything the other player scores is then subtracted. Our final answer depends on whether, from Alice’s position, the best we can do is negative (win), zero (draw), or positive (lose).

Very beautifully explained! Its becomes a little tricky when you are not the one playing the game! I've come across many problems like this where you sometimes have to maintain the difference of 2 players score!

Where do you guys get such problems? Although punishing, quite simple interesting!

My solution for C:Store the positions for each unique number. Consider the example:

$$$[1,2,1,1]$$$

All pairs $$$(i,j)$$$ with $$$a[i] = a[j]$$$ are:

$$$a[i] = 1; [(1,3), (1,4), (3, 4)]$$$

Consider the pair $$$(i,j) = (1,3)$$$. For each subsegment that contains this pair, we have $$$(i)$$$ possible choices for starting position of the subsegment and $$$(n-j+1)$$$ for ending position of the subsegment. Using this, we can get number of subsegment containing each pair as $$$i*(n-j+1)$$$.

Let's say we store positions of all $$$1$$$ as $$$[1, 3, 4]$$$.

Then, $$$count_1 = 1*(n-3-1) + 1*(n-4+1) + 3*(n-4+1)$$$.

Note that $$$(n-4+1)$$$ is repeated twice since there are $$$2$$$ ones to the left of $$$a_4$$$. We could simply multiply $$$(n-4+1)$$$ by $$$(1+3)$$$. This is the prefix sum of positions of all $$$1$$$s before the current $$$a_4$$$.

Hence, for each unique $$$num$$$, $$$count_{num} = \sum\limits_{i=2}^{size(pos[num])} (n-pos[num][i]+1)*sum(i-1)$$$ where $$$sum(i-1)$$$ returns sum of all values in $$$pos[num]$$$ in range $$$[1,i-1]$$$ inclusive.

Sum of $$$count_{num}$$$ for all unique numbers is the final answer.

Submission

Nice explanation, a bit of typo, should be $$$a[i] = (1,3),(1,4),(3,4)$$$

Sad that simple $$$O(NK \log(N))$$$ with long long and recursive lazy segment tree TLEed on E. Had to make some submissions and ACed with unsigned in the end. Did no tester face this issue or was it intentional to prevent other slower solutions for passing?

Just submit the same code with C++17(64)

Wow. Now it passed in ~2 seconds. Interesting!

Actually, none of the testers solved that problem while testing.

Don't know why but B1 and B2 for me easier than C a lot!! :)))

For me too, that is because DP does not like me.

Sorry, my bad...