Hi, Codeforces!
I'm glad to invite you to take part in Codeforces Round #721 (Div. 2), which will take place on May/20/2021 17:35 (Moscow time). 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.
- Monogon, ajit, kassutta, namanbansal013, Qualified, 4qqqq, Ekler, Rajdeep, wxhtzdy and kalki411 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
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 .
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
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? Jhin
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
Why isn't demoralizer 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 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.me/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.
WowGood！Regardless of the difficulty of the question, I really expect this "simple-to-read statement"!
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 demoralizer 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 demoralizer 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.
Best of luck to all the participants :)
Strange Monogon did not ask for contribution this time :( Feeling unlucky already :((
Monogon never asks for contribution, contribution asks for 1-gon.
1-gon > gyrating cats.
Zlatan Agrees...
Hope I become a pupil this time
Any update on scoring distribution? UPD : added
I hope I can solve only 2 problems...as a newbie...
.
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
what are subtasks? can anyone tell
basically they are the same problem with different constraints
Second question having a subtask seems scary.
Maybe it's combinatorics :o
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?
Aren't you supposed to be Mr. Incredible?
"Math is Math" — Mr Incredible , 2018
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.
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 theory and dp (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$$$.
totally 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.
nvm
Ah, you already got it. I just finished rereading the task and wanted to comment, that this is not a problem I'm very motivated to think about again... It felt like a big casework 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
You have a really minor error.
The sz is wrong. It should be:
See 116995339
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?
For any
(i, j)such thata[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 inaof sizen=10, value3is at{0, 2, 4, 5, 8}.Now using the above expression => let's say
j == 5then subsegments which have index5andone 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).Can you please explain how you get to (i+1)*(n-j)?
Edit — Nevermind got it. I misread subsegment as subsequence!
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
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.
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:
if 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.
Suppose 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.
try to make the dp associated with the value instead of the position.
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.
.
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'ands[f(i)]=='1'. Let's call this $$$C_{0,1}$$$.s[i]=='0'ands[f(i)]=='0'. Let's call this $$$C_{0,0}$$$.rev.0or1, (if the string's length is even we consider it as a1). Let's call this a Boolean variablemid.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 minimizedand Bob wants to maximized. So, we can have the following DP solution:$$$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 ofd. 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 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.me/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 .:(
Finally getting to 1500! Ideas for A,B1 and C :
Simple 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.
If 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.
Make 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.
On 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.me/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 ;_;
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
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
Please check this submission :- https://codeforces.me/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(n2). Take a look at https://codeforces.me/contest/1527/submission/116859222
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.me/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(n2) for pre-processing the cost matrix and then O(n * k * log(n) * 20) for calculating the minimum cost partition.
The
20is needed because we can't store O(n2) values within the memory limit. We could compress it further to reduce it to10or5but 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
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.
1001001(Alice), 1101001(Bob), 1101011(Alice), 1111011(Bob), Alice's reverse, 1111111(Bob), Alice wins
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!
That hot chick is your girl?
Yes, bro, isn't she beautiful? =)
I think B1+B2 can be solved by greedy: denote
aas the number of0at some indexisuch that1at indexn+1-i; and denotebas the number of other zeros. Ifa = 0(here is the easy part): ifb = 1or2then Bob Win; otherwise, Alice wins if and onlybis odd. Ifa = 1: Alice wins except caseb=1(draw). Ifa \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
nmust be1, suppose that it is on indextfrom right to left, so in the expression, you need to have a number with bit0at that position. And the maximum one is011...1witht-1numbers of1.I overkilled it with binary search.
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
Let $$$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->1move possible on $$$s$$$ such that you will win or draw from that. Then you can do that and hence, $$$f(s) \geq 0$$$. If every0->1move 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->1move 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 two0s 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 position11000011. Continue for two more steps:11100111, now each one costs3and here is turn of Alice, she makes11110111, now Bob just reserves the string, and Alice costs2more 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
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_setwhether 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_revwhether 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).
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
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...
Look at the statement again boy :))
Its given in the question that there is at least one 0
It is guaranteed that the string s contains at least one '0'.:P
I am fucking brain dead holy shit
What will be the output for string '0000' in B1? I think the output should be "DRAW".
No, lets say Alice puts 1 in any position 0100 Bob can make it 0110 then since it is pallindrome again, Alice has to enter 1 making it 1110 Then Bob can reverse and Alice would have to fill again. Thus, Alice lost
Can someone please explain why first soln failed but second passed?
116754150
116768652
How could Alice win with 10000?
She just make the 2nd operation first then Bob have to put 1 somewhere. After we will have the same picture as in B1 version.
Alice keep on reversing it in every turn until he gets a palindrome after bob turn.
Alice reverses 00001 (score 0-0)
Bob's options: (1) 10001, (2) 01001, (3) 00101 (note that 00011 is equivalent to 01001) (score 0-1)
In scenario 1, Alice then places in the middle 10101, and from there Alice can force Bob to mark both remaining 0s.
In scenario 2, Alice reverses on both her next two moves, forcing Bob each time to mark another 0.
In scenario 3, Alice then goes 10101, and the outcome is the same as scenario 1.
I wonder why writers wouldn't use the term 'subarray' instead of 'subsegment' in C. I misread 'subsegment' as 'subsequence' and I'm sure there are many others who made the same mistake reading it for the first time. If your aim was to create simple-to-read statements why not use the conventional terms?
The why i fear problem C, this should not translate to fearing C cups.
I spent too much time on C, and when I figured it all out, I was too slow to code everything out and submit.
So yes I do fear problem C, too.
casework solution for B2
let cd = count of a[i]!=a[n-1-i]
let c0 = count of a[i]==a[n-1-i] and a[i]==0
if cd==0: solve same as B1
else if cd==1 and n%2 and a[n/2]==0 and c0==0: DRAW
else ALICE
I can't prove how it works but it passed system test
AC code: https://codeforces.me/contest/1527/submission/116851873
What about cheaters ?
Here's my screencast from today's round. It's currently uploading and should be ready in the next few minutes.
bad round :(
How to prove the correctness of case based solution of B(1+2)?
B1 feels intuitive. bob copies alice as much as he can until there's only 1 token left (on either side of the palindrome), in which he can flip it the final time to make alice go down an extra 2 tokens. be careful about n%2==1 where middle is open to '0' (as then alice can flip the script) and should be good.
then B2, the logic is bob wants to make it a palindrome ASAP, otherwise alice keeps spam flipping. so we know that the cases eventually reduce down to B1. then, alice can also decide whether she wants to be the one to start case B1 by placing the final token herself, or keep spam flipping and let bob get to case B1 with it being his turn to move, and adjust costs accordingly.
hmm, using the same but getting WA in B2.
Anyways thanks! I will try again.
From my point of view, task C was rather well-known and classical. This idea is obvious.
How could this task even get to this round? I thought that rounds are checked for well-known tasks with trivial and well-known ideas.
This could be compared with the task like "longest increasing subsequence" and some other basic tasks.
Can you tell what's the well known version of C or link it here? Curious as i could'nt solve
I think it's fine to have it in Div 2, this approach is indeed standard, but it isn't described in algorithm books and websites, so a lot of newbies don't know it. Now they know.
inkjhb
This contest was a disaster for me
Great
Alice: 1000 (add)
Bob: 1001 (add)
Alice: 1101 (add)
Bob: 1011 (flip)
Alice: 1111 (add)
small hint for B2 : If the starting string isn't palindrome, Alice will win or it will be a draw. There is no way for Bob to win if the starting string isn't palindrome.
Test cases are weak for Problem A as my this solution also passed:- int main() { int t; cin>>t;
while(t--) { long long int n,count=0,u; cin>>n; u=n; while(n) { u=n-1; n=n&u; } cout<<u<<endl; }}
Your solution works in log(n), you are doing
n=n&(n-1)which sets least significant 1 to 0.What if the string is of 4 length and string is 0000 then it should be draw,because first alice will change first character to 1 so string becomes 1000 then bob reverses it and then alice changes it to 1001 now bob cannot reverse the string because its palindrome, now bob makes it 1101 and now alice reverses it and now bob again makes 0 to 1 so string became 1111 and both pays 2 2 dollar for changing 0 to 1 , so answer should be DRAW and not BOB
Init 0000
Alice+1 1000
Bob+1 1001
Alice+1 1101
Bob+0 1011
Alice+1 1111
Score 3:1
the score of B2 must be 1750 or 2000
How I solved A:
Sir MikeMirzayanov, problem B1 lacks tests that come out "DRAW"!!?
Because draw is impossible
what about 11111
The second line of each test case contains the string s of length n, consisting of the characters '0' and '1'. It is guaranteed that the string s is a palindrome and contains at least one '0'.
Problem E is similar to B. The Bakery.
Question B2 https://codeforces.me/contest/1527/submission/116807363 Can anybody tell on what test case this solution goes wrong??
if(n%2 == 1 and s[n/2] == '0' and z == 1) change this line to
if(y==2 and z == 1)
test case — 10000 ans = ALICE operations
alice(0) — 00001
bob(1) — 10001
alice(1) — 10101
bob(2) — 11101
alice(1) — 10111
bob(3) — 11111
Easy solution B2 https://codeforces.me/contest/1527/submission/116808998
When will be the ratings updated ?
new to this, same question
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Can anybody highlight the Corner Cases for Problem B2... I am getting wrong answer on Pretest2...
Try
1
7
1100010
Output should be
ALICE.Yes, this is a nice case...my solution is not working. May i know ur approach? Whether dp is required here? Actually, i am trying for a generalized solution for both B1 and B2. B1 got executed, but is failing cases in B2.
We can use DP in this problem, but it I don't think its necessary.
I've just further built upon my solution from B1. If you've done B1, you might have noticed that Alice wins by one point when there are odd no. of 0s and Bob wins by 2 points when there are even no. of 0s (given both players play optimally and discarding the edge case of n=1). Hence whoever wins, wins by a margin of a maximum of 2 points.
Alice's disadvantage in B1 is that the string is a palindrome when she starts; hence her first action can't be of reversing. She is forced to change a 0 to 1. But in B2, she can start by reversing the string if it isn't a palindrome, forcing Bob to change a 0 to 1. She'll keep spamming the reverse operation till possible, so the only way for Bob to stop her from doing this is by making the string a palindrome again.
Now the cases reduce to how many zeroes need to be changed to make the string a palindrome. If 0 changes are required, then the answer would be the same as B1. If 3 or more changes are required, then Alice would win. Bob will change these 3 zeroes to ones, but once the palindrome is obtained, he can gain a maximum of 2 points more than Alice in the palindromic string (explained earlier), and hence will remain 1 point down in total.
So the only cases which are required to solve for are 1 and 2 changes. I encourage you to solve these cases on your own. If stuck, you can refer to my solution, which I think is relatively simple.
May I know where is the mistake in my solution for Problem B2?
I can tell you my approach. (Assuming you solved
B1)In
B2, if the input string is not a palindrome thenAlicekeeps on reversing the string untilBobmakes it a palindrome. Once the palindrome is made, you can use yourB1method to see who wins. But here is the tricky part,Alicejust doesn't wait untilBobmakes the palindrome. IfBobtakeskno.of operations to make the string palindrome, thenAlicewaits till the (k-1)th step and sees the future by using yourB1function which takes the finished palindrome string as parameter and assumingAlicestarts the move.If
B1function outputs => DRAW or ALICE, thenAlicewill letBobmake the kth step too and proceeds.If
B1function outputs => BOB, thenAlicewill do the kth step and let Bob start the move once the palindrome is made.Can someone tell me why my code is giving correct answer on local compiler but not on codeforces ones?(For problem B2 in today's contest)
I suspect there must be something wrong with declaring string as global variable.
UPD : It's becoz i was using cout and puts in the same code. The code got accepted when i either used cout or puts solely. Don't know the technical concept behind it.
It is because of the fast IO lines you have included as the first two lines in
main(). Removing these lines would get AC. (Since fast IO is needed, don't mixcoutandputs.)To understand, how this works behind the scenes, you can read about it here.
https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull
.....
Can someone help me in CodeForces 721 Div 2 Problem B1, what if the string is '0000' ,why the answer is BOB why not it is DRAW. Since both will play optimally and will not allow to win the opponent.
0000 Alice=0 , Bob=0 // in starting
1000 Alice=1 , Bob=0 //alice have to change
0001 Alice=1 , Bob=0 //bob reverse the string i.e. not want to spend money
1001 Alice=2 , Bob=0 // again alice have to change the
1101 Alice=2 , Bob=1 //bob has no other option but to change
1011 Alice=2 , Bob=1 // alice reverse the string i.e. not want to spend money
1111 Alice=2 , Bob=2 // again bob will change
0000 Alice=0 Bod=0
1000 Alice=1 Bod=0
1001 Alice=1 Bod=1
1101 Alice=2 Bod=1
1011 Alice=2 Bod=1
1111 Alice=3 Bod=1
yes i know this is one of the possible way , but if there is a way ALICE not want to make BOB win so he will make the game draw if he himself cannot win Dont you think it is also valid
Yes it is also valid
Don't you think this case is a contrary case and can have different answers and still both are playing optimally
Why editorial is not published yet?
can anyone tell me how BOB will win if S = 100001, in ques B. Thanks!
First Alice has to make 1 zero to one, so S=110001 Bob converts Last zero to one, S=110011 It is palindrome so ALice cant reverse it so convert zero to one, S=111011 It is not palindrome so bob reverse it, S=110111 It was reversed last time so alice converts zero to one , S=111111 No of dollars Alice spent=3 Bob spent=1 Bob wins.
100001(0:0) goes to 100011(1:0) to 110011(1:1) to 110111(2:1) to 111011(2:1) to 111111(3:1)
as bob has lesser number of coins, hence bob wins
I think E in the contest is some kind of classical problem, can anyone please provide me link for similar questions for practice.
I didn't see anyone notice that B2 does not require DP, In B2 we just need to check if the given string is palindrome or not.
If it is a Palindrome then B2 solution is the same as B1 but if it is not a palindrome then we just need to count the number of zeroes and how many numbers are different. let Z : number of zeroes in the string and P : number of zeroes that need to change to make the string palindrome. if(z == 2 && p == 1) then only ans will be DRAW and in every other case ALICE will always win. code : here
Yes that is right! Printing out the dp-table shows the same result. So if somebody is stuck on the game logic and can't work it through, he or she could do the dp, see the regularity, improve the answer and then be able to solve even bigger constraints, than dp allows (since the dp is $$$O(n^2)$$$ and your solution is $$$O(n)$$$).
For the string
1your program gives the wrong answer. Of course though, the case is not allowed, since it has no 0.Can anyone help me why did this give me TLE its problem A- submission
see, for A if you consider the most significant bit, then , adding all the numbers till the highest power of 2 smaller than will get you a number in which the most significant bit is one as for all numbers from n to 2^k, that bit is always gonna be one , but for 2^k-1 that goes to a 0 and rest to 1 whereas we already had 0s in those bits previously , so adding that fetches us 0.
quite simply (2^k)&(2^k-1) = 0 and this is what was used giving us the and 2^k — 1
Super fast Editorials in the previous contests created a bad habit. Now I am angry since the editorial of this contest is not up yet XD
No it isn't bad habit. I honestly don't know why it so hard to have the round started when editorial is ready. Usually the "late" editorials are added after 1 day. Would it be so bad to have the round 1 day later and have everything prepared? I don't think so.
When can we expect the editorial to be published...
Hi!
Can someone explain me why my submission to Problem C keeps failing (attempt)? I think I had got the idea behind it, but I failed pretest 5 times during the contest!
Thanks in advance!
Auto comment: topic has been updated by the_nightmare (previous revision, new revision, compare).
nightmare round
Can somebody help me understand B1 in 721? There are two test cases that have been bugging me
TEST CASE 1 :-
7
1001001
I feel that the answer for this test case is DRAW because both Bob and Alice spend two Dollars each
TEST CASE 2 :-
7
1000001
I feel that the answer for this test case is BOB because Bob spends 2 Dollars and Alice spend 3 Dollars
CLEAR EXPLANATION OF MY POV:- In case1 :- step 1:- 1101001 (Alice spends a Dollar)
step 2 :-1001011 (Bob reverses the string)
step 3:- 1101011 (Alice spends a Dollar)
step 4:- 1111011 (Bob spends a Dollar)
step 5:- 1101111 (Alice reverses)
step 6:- 1111111 (Bob spends a Dollar)
Both Alice and Bob spent 2 Dollars each.
In case2:- step 1:- 1001001 (Alice Spends a Dollar)
step 2:- 1101001 (Bob spends a Dollar)
step 3: 1001011 (Alice reverses)
step 4:- 1101011 (Bob spends a Dollar)
step 5:- 1111011(Alice spends a Dollar)
step 6 :- 1101111 (Bob reverses)
step 7 :- 1111111(Alice spends)
Alice spent 3 Dollars and Bob spent 2 Dollars
The idea behind the 2 test cases you mentioned is similar, so I will just mention it for the first one:-
Step 1: 1101001 (Alice spends a dollar); Step 2: 1101011 (Bob spends a dollar); Step 3: 1111011 (Alice spends a dollar); Step 4: 1101111 (Bob reverses the string); Step 5: 1111111 (Alice spends a dollar).
Alice spends 3 dollars while Bob spends just one dollar, which means that Bob wins.
Can you explain me why doing this yields an optimal solution?
Not sure about what you mean.
.
Hello MikeMirzayanov ,Codeforces system sent me a message saying that my solution(116813246) for B1 matches with someone else's(whom I don't know) submission(116794282).Now I see that some part of our code coincidentally matches but that was the most obvious part of this question.In my opinion that part was quite straightforward and many people would be having similar implementation.Even given solution has similar code but that doesn't mean I copied from problem setter or vice versa.Please check my solution manually and tell if it looks plagiarised...