Monogon's blog

By Monogon, history, 4 years ago, In English

I hope you enjoyed the contest! I will add implementations later.

UPD I've added implementations.

1382A - Common Subsequence

Tutorial

Implementation

1382B - Sequential Nim

Tutorial

Implementation

1382C1 - Prefix Flip (Easy Version)

Tutorial

Implementation 1 Implementation 2

1382C2 - Prefix Flip (Hard Version)

Tutorial

Implementation 1 Implementation 2

1382D - Unmerge

Tutorial

Implementation

1382E - Mastermind

Tutorial

Implementation

1381D - The Majestic Brown Tree Snake

Tutorial

Implementation

1381E - Origami

Tutorial

Implementation

  • Vote: I like it
  • +497
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 5   Vote: I like it -27 Vote: I do not like it
Deleted
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can submit once system testing is over.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it -13 Vote: I do not like it
      Deleted
      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        It is. Interestingly, the approach you described is not the same as what is written in your code.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it
          Deleted
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            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.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Video Editorial of C2. Prefix Flip.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          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 :)

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Great explanation. thanks

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          nice explanation bro.... keep it up create more like this,not now but in future you sure get more and more likes ....

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Wonderful, you explained everything in such a simple manner, and everything in the editorial made sense after it. Thank you

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes the code is good to go but correct you last statement

    "If the number is odd then First player win else Second player win"

    with

    "If the number is even, then First player win, or else Second player win"

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you ensure that the players are playing optimally if you follow this scheme? If you can kindly explain....

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Consider the case :

        1 1 1 2 3 4 5
        

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          " 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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 say x and x > 1, then that player is in control of the game, and will win the game

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        To 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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep yep, I too did the same thing, counting the no. of consecutive ones in the prefix.

»
4 years ago, # |
Rev. 8   Vote: I like it +329 Vote: I do not like it

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!

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Ok I got something wrong in my code. My array f is too small.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      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 :)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you please elaborate your solution?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Code:

      I think it should be pretty intuitive.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone further explain how to optimise the 2nd solution for C1 with a segment tree?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

couldn't solve but really loved the problems Div2 C1, C2 and D.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone with a randomized solution for C2?

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

