Monogon's blog

By Monogon, history, 2 months 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

»
2 months ago, # |
Rev. 5   Vote: I like it -27 Vote: I do not like it
Deleted
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can submit once system testing is over.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it -13 Vote: I do not like it
      Deleted
      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it
          Deleted
          • »
            »
            »
            »
            »
            »
            2 months 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.

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

        Video Editorial of C2. Prefix Flip.

        • »
          »
          »
          »
          »
          2 months 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 :)

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

          Great explanation. thanks

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          easy approach, thanks

        • »
          »
          »
          »
          »
          4 weeks 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 ....

  • »
    »
    2 months 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"

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

      Totally agree, in fact my code gets accepted on same idea.

    • »
      »
      »
      2 months 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....

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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.

          • »
            »
            »
            »
            »
            »
            2 months 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

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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.

»
2 months 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!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Agreed! This is probably the best contest I've ever seen on CodeForces!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    yeah, background stories just make the statements more confusing.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    Give Monogon some contribution.:))

  • »
    »
    2 months ago, # ^ |
    Rev. 5   Vote: I like it -29 Vote: I do not like it

    [Deleted]

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      Yes,It Happened with me :(

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      I agree.

      Got Wrong answer on test 15! Can someone please tell me what is wrong with the code? Submission Edit: found the problem it was really stupid. I guess pretests were short ;)

      Anyways, loved the problem Div2. D (although I was unable to solve it).

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

    Agreed .. This was one of the best division 2 rounds.. Hats off Monogon

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

    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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    You Forgot No QueueForces!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah my bad, how could I even miss it, edited thanks !:)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A very nice and balanced round! Solved some and then some to learn from.

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

good problem set and very fast editorial thanks to the makers and the testers of the round

»
2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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 :)

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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.

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

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

    Can you please elaborate your solution?

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

      I think it should be pretty intuitive.

»
2 months 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?

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    indeed and you're an inspiration bro ... all the best for CM again ..

»
2 months 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

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

Anyone with a randomized solution for C2?

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

Does a BFS tree search work for Div 2 C1/C2?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I created a pruned BFS search for Div 2 C1 but it quickly runs out of memory if you try to store the operation as the path taken.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I also tried to apply the same approach. It does run out of memory.

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

