Codeforces Round #585 Editorial

1215A - Yellow Cards

1215B - The Number of Products

1215C - Swap Letters

1215D - Ticket Game

1215E - Marbles

1215F - Radio Stations

• 21 month(s) ago, # ^ |

  God level explanation!

• 7 months ago, # ^ |

  I think we only have to look at cases where Monocarp adds digits 0 or 9, since, if he adds any other digit d, his chances of winning can improve by either changing d to 0 or changing d to 9 (for intuition, we can think that Monocarp will want to take "extreme" steps because he wants to make the two sides unequal).

  Also, we can just look at "surplus" question marks, since, if ? exist on both sides, Bicarp will always add the same digit that Monocarp added, but to the opposite side. This can be proved as well (I think it has something to do with Nash Equilibrium, but for intuition, we know that Bicarp will not like whatever Monocarp does, and will try to nullify it).

  The above statements (if properly proved) will greatly simplify your proof.

if(a[i]==0)

• 2 years ago, # ^ |

  That's just for input error or testcase error

• 2 years ago, # ^ |

  I think he just considered a[i] == 0 case too. But as given in question there are no element with 0 value so we can just skip this condition , rest of the solution is same .

• 2 years ago, # ^ |

  Nice solution!

• 2 years ago, # ^ |

  for problem B

  • 2 years ago, # ^ |

    The write to arr[(n << 1)] on line 18 caused array index overflow.

    Increasing the size of the array seems to work.

     	long ans[2];
     	cin >> n;
     	//vector<long> arr(n << 1);
    -	long *arr = new long[(n << 1)];
    +	long *arr = new long[(n << 1) + 1];
     	cin >> next;
     	if (next > 0) {
     		ans[0] = arr[0] = 1;

    • 2 years ago, # ^ |

      That's stupid. xd

• 2 years ago, # ^ |

  For those of you who are as confused as I was, I asked my friend who ACed this problem and the explaination is as follow:

  • When we transit from one dp state to another, we only consider types that are in the mask. So when we try to place type i as the last marbles in this dp state, each swap of type i marble with the other marbles is counted in cnt[j][i], for some j in the mask. So the summation of cnt[j][i] is indeed the number of extra steps that we need to take.
  • The cue to understand the dp state properly is to know that dp[mask] means we only consider marbles that are in the mask and ignore other types. Take the same example {2, 3, 1, 2} here. Say we wanna transit from dp[011] to dp[111] (adding type 3 marbles), and want the last marbles to be of type 3. dp[011] means the number of steps needed to reorder {2, 1, 2}, as we ignore type 3 marbles. Thus dp[111] equals to summation of cnt[j][3] + dp[011].

  I hope this explanation helps.

  • 20 months ago, # ^ |

    can you make me understand why does cnt[j][i] is indeed the number of swaps required. because as far as i know in the mask the positions of the 1s' in the mask have already changed. And the precalculated cnt[j][i] will then remain invalid. Where is the flaw in my reasoning??

    • 20 months ago, # ^ |

      cnt[j][i] would only factor in the relative positions between type i and j. i.e. only the swaps between type i and j are counted, swaps between type i and another type k would be taken care of in cnt[k][i], and so is the case between type j and type k.

      When you try to move type j marbles in front of all the marbles in mask, each swap would be counted only once in cnt[j][i], for some i in the mask, because we only consider type j and types that are in the mask.

      Hope the explanation helps.

      • 20 months ago, # ^ |

        Correct me if i am wrong this then means, that when bit i is moved ahead of all bits marked 1 in mask then later on when the bit k is added is already taken care of despite the change in positions or in other words cnt[i][k] when added already takes care of bits that are marked 1.

        • 20 months ago, # ^ |

          It's not proper for you to think that way because only means types in mask is "sorted" in some order, not necessarily means type i is at the very beginning. We don't really have to care about the order of how it is "sorted".

          Maybe it's better to think of the dp transition this way: when you try to "sort" all marbles of type k and types in mask, one way you can do is to put all types in mask in front of type k, this is what accounts for. Then you "sort" all the marbles that are in mask, which is what accounts for. You sum these two terms up to get under this configuration.

          • 20 months ago, # ^ |

            ← Rev. 2 →  

            0

            Sorry if I am being very stupid,if the mask elements are already sorted, then isn't it possible that cnt[j][i], doesn't give the right value to add to the dp transition.I mean to say if you are swapping then don't you have to swap types of colour not in the mask . How are they accounted for?

            • 20 months ago, # ^ |

              Swaps involving types not in mask will be accounted in a later stage where that type is being considered in the state transition

    • 18 months ago, # ^ |

      This is the beauty of this solution, though "it may seem" the elements in mask have gone left, we haven't paid the entire cost! In the sense while moving to the left, the mask elements may have crossed some non-mask elements also, that should have costed some swaps but we never paid it, now for adding color j into the mask, already present mask elements must go left,from the intitial point they may have travelled some crossing j due to earlier added mask elements, but we never paid that before, and now the mask elements have to go further left, so we have 2 debts to settle,i.e cost for all the mask elements should go from intitial position to complete left of j, i.e all i belonging to mask should go to left of j and by definition that is sigma(cnt[i][j]).

      If we take an example : 3 2 4 3. Say we first add 4 to mask, we don't have to pay anything, now let us add 3 to mask the scenario becomes 4 3 2 3, and we have to pay 1, i.e. cnt[4][3], but if you observe we never paid for crossing 2,because we are paying only for elements in the mask. Now let us add 2 to the mask, we are paying cnt[3][2] + cnt[4][2], the total sum is cnt[4][3]+cnt[4][2]+cnt[3][2], we are paying the total cost in installments in different transitions. In short, say a color i, comes to the very front, the cost is cnt[i][1]+cnt[i][2]... ,but in one transition we pay for each element in the mask to cross the newly added element only, but when later adding another element to the mask we pay for that too!

• 2 years ago, # ^ |

  Why you initialized pos=1 ?

  • 2 years ago, # ^ |

    i am assuming 1 beforehand and considering n+1 elements,u could see that for prefix conventions if p[r]*p[l-1] denotes the sign of segment [l,r].so for 0 u need something before it.

• 2 years ago, # ^ |

  Can you explain me why you can caculate the number of pos subsegment by (pos*(pos-1))/2+(neg*(neg-1))/2;

  • 2 years ago, # ^ |

    consider we have a sequence like this

    +-+-+
    
    Then he is increasing pos whenever curr is +;
    initially,
    curr = 1, pos = 1;       (*) 
    + ->curr = 1, pos = 2;   (*)
    - ->curr = -1, pos = 2;  
    + ->curr = -1, pos = 2;  
    - ->curr = 1, pos = 3;    (*)
    + ->curr = 1, pos = 4;    (*)
    Therefore, neg = 5+1 - pos = 2;

    Notice the (*) denotes all the indexes where the curr == 1, Now see that on choosing any indexes from all the (*) and forming a segment of it will form a positive segment

    Example here (*) = {0,1, 4,5} choosing (l,r] as subsegment of these indices will give you positive segment. Number of ways = (pos)C2;

    Now, similarly you can see why he is adding negative count as (neg)C2;

  • 21 month(s) ago, # ^ |

    He is just multiplying the prefix values of same signs by taking nc2=n(n-1)/2. This, is in turn ,directly giving him all the positive values.

• 2 years ago, # ^ |

  Wow, beautiful solution brother

• 2 years ago, # ^ |

  Can u explain um_nik's solution please? i am not able to understand how multiplying the positive and negative gives the answer for all the subsegments

• 2 years ago, # ^ |

  whoa... just briliiant. Thanks for sharing.

• 2 years ago, # ^ |

  How did you interpret the equation of maxvalue on each side to be (number of ?/2)*9 + (?%2)*9 ??

  • 2 years ago, # ^ |

    Greedily, so suppose monocarp try to make the left side max he will get one more chance than bicarp to do so. so if it's odd he will get the last chance to increase it. Same goes for bicarp. If suppose monocarp tries to increase left bicarp will get one more chance to increase right side. And then after the ? is finish on either side bicarp will start minimizing the other side. It just works lol. Also upvote if u find it helpful :p

    • 2 years ago, # ^ |

      So you are saying that Monocarp will try to increase the sum of one side by changing '?' into 9, and bicarp will change '?' on the same side into 0. So Monocarp has at most (number of '?' on that side)/2 chances and then +1 if the number of '?' is odd. But though your solution is fairly simple but it is hard to see why this actually "works"...

• 21 month(s) ago, # ^ |

  Your approach is failing at s="441???" Monocarp has more chances here he wins in every condition. But your output is Bicarp

  • 21 month(s) ago, # ^ |

    Unfortunately you missed the last sentence of the input section which states that "The number of "?" characters is even".

• 2 years ago, # ^ |

  For the second part, let us suppose C1>C2. Let C1 = x+C2. So for both sides upto the first C2 positions on either side -> i.e. C2 positions in first half and C2 positions in second half, if Monocarp gives value 'val' on side, Bicarp gives value 'val' on the other side. So they even out each other. This happens till C2 positions on both sides are filled.

  So finally we have x positions remaining in the first half after this process is done. This reduces the second part of the solution to the first part of the solution.

  Similar logic if C2>C1 for the second part also.

• 23 months ago, # ^ |

  ← Rev. 2 →  

  0

  In C, what would the solution look like if the strings were allowed to have characters from a..z Enchom BledDest spookywooky

  Thanks!

  • 14 months ago, # ^ |

    its strange , Its been 16 months still no comment on @rishi's comment

    In C, what would the solution look like if the strings were allowed to have characters from a..z __

• 2 years ago, # ^ |

  Can u pls explain ur approach in detail??

  • 2 years ago, # ^ |

    ← Rev. 8 →  

    0

    I used a DP approach for this problem; keeping track of two values:

    • = number of subsegments with positive product with last index
    • = number of subsegments with negative product with last index

    Transitions should be quite elementary if you think about what adding a positive/negative element would do to the product of a subsegment.

    Final answer is and

    Code: 60664552

    • 22 months ago, # ^ |

      very good & easy process. thanks Spheniscine

pos[0] = 1 if v[0] > 0, otherwise 0
neg[0] = 1 if v[0] < 0, otherwise 0

pos[x] = 1+pos[x-1] if v[x] > 0,
pos[x] = neg[x-1] if v[x] < 0

neg[x] = neg[x-1] if v[x] > 0,
neg[x] = 1+pos[x-1] if v[x] < 0

• 2 years ago, # ^ |

  What you are saying is not always true. For example, let's have an array 5, -3 Then pos[0] = 1, neg[0] = 0. neg[1] = 2, pos[1] = neg[0] + 1 = 1. But pos[1] cannot be 1 because there is no subsegment that ends at index 1 with product being positive.

  • 2 years ago, # ^ |

    Sorry, I had messed up the transitions. They're correct now. Thanks for the feedback :D

• 22 months ago, # ^ |

  Can you please explain your approach to this problem B

  • 22 months ago, # ^ |

    Consider this example:

    a = {1, 2, -2, -5, 4}

    Now you have got two arrays pos[n] and neg[n]. Each of them counts the number of subarrays that end at position i and have the product of their elements as positive and negative respectively.

    For the above example, pos[0] = 1 and neg[0] = 0

    Now for any position i, if a[i] is negative then you will have: neg[i] = 1 + pos[i - 1] and pos[i] = neg[i - 1].

    Otherwise, if a[i] is positive then: neg[i] = neg[i - 1] and pos[i] = pos[i - 1] + 1

    So, in the above example you will have pos[n] = {1, 2, 0, 3, 4} and neg[i] = {0, 0, 3, 1, 1}

• 12 hours ago, # ^ |

  Case:

  (i) s1="aa" & s2="bb" then s1==s2 can be done by just a single swap(0,1) => s1="ba" & s2="ba".

  (ii) s1="ab" & s2="ba" then s1==s2 can be done by 2 swaps (1,1) => s1="aa" & s2="bb" now repeat the above process that is swap(0,1) s1="ba" and s2="ba".

  Cases like s1="a" s2="b" , s1="aba" s2="bab" s1="aabbb" s2="babaa" & so on can not be make s1 equals s2

  Now task is to first not consider all such indices i at which s1[i]=s2[i] , then divide the string s1 and s2 in above two cases and store indexes for a in vector v1 and b in vector v2 for s1 or s2 .

  if(v1.size() is even and v2.size() is also even this imply the case(i) so we have answer v1.size()/2 + v2.size()/2 as we can swap each pair of a & b separetly.

  if(any size of both vector are odd ) this implies case(ii) so we have answer =v1.size()/2 + v2.size()/2 +2

  +2 because when we are done with all the swaps we will only left with the case like "ab" and "ba" which can be done in 2 swaps .

  here is my solution: https://codeforces.com/contest/1215/submission/148853299

  ps: if you didn't get what i want to convey then you can ask me again . Happy to help:)

• 2 years ago, # ^ |

  Well, initially fcspartakm proposed this problem on lower constraints, so it could be solved with dynamic programming. Then I thought about how this problem can be solved using the special structure of allowed turns (they are symmetric). I can't remember how exactly I came to the equality , but it was something like that: if the first player wants to win, they should either make the balance very low, or make it very high. So I tried to analyze these two cases (the first player wants the balance to be as low as possible or as high as possible), and then somehow arrived at this answer. I think that this formula is easier to come up with if you have mathematical background, but if you don't have it, it might be much easier to find an approach more related to programming than to maths.

  I actually wanted to make this problem interactive, where the contestant should play as the second player, but, unfortunately, this was unacceptable for The Quals.

• 18 months ago, # ^ |

  could you explain your states a bit more and also the transitions , because maybe iam not pretty lucid about them thank you!