bye bye CM :(

»
4 years ago, # |
  Vote: I like it +52 Vote: I do not like it

I never thought that writing 'first' & 'second' instead of some random names would have been so helpful.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +248 Vote: I do not like it

    You would still be surprised how many questions we received of the form: "Who goes first? First or second?"

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      SUPERB!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      XD

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D2-C2, how exactly will we keep track of the first bit?
Won't it depend on a lot of other bits?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See my answer above

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have implemented it in my code using left and right pointers to our string — link

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +111 Vote: I do not like it

Video explanations if you are interested after you give Monogon contribution.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Loved this round!

»
4 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain more?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey... I did exactly the same using deque too lol! 87577133

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      looks like a notorious coincidence to me

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        notorious is a pretty bold term to describe it tho XD...

        i'd rather call it a brainsync 100 moment!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did without deque by using 2 variables start and end and count for inversions. but it wasted 10 min to got that.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$

If $$$head > tail$$$ then $$$tail = tail + 1$$$

If $$$head < tail$$$ then $$$tail = tail - 1$$$

  • If $$$a[tail] \neq b.back()$$$ then we must reverse

If $$$a[head] = b.back()$$$ then after reversing it will be different, so we have to flip it

Then we can reverse in $$$O(1)$$$ by swapping $$$head \leftrightarrow tail$$$

But becareful when we reverse it two times when the size is equal to one

My code
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Solution 4
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I solved C2 (Hard Version) with Doubly ended queue.
Here is my submission: 87597675

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

dp solution for B 87559531

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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. :(((((((

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    PyPy is quicker than python for everything except for input and output.

»
4 years ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

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 .

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Question E (Mastermind) reminded me of the question "Bulls and Cows"

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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').

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My Video solution for Problem B. Hope you Like It.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not 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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 4

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        "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"
        

        Can you please prove why this is true.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

How to solve div-2 D in O(n root n). Thanks in advance.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    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))

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      why your submissions are not visible?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 == n

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

Div1D potential solution

Does this work? If not, what is a counterexample?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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:

      Minimal failing test case
      Bug summary
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
4 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

Spoiler
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did the same, dp is the only way that i could think of and it is pretty simple

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice Contest!

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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..

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There is a dp approach which I have mentioned in one of the comments.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        maximum number of 1 such that $$$a_1=⋯=a_k=1$$$ i.e. consecutive 1s in the beginning. Read the editorial carefullly.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem div2D/div1B I saw some submissions using bitset. How to solve it using bitset?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In Solution 1 of C2, how is it possible to convert string 010 to 000 in 3 operations??

»
4 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

I love how Monogon has given 2-3 solutions for every problem

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 ago, # |
  Vote: I like it 0 Vote: I do not like it

4 years later we will see comments crying out for implementation

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
4 years ago, # |
Rev. 7   Vote: I like it +19 Vote: I do not like it

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:

  • ....001 -> flip the whole string
  • 011... -> filp prefix of length 1
  • 111... -> flip prefix of length 2
  • 001... -> flip prefix of length 1
  • 101... -> flip the whole string
  • .....010
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
4 years ago, # |
Rev. 11   Vote: I like it +8 Vote: I do not like it

"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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All the problems were interesting and statements were simple and straight..thanks Monogon!!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how we can use the randomization in third problem div2(1382C2) to reduce time complexity as mentioned in tutorial

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

bool w = 1;
for (int i = n - 2; i >= 0; --i) {
        if (w) {
	        if (v[i] == 1){
			w = 0;
		}else {
		        w = 1;
		}
       }else{
		w = 1;
	}
}
if (w) first
else second

code : 87607154

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls explain Div2 C2 Solution 2 from editorial , I know the N^2 solution...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look, you just need a data structure that allows you to do quickly the following:

    1. reverse a prefix.

    2. 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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

»
4 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I have 2 questions about Div. 2E/Div. 1C:

  1. How to prove that we can get at least 2f-(n-x) forced matches?
  2. Why are (n-x)/2 rotations of indices optimal ?

UPD: Never mind, I got answers by myself, if anybody has same questions, ask me and I will explain :)

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have the same question....I think the pattern would be alternate knitting but I can't do the math.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please explain

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide a sample code for Div2C2/Div1A2 that uses the solution 2 mentioned in the editorial for the problem?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Implementations for all problems are posted in editorial now.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

contest was awesome but the score distribution was not good div2 C2 was harder than B

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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".

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

»
4 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      By mistake I published the incomplete draft . I have edited it. I used the same concept for O(n) Approach. Please have a look.

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I solved B by dp lol My observation skills are low <.<

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 > ....

  • After we perform a swap at pos1, all the elements behind that will move to pos1 - i + 1.
  • When we perform a swap at pos2, all the elements will now move to pos2 - (pos1 - i + 1) + 1 = pos2 - pos1 + i.
  • Swap at pos3 gives, pos3 - (pos2 - pos1 + i) + 1 = pos3 - pos2 + pos1 - i + 1.

let's call pos1 - pos2 + pos3 .... as shift_pos.

ith bit will be at

  • shift_pos - i + 1 if i is odd. Hence the current value at ith position will be shift_pos - i + 1.
  • i - shift_pos if i is even. The current value at ith position will be shift_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).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was trying to apply this but was not able to do so.Thanks for explanation.

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very interesting to know it can be done efficiently. Thank you!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is my solution using Treap. It has some useless things cause I recycled part of the code.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    No u don't need to consider t.. As it is mentioned that the time limit of 1(or)2sec is per testcase

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you. I didn't look at it carefully.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Monogon In the editorial for problem E what do you mean by forced matches? Thanks!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

using bitset in div2D/div1B : submission

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Most red coders also did the same. Is there any reference where i can read about how it works? Thanks

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For example, you could keep an array dp[i][j][k] = x where i = 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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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$$$)

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think I arrived at something sort of similar: 109365062

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i m not able to understand the tutorial of sequential nim pls can someone explain it

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like 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!.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is it possible to do problem D without DP?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    1
    3
    4 5 3 2 1 6
    
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone need detail explanation for C1 and C2 Here

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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....

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Did anyone solved div1C/div2E using Hall's marriage theorem to prove correctness?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

one of the most balanced contests in a long time Monogon , u rock !!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody point out any mistake in B. here is my code in c++. 87685097. thnx in adv

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the observations made in Div2 D. I am unable to understand the editorial Sorry if i am missing something really silly

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot I figured out the pattern but was unsure how to proceed with it.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like 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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

                for (i = 0; i < n%3; i++)
			if (A[i] != B[i]) tripleOp(A, i);  // if i = 1 -> 1 is pushed, if i = 2 -> 2,1,2 are pushed
		for (i = n % 3; i < n; i += 3)
		{
			string RevTargA = A.substr(i, 3);
			reverse(RevTargA.begin(), RevTargA.end());
			string RevTargB = B.substr(i, 3);
			reverse(RevTargB.begin(), RevTargB.end());
			bitset <3> X(RevTargA), Y(RevTargB);
			Cnt++;
			Ops.push_back(i+3);
			for (auto T : Mat[X.to_ullong()][Y.to_ullong()]) //Mat[current][target] = vector of Operations
			{
				Cnt++;
				Ops.push_back(T);
			}
			Cnt++;
			Ops.push_back(i + 3);
		}
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what this means? ops1.insert(ops1.end(), ops2.rbegin(), ops2.rend()); 1382C2 — Prefix Flip (Hard Version)

»
22 months ago, # |
Rev. 9   Vote: I like it +1 Vote: I do not like it

I found someone's solution for problem C2 ,really cool implementation 191239865.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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