bye bye CM :(

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

  • »
    »
    2 months 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?"

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

      SUPERB!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      XD

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

»
2 months 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?

  • »
    »
    2 months 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

  • »
    »
    2 months 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.com/contest/1382/submission/87589106

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

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

Please , someone explain the approach to solce C2 of div 2.

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

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

someone explain B pls .why your current wise move cant be ulter by other player when ai > 1.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try drawing a decision tree for every turn. If the current element is greater than 1, then the player has 2 options, either he can pick all but one stones, or all stones. One of these causes that player to win and the other choice causes him to lose. Same thing will occur for all subsequent choices. But no choice can be made if the current pile has only 1 stone, since the player will have no choice but to take it. So the first point where any of the players can make a decision, decides who the winner will be

»
2 months ago, # |
  Vote: I like it +111 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Loved this round!

»
2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain more?

    • »
      »
      »
      2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      looks like a notorious coincidence to me

      • »
        »
        »
        »
        2 months 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!

  • »
    »
    2 months 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.

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

»
2 months 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

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

In problem A, I am getting Runtime error on pretest 1. here is my code:

t = int(input())

for i in range(t): a = int(input()) b = int(input()) li_1 = [] li_2 = [] for i in range(a): item_1 = input() li_1.append(item_1) for i in range(b): item_2 = input() li_2.append(item_2) li_3 = [] for number in li_1: if number in li_2: li_3.append(number)

if not li_3:
    print("NO")
else:
    print("yes\n")
    print(len(li_3),li_3)

I used python. where is the problem??

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

dp solution for B 87559531

»
2 months 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

»
2 months 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. :(((((((

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

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

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

  • »
    »
    2 months 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

  • »
    »
    2 months 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

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

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

»
2 months 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').

»
2 months ago, # |
Rev. 3   Vote: I like it -12 Vote: I do not like it

1382B — Sequential Nim Solution video : https://www.youtube.com/watch?v=DJr1eWcXGHU

1382C1 — Prefix Flip (Easy Version) Solution video : https://www.youtube.com/watch?v=uU8SUa4wrIE

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

where am i doing wrong for test case 1 case 4
question c1 please reply https://codeforces.com/contest/1382/submission/87600400 because i get the answer wrong answer a not transformed to b (test case 4) but on ide i get the a==b when i check final state of both strings

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ofcourse you get a==b in your ide. but perhaps you operation get over 3*n and system test only 3*n operation. so you got wa

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

Beautiful contest especially Div 2 C hard part! I just realised it was something related to linked list.... would love to see more contests from @Monogon

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

Can someone explain solution 1 of div2-c2. I understood the first part about converting into all 1's(or all zeroes) in O(n). Now how to get the required string?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you have to notice the sequence.. you can always find the ans less than 2n operation. 1. for i 0 to n 2. for each (n-i-1)th char of B string can match with either a[i/2] if i is even or a[n-1-i/2] if i is odd ... for detail you can check my code 87580566

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

I am wondering why this A solution 87591380 is giving WA, any help?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why are you swap m and n in intial..this is the reason you got WA.. when m>n you swapped the m and n then some value of array will insert into array B.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I believe that I have no clue why I did that, but does it really matter?

      I am just exchanging n and m values...

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        of course it matters system takes first n values for array A and next m values for Array B. but you swapped the value.. now out of (n+m) values first m values goes to Array A and next n values goes to array B so you never operate on desire arrays so you got BIG WA.. you can remove that swap operation you will definetly get Ac verdict

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, that is right...

          My fault

          Anyway, thanks for the clarification

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

can anyone explain editorial of div2 D problem?

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

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

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

anyone please explain approach of C2 . i was able to make 2*n operations but not able to optimise the code from 0(N^2) to some 0(N) . i was traversing the string a in the reverse direction . and if a[i]!=b[i] then I was comparing a[i] with a[0] .If they both are same then I just apply operation [0-i] else I apply the operation on [0-0] and then [0-i] hence making atmost 2*n operations . But this is O(N*2)How could i make it in 0(N) . ANY help is appreciated .

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you have to notice the sequence.. you can always find the ans less than 2n operation. 1. for i 0 to n 2. for each (n-i-1)th char of B string can match with either a[i/2] if i is even or a[n-1-i/2] if i is odd ... for detail you can check my code 87580566

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

I am fairly new to this. so forgive me if I am wrong. but this code failed. and I don't understand why. I was quite proud when I had coded this one but got disappointed when the pretest failed. any help would be appreciated. ~~~~~ def game(stones): firstMove = True secondMove = False idx = 0 while idx < len(stones): if idx == len(stones) — 1 and stones[idx] == 0: if firstMove: print('Second') if secondMove: print('First') break if firstMove: if idx == len(stones) — 1: stones[idx] = 0 secondMove = True firstMove = False continue if stones[idx] == 1: stones[idx] = 0 idx += 1 secondMove = True

else:
            stones[idx] = 1
            secondMove = True
        firstMove = False
    if secondMove:
        if idx == len(stones) - 1:
            stones[idx] = 0
            secondMove = False
            firstMove = True
            continue
        if stones[idx] == 1:
            stones[idx] = 0
            idx += 1
            firstMove = True

        else:
            stones[idx] = 1
            firstMove = True
        secondMove = False

T = int(input()) for i in range(T): n = int(input()) stones = list(map(int, input().split())) game(stones)

~~~~~

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

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

    • »
      »
      »
      2 months 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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        wow, I studied that theorem in probability but i can never think it can applied here in such beautiful manner. thanks for that theorem.. but i want to ask one more thing. In editorial there is a way to get this ans in O(n*sqrt(n)). Can you explain how can i find subset sum problem in O(n*sqrt(n)).. thanks in advance..

      • »
        »
        »
        »
        2 months 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.

    • »
      »
      »
      2 months 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

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

  • »
    »
    2 months 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))

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

      why your submissions are not visible?

      • »
        »
        »
        »
        2 months 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...

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes that would be very helpful ^_^

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give a proof for this "First notice that there are O(sqrt(n)) distinct values because 1 + 2 + 3...+k >= 2*n implies k = O(sqrt(n))"

»
2 months 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.com/contest/1381/submission/87596300

  • »
    »
    2 months 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

»
2 months 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?

  • »
    »
    2 months 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?

    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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.

»
2 months 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
  • »
    »
    2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please elaborate this part "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."

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

Nice Contest!

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

»
2 months 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

»
2 months 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.com/contest/1382/submission/87603260 Uncomment last two lines and run to see that a is onverted to b . Someone please explain!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For test case 4 in sample cases answer must be 7 1 10 8 7 1 2 1

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep I got it bro . I wrote wrong swap(). I used < instead of <= . Anyways thanks a lot .

»
2 months 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??

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

      • »
        »
        »
        »
        2 months 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

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

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

Can someone please explain me the solution 1 of div2-C2(hard) given in tutorial.I am not able to think a way in which the string is made all 0 in atmost n operations in O(n) time.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you have to notice the sequence.. you can always find the ans less than 2n operation. 1. for i 0 to n 2. for each (n-i-1)th char of B string can match with either a[i/2] if i is even or a[n-1-i/2] if i is odd ... for detail you can check my code 87580566

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

»
2 months 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?

  • »
    »
    2 months 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

»
2 months 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

  • »
    »
    2 months 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.

»
2 months 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??

»
2 months 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

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

  • »
    »
    2 months 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.

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

4 years later we will see comments crying out for implementation

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

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

@2wrist thank you!!

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

I got pupil lol! Thanks for an amazing contest with very interesting problems!

»
2 months 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.com/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
»
2 months 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)

»
2 months 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.com/contest/1381/submission/87606984

my solution seems like:reverse string a,trying to do something with first <=3 first bits,reverse string a

»
2 months 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!!

»
2 months 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

  • »
    »
    2 months 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.

»
2 months 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

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

Best Contest for me still now as I got +163, those subtask C1 and C2 were so interesting.Thank u monogon

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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

»
2 months 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 :)

  • »
    »
    2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please explain

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

what's wrong with this code? Problem C1 my submission is 87608593

»
2 months 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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Implementations for all problems are posted in editorial now.

»
2 months 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

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

Awesome problems.. c1 and c2 was really good.

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

»
2 months 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

  • »
    »
    2 months 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.

»
2 months 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".

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

I used a similar approach for C1 Suppose a1>1. If removing the entire first pile is winning, player 1 will do that. Otherwise, player 1 can leave exactly one stone in the first pile, forcing player 2 to remove it, leaving player 1 in the winning position. Otherwise, if a1=1, then it is forced to remove the first pile.. I have iterated over all the numbers with each time making a choice as removing the entire first pile is winning, player 1 will do that. Otherwise, player 1 can leave exactly one stone in the first pile, forcing player 2 to remove it and see who is the last one to choose. Can someone please tell what is the problem with this approach? link to my submission 87556049

»
2 months 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.com/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 :)

»
2 months 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!

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

»
2 months 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

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    at least you found the dp..
    spent hour just for B.. didnt even read D

»
2 months 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).

  • »
    »
    2 months 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.

»
2 months 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.com/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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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?

»
2 months 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?

  • »
    »
    2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months 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.com/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.

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

At last my rating increased <3

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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months 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.

»
2 months 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!

  • »
    »
    2 months 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.

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

using bitset in div2D/div1B : submission

  • »
    »
    2 months 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

»
2 months 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!

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

sir,for the second problem(sequential nim),I have a confusion. while taking off the stones from a particular pile do I know the number of stones in the next pile? if so then,consider the test case 5 3 8 1 6 4 what should be the answer to this according to you?

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

    Both persons know the number of stones on each pile in the first place, hence whoever gets the first chance to make an active decision will play in a manner such that he is guaranteed a win. Notice that by saying active decision, I mean to have piles with more than one stone.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for replying sir,but still I am confused,as the test case mentioned the following steps may happen 3 8 1 6 4 1 8 1 6 4 0 8 1 6 4 now if the if the first leaves 1 stone in this pile he wont be optimal as he knows that then he will lose. so my doubt is first should pick all the 8 stones from this pile resulting 0 0 1 6 4 is that how he wins?

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

While making all bits 0 in C2 solution1, consider the string 11011, according to the solution

  1. choose i=2 (1-based indexing)
  2. s = 00011, then i=3
  3. s= 11111

If we choose i = 5, it will become 00000. To apply operation in each step it will take O(n^2) complexity. How to resolve this?

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

can pls someone explain how second is wining in this case 1 2 2 1 1

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

    First takes 1 from first position(0 2 2 1 1) then second takes 1 from 2nd position (0 1 2 1 1) then first takes 1 from 2nd position(0 0 2 1 1) then second takes the entire pile at 3rd position(0 0 0 1 1) then first takes 1 from 4th position(0 0 0 0 1) then second makes the last choice(0 0 0 0 0).

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for the help so we have to find which player gets the first pile which is greater than 1 whoever gets the this pile wins,right?

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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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$$$)

        • »
          »
          »
          »
          »
          2 months 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!

»
2 months 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

  • »
    »
    2 months 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!.

»
2 months 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

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

Really hats off guys the approach of solution in Q C2 is really a fascinating and an elegant one , really a miraculous way!

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

is it possible to do problem D without DP?

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

"To fix the bit i (when si≠ti), we can flip the prefix of length i, then flip the prefix of length 1, and again flip the prefix of length i." how the author is getting to this solution? is he doing this by observation or is there any method in getting this solution?

»
2 months 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?

  • »
    »
    2 months 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

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

Check out our Video Editorials for the problems

A-Common Subsequence

B-Sequentials Nims

C1-Prefix Flip

C2-Prefix Flip(Hard)

Like, Share and Subscribe to our channel for more such editorials :)

