I hope you enjoyed the contest! I will add implementations later.
UPD I've added implementations.
Tutorial
Tutorial
1382C1 - Prefix Flip (Easy Version)
Tutorial
Implementation 1 Implementation 2
1382C2 - Prefix Flip (Hard Version)
Tutorial
Implementation 1 Implementation 2
Tutorial
Tutorial
1381D - The Majestic Brown Tree Snake
Tutorial
Tutorial
In the problem B, I tried to submit when the clock is 2 seconds but it says "Contest is over"
I dont complain anything here, just asking you guys if I am correct in my code (because I cant submit right now)
My approach is to calculate how many consecutive ones prefix $$$1, 1, 1, ...$$$ of the array
You can submit once system testing is over.
Yes I know but I'm excited to know whether my code is correct is not :(
It is. Interestingly, the approach you described is not the same as what is written in your code.
Well it was correct but what do you mean about my approach, am I wrong something ?
Oh, I am sorry. I got confused as I didn't directly find something not equal to 1. Your approach and code both are correct.
Video Editorial of C2. Prefix Flip.
Wow! The explanation is done on board. I thought it to be an explanation done using rough diagrams made on computer which I feel are satisfactory but using white board is what I go for.
Shall we see you make more videos.
PS: I was trying to explain my C2 solution over comment but looks like your solution is exactly same as mine, so it won't be needed anymore :)
Great explanation. thanks
nice explanation bro.... keep it up create more like this,not now but in future you sure get more and more likes ....
Wonderful, you explained everything in such a simple manner, and everything in the editorial made sense after it. Thank you
Yes the code is good to go but correct you last statement
with
How do you ensure that the players are playing optimally if you follow this scheme? If you can kindly explain....
Consider the case :
The Second player will have the chance to pick the third element, i.e 2. So if the next element is not one the player will always choose (ai-1), so that it is ensured that the other player is forced to pick the one that is left at that place. If the next element would've been one, then our current player would've picked the complete (ai) so that the next player is forced to pick one. And hence if the starting element isn't one, the First player will always win.
" If the next element would've been one, then our current player would've picked the complete (ai) so that the next player is forced to pick one" in this statement where from the one is coming that you are saying the next player is forced to pick up. Because if the next element is 1 then our current player will pick that 1.....
I am sorry for stupid queries but this game theory problems I am very poor at.
For this part consider the case to be :
1 1 1 2 3 1 4 5
Now since after 3 there is a 1, hence the player currently playing 3 will pick all of 3, hence the next player in turn is forced to pick 1, and hence the player picking 3 is still in control of the game. In short, the player whose turn it is, has to pick sayx
andx
> 1, then that player is in control of the game, and will win the gameTo win the round, a player need to have control over the piles on it. Every number except 1 return bacha the control over the game to other player. Intially player 1 has control over the game, but as soon as it gets 1 in front in it (in prefix only) then the control will be transferred to player 2 and vice versa. Therefore, if there are odd number of 1 in prefix of array, then player 2 will have the control of game at last and will win , else if there are even number of 1 in prefix, then player 1 will control over game atleast and hence will win. This is the reason of the above logic.
Yep yep, I too did the same thing, counting the no. of consecutive ones in the prefix.
Short and concise problem statements ✓
NO BACKGROUND STORIES ✓
Useful samples ✓
Quick Editorial with well documented implementations ✓
Super interesting problems ✓
Strong pretests (I hope so, please don't let me down) ✓
RATED FOR ALL ✓
No queueforces ✓
P.S: It seems pretests turned out to be a bit short (as warned in the announcement), never mind though
CONCLUSION: A perfect contest after a long time, Thanks Monogon!
Agreed! This is probably the best contest I've ever seen on CodeForces!
Indeed, He lives up to his name
yeah, background stories just make the statements more confusing.
Give Monogon some contribution.:))
[Deleted]
Agreed .. This was one of the best division 2 rounds.. Hats off Monogon
Monogon let you down becos pretest were not so good for c2. A n==3 test case could have made me realise the bug in my code.
You Forgot No QueueForces!
Yeah my bad, how could I even miss it, edited thanks !:)
A very nice and balanced round! Solved some and then some to learn from.
I think the time limit of Div.2D is too tight. I got the right solution when it was only 30 second before the contest was finished, but disappointedly got a TLE. My TLE Code
Ok I got something wrong in my code. My array f is too small.
You also use memset for every testcase which sets all the elements of the array, so in total your complexity is 2020 * 2020 * No of Testcases which might be too much and results in tle :)
Yes I got it too. I have already been away from keyboard for one year and I forget a lot of basical tricks like this.
I don't think so. My solution (which btw uses different approach than in the editorial: the strictly decreasing subarray must be in some of the arrays) performed in 31 ms.
For C2, I basically took Solution 2 for C1 and then added a custom data structure to make operations (modifying a prefix) done in O(1) time. Basically, you maintain the left and right indices of the original string and also keep booleans indicating if the string is reversed and if the string is flipped.
Can you please elaborate your solution?
I think it should be pretty intuitive.
Thanks!
Wow Wow Wow! Production Grade code.
Can someone further explain how to optimise the 2nd solution for C1 with a segment tree?
couldn't solve but really loved the problems Div2 C1, C2 and D.
My rating hovers at 1800 and I took a leap in div 2 to try Problem E.
It seems that my approach is the same as the answer, but my implementation is wrong :(
I also could not find a case that fails my implementation during the contest.
No regrets, other than failing to see the trick in solving D2C2
Anyone with a randomized solution for C2?
bye bye CM :(
There is always a next time
I guess,
I never thought that writing 'first' & 'second' instead of some random names would have been so helpful.
You would still be surprised how many questions we received of the form: "Who goes first? First or second?"
SUPERB!
XD
As mentioned by Errichto earlier also, there should be some criteria or some kind of bar and users who are above that bar should only be allowed to ask questions, otherwise people just start spamming without even reading the questions carefully.
While there are inevitably lots of silly/spam questions, I don't think it's a good idea to stop certain people from asking. There are lots of beginners who have genuine confusion about the statements that higher rated users won't have based on experience with similar problems and the general contest format.
Also, spam questions usually do not significantly increase the waiting time for genuine questions. My previous round was an exception to this because a bug made it hard for us to answer questions, and there was an extremely large number of spam questions from people complaining about the technical issues.
In D2-C2, how exactly will we keep track of the first bit?
Won't it depend on a lot of other bits?
After doing 2 operation the indexes gets circularly shifted(Obviously ignoring the bits that we fixed).
Consider these 0,1,2,3.....,9 After 1st operation of length 10
9,8,7,6....,0 After second operation of length 9
1,2,3,4....,9,0
Now since zero got fixed we move on with
1,2,3,4....9
But now 0 is at the end?
imagine string one has like 10 characters.the first bit will keep changing as follows iteration 1 -> position 1 without flip , iteration 2 -> position 10 with flip , iteration 3 -> position 2 without flip , iteration 4 -> position 9 with flip , iteration 5 -> position 3 without flip , iteration 5 -> position 8 with flip , and so on .... submission link https://codeforces.me/contest/1382/submission/87589106
Instead, we can observe that after making the last k bits correct with our procedure, the prefix of s of length n−k will correspond to some segment of the original string s, except it will be possibly flipped (inverted and reversed). So, we need only keep track of the starting index of this segment, and a flag for whether it is flipped. Complexity is O(n).
I was trying to implement this. Anyone help me how to implement this.
See my answer above
I have implemented it in my code using left and right pointers to our string — link
On closer observation, you will find a pattern, that is, suppose length is n. the bits in the first place will be,
s(0) -> first round
s(n-1) (flipped) -> second round
s(1) -> third round
s(n-2) (flipped) -> fourth round
all the bits from the end will be flipped and from the front won't. so you just need to match the first bit in every round with the required bit and flip the first bit if needed.
P.S.(i observed it all during contest but did sh*t for implementation. Now i solved it in 10, felt foolish)
Submission
I have also tried something like that.. you can check my submission. let me correct it if it works
Made a few changes, You'll understand
sorry I made a stupid mistake.. how to omit such stupid mistakes?
https://codeforces.me/contest/1382/submission/87635860
I just thought i will work as the last pointer..
my approach was right
Everyone makes mistakes. You just need to track your code and print every variable, see where it's going wrong. that's how i debugged yours. :)
Here is my solution for D, which works in O(n). I wasn't sure about greedy part of it, but it passed all of the tests. 87566235
Can anyone prove/explain why this trick works? I knew it since school, but I forgot how it works.
Grredy approach is wrong. This solution is hacked. Bit disappointed that this test was not part of System tests. :(
Shout out to fsshakkhor
Video explanations if you are interested after you give Monogon contribution.
just a silly question, how to give contribution.
Upvote.
Thanks Man i will Upvote.
Loved this round!
fourth approach for C2:
Use deque and insert all indexes from 0 to n-1. Then start popping from end. If value is not equal then we need to pop from front. Also keep track of number of inversions done.
Solution
Can you explain more?
We start from index n — 1 to 0. Let's initialize our current direction to pop from deque as back direction and number of inversions as 0. Note that if inversions are even then a[i] remains same else we invert it. So we ignore all indexes where (a[i] ^ (inv % 2)) == b[i]. That handles the inversion part in the operations.
Now to handle reverse part of operations, we use deque with choice of direction initialized above. Now if according to our current direction choice, it values don't turn out to be equal then it means we need to take element from other direction which will be equivalent of reversing the array. So change the direction.
Hope it helps.
PS — bitwise operations might be confusing. a[i] ^ (inv % 2) means if inv is odd then it's a[i] ^ 1 which is equivalent to inversion else it's a[i] ^ 0 which keeps the value of a[i] same.
hey... I did exactly the same using deque too lol! 87577133
looks like a notorious coincidence to me
notorious is a pretty bold term to describe it tho XD...
i'd rather call it a brainsync 100 moment!
i did without deque by using 2 variables start and end and count for inversions. but it wasted 10 min to got that.
My Linear Solution For Problem C
Lets $$$a[head..tail]$$$ correspond to $$$b[0..tail - head)$$$
If $$$a[tail] = b.back()$$$ then we move $$$tail \rightarrow head$$$
Just do solution 2, but store prefix which is not solved yet using initial array and following variables: physical position $$$x$$$ of bit we think of as a[0], bool for whether $$$a[1], a[2]\ldots$$$, are located in $$$x + 1, x + 2, \ldots$$$ or $$$x - 1, x - 2, \ldots$$$ and extra bit for whether actual values of $$$a[i]$$$ are bits in array, or their negations
hello friends, it might happen that this post of mine may get downvoted a lot, but I need to share something very important.
I loved the problems very much and even passed the protests for problems A, B and C1 and it was very disappointing to know that my solutions for B and C1 failed, maybe due to weak pretests.
I would appreciate it if I can get a fair knowledge regarding this and implore the codeforces community to make better pretest, it was very disheartening for me.
P.S: I do accept my incompetence, I just wanted better pretest so that if I knew i could have improved upon that. Again, awesome round authors.
I solved C2 (Hard Version) with Doubly ended queue.
Here is my submission: 87597675
dp solution for B 87559531
Yeah..I also solved it using DP. You can use only 2 states.... Though, 3 states also passes.... 87571204
Glad to know I'm not the only one who did DP on B You can also use 1 state DP. 87538227
In problem C hard version I used an O(n) deterministic brute force method.
I solved easy version with the following observation:
if I have a string ....0000000 (k zeros) and I want to change it to ....1111111 (k ones) I can apply {n=current length, k, n}. Then the last k bits are OK and the first n-k bits don't change. (And don't forget to n-=k after this operation) (P.S. and if the current last bit are the same, just skip)
So if k always > 2, we can do the task in 2n operations. The sad thing is that k could possibly(?) always be 1.
If k is 1(suppose current length is n, this bit would be a[n-1]), if n = 1, just apply {1} to flip. If n>1, we detect one more bit(a[n-2]). If a[n-2] == b[n-2](Suppose, 01 and 11), apply {n, 1, n}. So we used 3 steps to deal with 2 bits in this case. But when a[n-2]!b[n-2] (say 01 and 10), the optimal operation is n, 1, 2, 1, n, which is 5 steps. Not good enough.
So again we detect one more bit(a[n-3]), if a[n-3] == b[n-3], just do {n, 1, 2, 1, n} s, 5 steps for 3 bits, enough. If a[n-3] != b[n-3], there are two cases: (1) a[n-3] == a[n-2] (say 110 and 001}, use {n, 1, n, n-1, 2, n-1}, 6 steps for 3 bits (2) a[n-3] != a[n-2] (say 010 and 101}, use {n, 3, n}, 3 steps for 3 bits
So the task can be done in 2n operations
So dumb lol
my python code for problem D passed pretests but got tle in system tests. now the same code i submitted in PyPy it got accepted. But how? Why did python show TLE? My happiness of solving 5 problems for the first time was ruined in 15mins. :(((((((
PyPy is quicker than python for everything except for input and output.
Monogon In games like the one given in problem $$$B$$$ , how to prove that there always exist a fixed answer (i.e how to prove that result of the game is fixed from beginning itself if they both play optimally).Proof in the editorial assumes this .
Because it is a zero sum game. It is known that any zero sum game has an optimal strategy so the result must be fixed
Every player is playing optimally , so every player will try to win the game
It can proved by solving it using dp , then the player will see the best move he can do it so he will win the game , clearly if there's a move make the other player win , then he will not do it unless he can't do any other move
Question E (Mastermind) reminded me of the question "Bulls and Cows"
I had a different solution for C2, and used two pointers (left=0 and right=n-1), where left and right could be beginning/end of the remaining segment, and only advance in one direction (which was determined by the nubmer of flips). For example, if you start with abcdef, and you fix the last bit by flipping, now you have fedcba, and now you need to compare 'b' to 'f' (so the right pointer stayed on 'f', but the left, which was 'a', moved to 'b').
My Video solution for Problem B. Hope you Like It.
In problem D, after couting the lengths of all the continous blocks as in the editorial, i checked whether it can form a sub-set sum that equals to n by brute force (run in exponential time) but i used some optimizing tricks here, that is, according to pigeon hole principle, if the total number of continous blocks is greater than or equal to n, then we can always form a subset with sum = n, so there is no needs to check subset sum in these cases, and while running brute-force, if i encounter a subset that sum up to n, then i stop the algorithm immediately .Anyway, i passed the system test though i thought i could get a tle if the test cases were strict enough.
My solution for D
how can you say if sum of contigous block size is equal to n we can divide that array .. in subset order is not fixed. but in this question the first block always fixed with respect of other blocks.
sorry, i had a mistake, the total number of continous blocks must be greater than n. What i meant is that: if the number of blocks is greater than n, then there always exist such a way to form a subset with sum equals to n, remind that to total sum of all blocks size is always 2n. for example, if n = 4, then we may have block sizes of one of the following:
4 1 1 1 1
3 2 1 1 1
2 2 2 1 1
clearly, we can always choose a subset in each of the above so that their sum equals 4Can you please prove why this is true.
and yes, the order of subset is not important, as you said, the first block is fixed with respect to others, but that doesn't matter too :v
How to solve div-2 D in O(n root n). Thanks in advance.
First notice that there are O(sqrt(n)) distinct values because 1 + 2 + 3...+k >= 2*n implies k = O(sqrt(n)). Then you can take all distinct values with their count and then make a dp: dp[i][j] = 1 if it is possible to make sum 'j' using starting first 'i' elements(i <= sqrt(n), j <= n)
Now the recursion is: dp[i][j] = dp[i-1][j]|(dp[i-1][j — val[i]])|(dp[i-1][j-2*val[i]])|....|(dp[i-1][j-cnt[val[i]]*val[i]]), where | is OR operator, val[i] is distinct value and cnt[val[i]] denotes it's count.
Note that it is still O(n^2) if we do it in this way....however make a 2D pref array which is defined as:
pref[i][j] = dp[i][j] | pref[i][j — val[i+1]], in this way dp[i][j] = pref[i-1][j]. Now it is O(n*sqrt(n))
why your submissions are not visible?
Hmm....I made those submissions in the morning, I don't know why they are not visible....also I haven't implemented the O(n*root(n)) algo....do tell if you want its implementation...
Yes that would be very helpful ^_^
Can someone explain what is wrong with the following approach for div1 C(Mastermind):- Let "nc" be the color which has not occurred. Let's first sort the sequence and keep track of corresponding index in original array.Let's try to first color (y-x) indexes which can be done by swapping color of first((y-x)/2) with last (y-x)/2 indexes if colors of cells to be swapped are different,if (y-x)is odd we will make one index equal to color "nc", else we cannot find a solution(I chose first and last (y-x)/2 because if possible they only can be of different color) . After that we will left with some indexes in middle, then we can color x indexes from the remaining indexes in same color and leftover indexes in color "nc". But, i am getting wrong answer in testcase 38 of test 2. Link to submission:- https://codeforces.me/contest/1381/submission/87596300
Don't quite get your code, but
if (y-x)is odd we will make one index equal to color "nc"
would result in no solution if y == nThanks ,I found my mistake.
I had the following solution to Div1D. Unfortunately I did not manage to implement it correctly in time, but I am still curious if this is the correct approach.
Repeat the following until one of the end conditions is reached:
Does this work? If not, what is a counterexample?
I have now implemented this solution, in submission 87661047. It gives WA, but I cannot think of a counterexample (or my code may have a bug). I cannot get the killing test case out because the test case file gets truncated. Anyone have an idea?
Your implementation has a simple one-line bug. It's surprising to me how often your program gets the right answer in spite of that bug. Its smallest failing test case seems to have n=12. Here is one such case:
You add the head back in when it is a leaf, rather than leaving it out, and likewise add the tail back in when the head is not a leaf.
Thank you so much! It's very satisfying to get an answer to this, it's very unlikely I would have figured it out myself. Indeed I just have to change a single byte to get AC.
For anyone looking for a fun DP approach for Problem B. Here is the code, basically dp[i] signifies if a player starting from the ith index of the array can win. In order to solve the problem for any index i, you check if the you can force a loss from (i+1) index by taking all the stones at ith index or if you can't do that check if you have more than 2 stones at index i, if so, leave 1 stone so that you can win from the (i+1)th index. If none of this works, then the person starting at the ith index cannot win.
i did the same, dp is the only way that i could think of and it is pretty simple
Nice Contest!
is this the only solution for 1382B ?
like is there any technique or algorithm for problem like this..?
just curious..
thank you for the round..
There is a dp approach which I have mentioned in one of the comments.
Is the score of c2 too low? I found that problem D is a relatively simple dp, but there is not enough time to solve it. It takes a lot of time to solve c2, but the score of c2 is only 1000 points
What is wrong in my this code (for C1)-> Codeforces is saying a is not converted into b but here is my code: https://codeforces.me/contest/1382/submission/87603260 Uncomment last two lines and run to see that a is onverted to b . Someone please explain!
For test case 4 in sample cases answer must be 7 1 10 8 7 1 2 1
can someone explain to me problem B of div2. especially this test case 6 1 1 2 1 2 2 why is the answer First??
init : 1 1 2 1 2 2
1st : 0 1 2 1 2 2
2nd: 0 0 2 1 2 2
1st : 0 0 0 1 2 2
2nd: 0 0 0 0 2 2
1st : 0 0 0 0 1 2
2nd: 0 0 0 0 0 2
1st : 0 0 0 0 0 0
2nd cannot move. 1st wins.
for me a doubt in why it cant be like this, eg: for testcase: 1 2 2 1 1 second wins, init: 1 2 2 1 1 first: 0 2 2 1 1 second: 0 1 2 1 1 first: 0 0 2 1 1 second: 0 0 1 1 1 first: 0 0 0 1 1 second: 0 0 0 0 1 first 0 0 0 0 0 2nd cannot movie, so first wins, but the answer is second wins why
"why it cant be like this" because the player "second" is much more intelligent and will pick up 2 in the 3rd pile.
init: 1 2 2 1 1
first: 0 2 2 1 1
second: 0 1 2 1 1
first: 0 0 2 1 1
second: 0 0 0 1 1
first: 0 0 0 0 1
second: 0 0 0 0 0
sir,does this match the idea told in the editorial? it says count hte maximum number of 1,i.e. 3 in the above case so the answer should come out to be,second. sorry,if I have misinterpreted,please help me out. thanks in advance.
maximum number of 1 such that $$$a_1=⋯=a_k=1$$$ i.e. consecutive 1s in the beginning. Read the editorial carefullly.
Thanks For the good problems. I really enjoyed the contest. First time I am able to solve the 5th question in Div 2. It's really nice feeling.
In problem div2D/div1B I saw some submissions using bitset. How to solve it using bitset?
It's pretty much the same, just that I think it's shorter to code. Every bit represents whether the value is reachable or not. For each value x, b = b | (b << x). In the end just check if b[n] is set or not. Code
I want to notify you that omaik786 is also my account . I want to grow two accounts at the same time . If handling two channels is not appropriate , notify me . I won't continue the 2nd account
It is better to only participate in contests with one account, so you don't introduce bias in the rating system. In fact, a recent change to the rating system was made to discourage secondary accounts.
In Solution 1 of C2, how is it possible to convert string 010 to 000 in 3 operations??
110->000 by only operation..by taking 2 prefix.
Sorry for typo mistake I mean to say 010
010->110->000 ...by <=3 operation..by taking 1 & 2 prefix serially .
Thank You!!
I love how Monogon has given 2-3 solutions for every problem
Thought about question C2 but wouldn't flipping for randomization also (takes steps) make it come close to the 3*n mark? P.S-Please explain a bit more about this randomization concept if you can,please.
It's 3 * (number of mismatches). If you flip some prefixes of random lengths initially, the hope is that the number of mismatches is closer to n/2 than n. Then we achieve about 3n/2 < 2n operations, plus the initial random flips. It's difficult to compute the exact probability, but it's easy to see that we can repeat trials until it works, and we can even handle small n separately if needed.
4 years later we will see comments crying out for implementation
Almost same code gets once runtime error and once AC in Div1C.
AC CODE vs RUNTIME ERROR . Can anyone check please ? This is very weird.
Got it, made a stupid mistake.
.
I think I have a deterministic solution for С2 with ratio 5/3 operations per bit.
Here is my code:
https://codeforces.me/contest/1382/submission/87592131
The main idea is: you scan both strings from the end to the beginning, taking suffixes of length 2 (or 3) making these suffixes alike. If suffixes of length 1 are equal, we just go on. For example (converting suffix 00 to suffix 01): - ......00 -> filp the whole string - 11..... -> filp prefix of length 1 - 01..... -> filp the whole string - ......01
We filp the whole string only two times in each case, in the beginning and in the end, so dots part remains unchanged.
The most operations-consuming case is, for example, when you want to convert suffix 001 to 010. It takes 5 operations per 3 bits. So overall complexity in operations is 5/3 operations per bit. Here is how you deal with this case:
Simple approach for C1 and C2, make the first string all 0s,make it 2nd string from there. as handling all 0s or all 1s is O (n)
"If you find a deterministic solution with a strictly lower ratio than 2 operations per bit, we would love to hear about it!"
Monogon,
if last bit of a is equal last bit of b,we can erase it(decrease length to 1)
else let's try to do last 2 bits of a equal last 2 bit's of b
1)reverse string a
2)if we can do at most 1 operation to do first 2 bits of a reversed 2 last bits of b,do it and after that reverse all string a(decrease length to 2)
if we failed in it our last bits of a and b is 01,10 or 10,01
3) in this case try to decrease length of s by 3 doing <=3 operations,and after that reverse a
in addition: decrease to 1(case 1):0 operations
decrease to 2(case 2):<=3 operations
decrease to 3(case 3):<=5 operations
we are doing at most (5*n/3) operations
i missed some cases in explanations you can see it in my code code:
https://codeforces.me/contest/1381/submission/87606984
my solution seems like:reverse string a,trying to do something with first <=3 first bits,reverse string a
reverse a,doing something with <=4 bits,reverse a
we can do it in <=3*n/2 operations
link:https://codeforces.me/contest/1381/submission/87611009
All the problems were interesting and statements were simple and straight..thanks Monogon!!
how we can use the randomization in third problem div2(1382C2) to reduce time complexity as mentioned in tutorial
The randomization is used to reduce the number of operations, not the time complexity. In fact, it increases the time complexity since it may require multiple trials until the number of operations is low enough.
Nor that anyone is interested but still ...
I have another approach for div2B , we start from the end and will use a boolean win and set it to 1. whoever selects the last pile will select the full pile and win. now moving from end
when w = 1 (next move is of the winner) if v[i] > 1 the winner should select v[i] — 1 and leave 1 for the looser so that he would have won in the next step and if v[i] = 1 we change the move to looser and set w = 0 as looser would have maken this move
when w = 0 (next move is of losses) we will just set w = 1 because last move would have been of a winner
if we end up at w = 1 then the first person won otherwise the second person won.
code : 87607154
Can someone pls explain Div2 C2 Solution 2 from editorial , I know the N^2 solution...
Look, you just need a data structure that allows you to do quickly the following:
reverse a prefix.
toggle a prefix
We can use a more general data structure like Implicit-Key Treap + Lazy Update that allows to do that over a range in $$$O(\log n)$$$ per operation. This is what I did in contest. You can learn about this Data Structure here.
But there's no need for this. Oberseve that we are updating the prefixes from right to left. So, after any operation over a prefix, the smaller prefixes are a subarray (maybe reversed) of the original array, so each time you make a reverse operation is like popping elements from the front of the original array. So, all you need is a double-ended queue (
deque
in C++) and a boolean flag that tells you whether the prefix is inverted or not.Thanks man for this great explanation... I ended up doing the same thing you described using two pointers , for first and last index of a particular segment
I have 2 questions about Div. 2E/Div. 1C:
UPD: Never mind, I got answers by myself, if anybody has same questions, ask me and I will explain :)
I have the same question....I think the pattern would be alternate knitting but I can't do the math.
please explain
Can someone provide a sample code for Div2C2/Div1A2 that uses the solution 2 mentioned in the editorial for the problem?
Implementations for all problems are posted in editorial now.
I was unable to find out the reason behind MLE on test case 2 of this submission of problem 1382C1 - Prefix Flip (Easy Version). I've tried for a long to find out this. Can someone please tell me what is wrong with the code? My Submission -> 87609365
Got it! Made a simple mistake.
In My solution of C1 I followed the second approach mentioned in the tutorial. But my code is getting runtime error. I am still not able to figure out the problem. It would be really helpful if someone can debug my solution.
contest was awesome but the score distribution was not good div2 C2 was harder than B
But you if you solved c2 directly without trying c1. You will get points in both c1 and c2 with same code. So it gives more points than B.
Why does the following submission: 87526271 for Div. 2 A fail the test case: 1 1 1 1 2
Even though in the CF ide it is printing "NO".
I used a different approach for C2 by considering 3 consecutive bits of A and changing them but getting WA for test case 2. Can someone tell me what is wrong with my code? It gave WA. Its a big test case so I can't read it.
https://codeforces.me/contest/1382/submission/87594112
I tried to change every 3 consecutive bits from end of string A by considering all the possible cases. Any 3 consecutive digits bits will have at max 6 operations. **** I didn't forget to check first two digits for input of type n = 3k + 2.
Thanks in advance :)
My solution for C2: Actually an O(n) approach of C1 Solution 2.
My approach for C1 was brute force.(Like Editorial C1 Sol.2).We Fix the bits one by one from the end. i.e. Firsly we have make a[n] same as b[n]. (We flip a[0] if it's same as b[n]). Then perform the operation on a[1...n].
Now you'll observe that a[n]=b[n], performing same operations for(n-1...0). At the end we have our answer in O(n2).
C1 Code. Same concept goes for C2 as well.
You would have noticed that.
for(i=n...1) we always check for a[1] (Perform flip operation on it if necessary). Then we perform operation on (1...i) to get b[ i ] = a[ i ]. We flip and reverse this [1...i] part of string a. Now we have the newer a[0], (for the next value of i in loop) and we repeat the process.
But , for a moment think of string as "abcdef" instead of 0/1's and perform these operations. You'll realize that after every operation, firstly index 1 is a[0], then after flipping and reversal a[n] becomes a[0], then a[1] becomes a[0] and so on... (Ignore their parities for a moment and think on the fact I just stated).
So now we know that 1st index of the string changes in a Pattern. Now we keep a variable to keep a track of the number of flips faced (To maintain the correct parity order as we are not reversing the string[1...i] anymore ) , and we perform it in O(n). I hope my Code would make it clearer.
EDIT: Absolutely loved C2's 1st solution!
This approach is O(n^2) which works great for C1 as sum of all n is less than 1000. But this will give TLE for C2 as sum of all n goes around 10e5.
By mistake I published the incomplete draft . I have edited it. I used the same concept for O(n) Approach. Please have a look.
I solved C2 using the brute force idea for C1 (2n operations and N^2 time) which I optimized to O(N) using a doubly linked list.
Solution link: codeforces submission
Video Explanation: https://youtu.be/TSr0x3EBWSg
P.S. I feel the idea is very simple, the implementation maybe not :p
I solved B by dp lol My observation skills are low <.<
I solved C2 the following way. Starting from back, if the ith position is different, we need to perform the said operation (flip and reverse). But for the ith position to be same after the operation, the first char and the current char need to be same. So if they are different, we first perform the op on just the first element and that flips the bit. Then we continue with the op at position i. This guarantees
2 * n
operations.To find the current element at i, we just need to know where would the current element be going after the swaps.Let's assume we did the swap and
pos1, pos2, pos3, ....
(starting from back).So
pos1 > pos2 > pos3 > ....
pos1
, all the elements behind that will move topos1 - i + 1
.pos2
, all the elements will now move topos2 - (pos1 - i + 1) + 1
=pos2 - pos1 + i
.pos3
gives,pos3 - (pos2 - pos1 + i) + 1
=pos3 - pos2 + pos1 - i + 1
.let's call
pos1 - pos2 + pos3 ....
asshift_pos
.ith bit will be at
shift_pos - i + 1
if i is odd. Hence the current value at ith position will beshift_pos - i + 1
.i - shift_pos
if i is even. The current value at ith position will beshift_pos + i
.And we know how many swaps happened until now. We can keep updating the value of
shift_pos
traversing from back and can find the current value in O(1).I was trying to apply this but was not able to do so.Thanks for explanation.
Monogon I implemented an optimal (in worst case for each n) solution to 1382C2 — Prefix Flip. It runs in linear time.
https://codeforces.me/contest/1382/submission/87617645
It uses at most n operations except for the case when n = 2 where it might need 3 operations. This is optimal, as ...0101 -> ...0000 takes n operations for any n (we can decrease the number of pairs of consecutive bits with different values by at most one per operation, and we need one operation to make the last bit 0). Also, 01 -> 10 takes 3 operations for n = 2.
The approach greedily changes the last bits of a and b which are not equal, by performing flips on both a and b (operations on b are applied in reverse in the output). It looks at the two first bits and three last bits of a and b to find some sequence of operations of length <= k to make the k last bits equal for some 1 <= k <= 3, this is just a bunch of cases. Repeat the process until length <= 4, then run a simple brute force.
Very interesting to know it can be done efficiently. Thank you!
When you say it's optimal, do you mean that your solution uses at most $$$n$$$ operations and there exists no solution that uses at most $$$n-1$$$ operations?
There's another stronger notion of "optimal", which would be your solution uses the minimum number of operations possible for each given test case -- does it satisfy that too?
The implementations provided are very beautiful and elegant. For C2,
Another approach is to optimize the simulation for solution 2 from the easy version. You can do this with a data structure such as a balanced binary search tree in O(nlogn) time
, how does one do this simulation using a BST?I've actually used a Fenwick tree: for each position, I save the bit that was initially in that position. I use the difference array (so that it's possible to do point queries and range updates). For each move, it's easy to calculate the initial position of the bit that is in the first position before that move (the pattern is $$$1, n, 2, n - 1, \dots$$$). The updates are also nice (the ranges are $$$[1, n], [2, n], [2, n - 1], \dots$$$)
87569413
Treaps and splay trees are examples of binary search trees that can implement this in $$$O(\log n)$$$ time per flip. You can read about reverse operations on a treap here: https://cp-algorithms.com/data_structures/treap.html
The idea is very similar, in that you split the treap to identify the interval you want to flip, then push flags when needed, and inverting bits when the flag reaches a leaf.
This is my solution using Treap. It has some useless things cause I recycled part of the code.
Anyone here who tried solving D2D/D1B using memoization. Here is my time limit exceeded solution for this: https://codeforces.me/contest/1382/submission/87615728. What I did was, get all the numbers greater than the current number and then put the numbers in between, into one array and then do the same for the next element alternating between arrays. Help appreciated.
The time complexity in solution2 in C1 should be O(t*n^2)? Do I need to take t into account? In this case, it seems to be overtime, because both t and n may reach to 1000. Thanks.
No u don't need to consider t.. As it is mentioned that the time limit of 1(or)2sec is per testcase
Thank you. I didn't look at it carefully.
Actually the time limit applies to all test cases in the same file. The real reason it doesn't matter is that the sum of n across all test cases is small.
Monogon In the editorial for problem E what do you mean by forced matches? Thanks!
I mean when we shuffle colors around, we are forced to have a certain number of them as fixed points. For example, if we reorder the colors 1,1,1,2, no matter what there will be at least two indices where the color matches. So I say there are 2 forced matches.
using
bitset
in div2D/div1B : submissionMost red coders also did the same. Is there any reference where i can read about how it works? Thanks
Wow I did get the right idea on how to solve Div 2 D — Unmerge. But for some reasons my Python 3 solution keeps getting Runtime Error. Earlier today I got another Runtime Error on a different practice problem with Python and consequently I discovered about Python's small recursion depth limit (~1000).
I have been enjoying coding with Python because of its short, clean syntax but now I realize my lack of knowledge about how Python works internally makes it harder for debugging.
I guess it's time to go back to C++. Or at least I will use C++ when trying to solve C and above :P.
Thanks for the great contest!
For problem 1382D — Unmerge, if we consider the fact that every element will belong to either 1st set or 2nd, can we do a DP like this way? Is there any overlapping subproblem? I tried but could not find any. Can anyone suggest whether it can be solved that way or not? I wanted to solve it other than the subset-sum DP that the editorial has suggested.
For example, you could keep an array
dp[i][j][k] = x
wherei
= length of the prefix of $$$p$$$,j
= number of elements in the prefix of $$$p$$$ that belong to the array $$$a$$$,k
= the array that contains $$$p[i]$$$ ($$$1$$$ if it's the array $$$a$$$, $$$0$$$ otherwise),x
= the maximum possible index such that $$$p[x]$$$ and $$$p[x - 1]$$$ are in different arrays. The transitions are pretty intuitive.87598663
Could you please explain why are you maintaining only a given maximum x, for an i , j, k ? In other words, why is it dp[i][j][k] = x and not dp[i][j][k][x] = true / false, something like that? In other words, why is the maximum x always best?
You can change array iff $$$p[i]$$$ is greater than all $$$p[j]$$$ such that $$$j \geq x$$$, and keeping the maximum is optimal because if the condition is true for some $$$x$$$, it's true also for $$$x' > x$$$ (the indices with $$$j \geq x'$$$ are a subset of the indices with $$$j \geq x$$$)
You mean if p[i] is greater than all previous p[j] then we could also have kept p[i] in the other array, so this gives p[i] more freedom, so we try to keep max(p[j]) as less as possible?
Very nice idea!
Yes.
I think I arrived at something sort of similar: 109365062
i m not able to understand the tutorial of sequential nim pls can someone explain it
I'll explain my solution to you
So initially let's assume the sizes of all the piles are greater than 1
Notice that the first player can always leave one stone remaining in a pile so that the second player has no other option than to take the remaining stone in the pile (since you must choose from the leftmost non-empty pile) and continues this till it reaches the last pile
Let's assume the sizes of the piles are $$$a_0, a_1, \ldots, a_{n-1}$$$
The gameplay will look like this
Pile $$$0$$$ :- First chooses $$$a_0 - 1$$$ stones, second has to take remaining stone
Pile $$$1$$$ :- First chooses $$$a_1 - 1$$$ stones, second has to take remaining stone
Pile $$$2$$$ :- First chooses $$$a_2 - 1$$$ stones, second has to take remaining stone
.
.
.
Pile $$${n-1}$$$ :- First takes the whole pile and wins the game
So with this it should be obvious that the first player always has an advantage since he can force the moves of the second player
But if the size of the beginning pile is 1 notice that the first player doesn't have a choice but to take the pile making the second player the one with the advantage
So basically the parity of the ones at the beginning excluding the last pile will determine the player with the advantage
Submission: Link
Hope this helps!.
This solution explains better than editorial. Thanks. And the best part was you haven't included unnecessary templates which makes it very convenient to understand. Kuroni SecondThread
is it possible to do problem D without DP?
can anyone help me out that in problem E unmerge. My approach was to count maximum length of increasing subarray in array of p of length 2n.If this length is >=n then answer is "YES" otherwise "NO". As for two different array A and B there should exist such a subarray? can anyone tell me why this approach is wrong?
Look at 11, 10, 13, 12, 15, 14, 17, 16. The longest increasing subarray is of size 2, but you can easily build a and b.
a = 11, 10, 15, 14
b = 13, 12, 17, 16
ok thnx now in understood
I submitted two solutions, one with vector and other with array. The one with vector got TLE, and the array was accepted in 46ms. I was astonished.
vector (TLE) — https://codeforces.me/contest/1382/submission/87648649
array (AC) — https://codeforces.me/contest/1382/submission/87648751
The second part of your dp[][] array isn't big enough so you end up writing outside of the array and corrupting your stack. It's purely luck that the corruption doesn't break your array solution too.
For the below testcase check is [1,4] and dp[1][check[1]] is out of bounds.
So it could have been hacked. Damnn that was nice observation
My solution to C2.
Lets do things like in second solution to C1, and we need somehow to reverse string quickly. Let all operations with reverse that we have done so far will be array $$$k$$$. Now we are going to fix $$$i$$$ bit of string. I assume that $$$k_j \geq i$$$ We need to find out what number is on $$$i$$$s position in string. Before last operation it was on pos $$$k_m - i - 1$$$. Before last two on $$$k_{m - 1} - (k_m - i - 1) - 1$$$. If we open brackets its easy to see that we have formula for initial position of i depending only on parity of m, its easy to count it with some sums. Now about our assumption about $$$k_j \geq i$$$. Sometimes we should flip first letter of string, i won`t add this operation to list, I only flip it on its position in string.
Code
It may seem overcomplicated, but I just wanted to share this.
If anyone need detail explanation for C1 and C2 Here
In div2 Problem E mastermind can someone explain it to me that why can't we continue to greedily choose colors for the remaining n-y garbage values(the ones we are going to replace with some unused color) after greedily choosing x perfectly matching values, because we can further reduce f using these values, I realize that that would also reduce the spaces available for imperfect matches, but I a not sure why it should harm the arrangement in any way.
Consider the second test case of the sample. $$$x=3, y=4$$$, and $$$b=[1,1,2,1,2].$$$ Let's see what your solution does, if I understand it right.
First you greedily choose $$$x=3$$$ spots to match: $$$[1,1,2,\_,\_]$$$. Then you fill in $$$n-y=1$$$ garbage value: $$$[1,1,2,3,\_]$$$. But now it's impossible to shuffle the $$$1$$$ remaining index to avoid a perfect match.
The reason this fails is that the colors you fill with garbage values should still be available for the imperfect matches.
ok, Now I understand ....using garbage values to try and decrease f might not work because we might not be able to decrease f right away( as there can be many candidates for f) and will also loose a place in doing so which is not optimal....Thanks for the explanation....
Did anyone solved div1C/div2E using Hall's marriage theorem to prove correctness?
In Div2D(Unmerge), to find subset-sum I used the algorithm with TC:- O(N*M) & SC:- O(N*M), I got TLE in the contest. After the contest, I got to know about an algorithm that uses Linear space to find subset-sum but the TC of that algorithm is same as O(N*M), but it got accepted. Can anyone explain why I am getting TLE in the first approach? First Approach:- https://codeforces.me/contest/1382/submission/87597226 Second Approach:- https://codeforces.me/contest/1382/submission/87612296
You need to do something better than memset on the entire dp array. Setting 4 billion ints to -1 isn't going to fit in the time limit.
Thank You! Found my mistake!
In Solution-2 of "C2-Hard Version" editorial it is mentioned that the simulation can be optimised by the use of balanced binary tree, can someone elaborate on that please ?
My Solution for C1-87677440
Can Anyone Tell What will be the Time Complexity of my Solution Mentioned above.
I think its O(n^2) (Considering the Complexity of reverse function too ).
Can Anybody Correct me if i am wrong?
one of the most balanced contests in a long time Monogon , u rock !!
can anybody point out any mistake in B. here is my code in c++. 87685097. thnx in adv
What you are doing is counting the number of piles of '1' elements, whereas, for the correct solution, you need to count the number of consecutive '1' sequentially from the starting. But Why ? Because the person that encounters the first pile with elements greater than 1, will win the game, since they both make optimal choices. @daddy_puff
Need help!! My solution for div2 problem E/ div1 problem c Mastermind fails on test case 2 with the verdict "wrong answer jury has a solution but participant doesn't (test case 40)". I can't understand why is it so.....would appreciate if some one could help.
Can anybody please tell me that is there any way to optimise my solution using the same approach as I have done for problem div-2 D because it is showing TLE https://codeforces.me/contest/1382/submission/87693512
Can someone explain the observations made in Div2 D. I am unable to understand the editorial Sorry if i am missing something really silly
The suffix starting at the largest element must be a contiguous block in one of the two partitioned arrays. Once thats done, imagine stripping off this suffix, and putting this whole suffix in one of the arrays. Apply the same argument to the suffix of second largest array, this must also be a contiguous block in one of the two arrays. At the end, you will end up saving different lengths of suffixes. let's say you have p of these lengths. The answer is "YES" if you can combine all these p lengths into two segments, each of length n. So if any subset sum is n, the sum of the remaining lengths will also be n. These can be combined together to get two segments of length n, which can finally be combined to get the full array of length 2*n.
Let's take an example:
1, 5, 2, 3, 6, 4, 8, 10, 9, 7
You will get the following suffixes if you consider the suffix of first largest, second largest, 3rd largest and so on
[10, 9, 7] [8] [6,4] [5, 2, 3] [1]
Their lengths are 3, 1, 2, 3, 1. Is there any subset with length 5? Yes. Lets combine [6, 4] and [5, 2, 3] You get [5, 2, 3, 6, 4] This is partition 1.
Now lets combine
[1] [8] --> [1, 8]
[1, 8] [10, 9, 7] = [1, 8, 10, 9, 7]
Finally [1, 8, 10, 9, 7] + [5, 2, 3, 6, 4] = [1, 5, 2, 3, 6, 4, 8, 10, 9, 7]
The answer is no if there does not exist a subset with sum = n. Because you can never get 2 arrays with length n each. Hope this helps!
Thanks a lot I figured out the pattern but was unsure how to proceed with it.
My Approach for DIV2 C2
We come from last, i.e. prefixes are n,n-1,n-2,.. and at times we may have to flip first element.
say n = 6, x' indicates conjugate of that element.
1 2 3 4 5 6
6' 5' 4' 3' 2' (1'/1) (prefix — 6)
2 3 4 5 (6/6') (1'/1) (prefix — 5)
5' 4' 3' (2'/2) (6/6') (1'/1) (prefix — 4)
3 4 (5/5') (2'/2) (6/6') (1'/1) (prefix — 3)
4' (3/3') (2'/2) (6/6') (1'/1) (prefix — 2)
(4'/4) (3/3') (2'/2) (6/6') (1'/1) (prefix — 1)
We can see a pattern here and at before every flip we may or may not flip the first element
My solution : 87780335
For the The hard version, I actually found another deterministic solution inspired by the first solution to the easy one. I took them 3 chars by 3. this means that I have 8 states and when I tried to see the transitions between any of these, it was in range [0,4] -> now add the 2 steps to make the substrings of length three in the first 3 indices and then bring them back without changing any thing else and you get a range of [2,6]. Also, keep in mind, that you need to reverse the substrings of length 3 on the target as well as the input. if n%3 = 1 just fix the first bit, and if n%3 = 2 you need 1 step for first bit and 3 for second(using same method as the easy version) thus 2*n atmost for the reminder and 2*n atmost for the part divisible by three which is range [2,6] per 3 chars. Calculating the transitions for the states was rather easy by hand and other than that I just needed to loop in multiples of three and access the precalculated transitions so O(n)
This is the interesting part of the code:
https://codeforces.me/contest/1381/submission/87817029 My submission :D
For C1/C2 I was thinking a solution on these lines...
Suppose we have
a = a_1, a_2, a_3 ... a_n-2, a_n-1, a_n
b = b_1, b_2, b_3 ... b_n-2, b_n-1, b_n
Suppose we have a operation called "OP" which does the following:-
It tries to match first element of a and last element of b, if a_1 == b_n, then we can flip the first bit using prefix operation on prefix of length 1 and then apply prefix operation on prefix of length n. This make the changes to the array in the following way.
a = a_n, a_n-1, a_n-2 ... a_3, a_2, a_1
b = b_1, b_2, b_3 ... b_n-2, b_n-1, b_n
Then we try to match b_n-1 with a_n using the same steps as above but apply prefix operation on prefix length n-1 instead of n. After this we have:
a = a_2, a_3, a_4 ... a_n-1, a_n, a_1
b = b_1, b_2, b_3 ... b_n-2, b_n-1, b_n
Since we now know that a_n = b_n-1, and a_1 = b_n, we now have a recursive problem...
a = a_2, a_3, a_4 ... a_n-3, a_n-2, a_n-1
b = b_1, b_2, b_3 ... b_n-4, b_n-3, b_n-2
That is we have new "a" array with first and last element removed and new "b" array with last 2 element removed.
I was wondering if someone solved this problem on these lines. I am getting wrong ans for this. Can't see the flaw in the solution.
PS: there are some edge cases when n<=3
In Div1 E it is sufficient two have a pivot p with 3 children with length more than the snake's length l.If yes than why the solutions are using two pointers.
Can anyone tell me what this means? ops1.insert(ops1.end(), ops2.rbegin(), ops2.rend()); 1382C2 — Prefix Flip (Hard Version)
I found someone's solution for problem C2 ,really cool implementation 191239865.
could someone please explain the O(n.route(n)) optimised solution.I have understood the logic and the O(n^2) solution has been implemented but it would be grtt if someone could help me understand the optimisation implementation