»
2 months 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.com/contest/1382/submission/87648649

array (AC) — https://codeforces.com/contest/1382/submission/87648751

  • »
    »
    2 months 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
    
»
2 months 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.

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

If anyone need detail explanation for C1 and C2 Here

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

In problem B can we calculate the number of moves till end based on the conditions that : 1 — if(ar[i]==n-1) then moves++; 2 — else if(ar[i]!=1) then move+=2; 3 — else move++;

at the end if moves is even then second wins else first wins ? but i don't know where am i going wrong ?

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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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....

»
2 months 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?

»
2 months 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.com/contest/1382/submission/87597226 Second Approach:- https://codeforces.com/contest/1382/submission/87612296

  • »
    »
    2 months 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.

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

i cannot understand the solution 2 of prefix flip easy version.pls help

»
2 months 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 ?

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

This was the best contest.

No bullshit stories.

No confusing statement.

No long queue.

thanks Monogon for the contest!

»
2 months 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?

»
2 months 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 !!

»
2 months 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

  • »
    »
    2 months 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

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

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

Can anyone explain the editorial of div 2 D more elaborately?

»
2 months 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.com/contest/1382/submission/87693512

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

For c2(hard),can any one explain how to implement solution2 use balanced tree in O(nlogn)?

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

Soneone can cleary explain prolem D. I still don't understand it ?

»
2 months 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

  • »
    »
    2 months 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!

    • »
      »
      »
      2 months 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.

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

Wow. D is bootiful

»
2 months 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

»
2 months 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);
		}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

does anyone have code for solution 3 of c2?

»
2 months 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

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

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

Prefix Flip (Hard Version) in this problem my code convert first string into second string but my output is optimized and different but first string convert perfectly into second and my solution is not accepted. can anyone help me with this ?[submission:88217011][problem:1381A2]

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How could one possibly come up with a solution like Solution 1 of C1 during a contest? I could never do it if I haven't solved a similar question before.

»
4 days 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)