codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

451.md (8830B)


      1 Source: https://codeforces.com/blog/entry/13181
      2 
      3 **[451A - Game With Sticks](/contest/451/problem/A "Codeforces Round 258 (Div. 2)")**
      4 
      5 From a grid of size *n* * *m*, if we remove an intersection point, then the grid after removing the sticks passing through it, will of size *n* - 1, *m* - 1.
      6 
      7 Notice when the grid consists of a single horizontal stick and m vertical sticks, If we pick any intersection point, then the updated grid will be only made of vertical sticks. You can see that there is no intersection point in the grid now.
      8 
      9 So  
     10 *ans*(*n*, *m*) = *ans*(*n* - 1, *m* - 1) ^ 1.  
     11 *ans*(1,  * ) = 1  
     12 *ans*( * , 1) = 1
     13 
     14 So we can notice that answer will depend on the parity of *minimum*(*m*, *n*).  
     15 You can prove it using the previous equations. You can also check this by seeing the pattern.
     16 
     17 So finally if *min*(*n*, *m*) is odd, then Akshat will win. Otherwise Malvika will win.
     18 
     19 You can also observe that "players will play optimally" is useless in this case.
     20 
     21 Complexity : *O*(1)
     22 
     23 **Solution codes**
     24 
     25 * [my solution](//codeforces.com/contest/451/submission/7233706)
     26 
     27 **[451B - Sort the Array](/contest/451/problem/B "Codeforces Round 258 (Div. 2)")**
     28 
     29 Note that if from a given sorted array, if reverse a segment, then the remaining array will be arranged in following way. First increasing sequence, then decreasing, then again increasing.
     30 
     31 You can find the first position where the sequences start decreasing from the beginning. Call it *L*.  
     32 You can find the first position where the sequences start increasing from the end. Call it *R*.
     33 
     34 Now we just need to reverse the segment between *a*[*L*] to *a*[*R*].
     35 
     36 Here is outline of my solution which is easy to implement. First I map larger numbers to numbers strictly in the range 1, n.  
     37 As all the numbers are distinct, no two numbers in the mapping will be equal too.
     38 
     39 Let us define *L* to be smallest index such that *A*[*i*]! = *i*.  
     40 Let us also define *R* to be largest index such that *A*[*i*]! = *i*.
     41 
     42 Note that if there is no such L and R, it means that array is sorted already. So answer will be "yes", we can simply reverse any of the 1 length consecutive segment.
     43 
     44 Otherwise we will simply reverse the array from [*L*, *R*]. After the reversal, we will check whether the array is sorted or not.
     45 
     46 Complexity: *O*(*nlogn*)
     47 
     48 **Solution codes**
     49 
     50 * [my solution](//codeforces.com/contest/451/submission/7233716)
     51 
     52 **[451C - Predict Outcome of the Game](/contest/451/problem/C "Codeforces Round 258 (Div. 2)")**
     53 
     54 Let *x*1 be number of wins of first team in the first k games.  
     55 Let *x*2 be number of wins of second team in the first k games.  
     56 Let *x*3 be number of wins of third team in the first k games.
     57 
     58 Note that *x*1 + *x*2 + *x*3 = *k* ---(1)  
     59 |*x*1 - *x*2| = *d*1. — (a)  
     60 |*x*2 - *x*3| = *d*2. — (b)
     61 
     62 Note that |x| can be x and -x depending on the sign of x.
     63 
     64 Case 1: Assume that *x*1 > *x*2 and *x*2 > *x*3.  
     65 *x*1 - *x*2 = *d*1 ---(2)  
     66 *x*2 - *x*3 = *d*2 ---(3)
     67 
     68 Adding 1 and 2, we get  
     69 2*x*1 + *x*3 = *d*1 + *k* --(4)  
     70 Adding 2 and 3, we get  
     71 *x*1 - *x*3 = *d*1 + *d*2 ---(5).
     72 
     73 Now solve (4) and (5), we will get values of *x*1 and *x*3. By those values, compute value of *x*2. Now we should check the constraints that *x*1 ≥ *x*2 and *x*2 ≥ 3.
     74 
     75 Now comes the most important part. Number of wins at the end of each team should be *n* / 3. So if *n* is not divisible by 3, then our answer will be definitely "no".
     76 
     77 Note that if all of the *x*1, *x*2, *x*3 are  ≤ *n* / 3, then we can have the remaining matches in such a way that final numbers of wins of each team should be equal.
     78 
     79 Now you have to take 4 such cases. Implementing such cases in 4 if-else statements could incur errors in implementation. You can check my code to understand a simple way to implement it.
     80 
     81 I will explain idea of my code briefly, basically equation (a) and (b) can be opened with either positive or negative sign due to modulus.  
     82 So if our sign is negative we will change *d*1 to be  - *d*1. So if we solve a single equation and replace *d*1 by  - *d*1, we can get solution for the second case.
     83 
     84 All the cases can be dealt in such way. Please see my code for more details.
     85 
     86 *Complexity:* *O*(1) per test case.
     87 
     88 **Solution codes**
     89 
     90 * [my solution](//codeforces.com/contest/451/submission/7233730)
     91 
     92 **[451D - Count Good Substrings](/contest/451/problem/D "Codeforces Round 258 (Div. 2)")**
     93 
     94 Merging Step: We have to convert string like "aaaabbbaabaaa" into "ababa".
     95 
     96 *Important Observation*  
     97 A substring made of the string will be a "good" palindrome if their starting and ending characters are same. If the starting and ending characters are same, then the middle characters after merging will be alternating between 'a' and 'b'. eg. "abaa" is not a palindrome, but it is a good palindrome. After merging step it becomes "aba". Note that in the string left after merging, the consecutive characters will alternate between 'a' and 'b'.
     98 
     99 So if we are currently at the *i**th* character, then we can have to simply check how many positions we have encountered upto now having the same character as that of *i**th*. For counting even and odd separately, we can make count of a's and b's at even and odd positions.
    100 
    101 So if we are at *i**th* position, for counting even good palindromes, you just need to add count of number of characters a's at odd position. For counting odd good palindromes, you just need to add count of number of characters a's at even position.
    102 
    103 Complexity: *O*(n) where *n* is length of string *s*.
    104 
    105 **Solution codes**
    106 
    107 * [my solution](//codeforces.com/contest/451/submission/7233740)
    108 
    109 Note that you can also consult following comment for [alternate editorial](//codeforces.com/blog/entry/13111#comment-179408).
    110 
    111 **[451E - Devu and Flowers](/contest/451/problem/E "Codeforces Round 258 (Div. 2)")**
    112 
    113 The number of ways to choose *N* items out of *R* groups where each item in a group is identical is equal to the number of integral solutions to *x*1 + *x*2 + *x*3...*x**R* = *N*, where 0 ≤ *x**i* ≤ *L**i*, where *L**i* is the number of items in *i**th* group. Number of integral solutions are coefficient of *x**N* in [Product of (1 + *x* + *x* * *x* + ...*x**L**i*) over all $i$].
    114 
    115 You need to find coefficient of *x**s* in (1 + *x* + *x*2 + *x*3 +  + ..*x**f*1) *  *  * (1 + *x* + *x*2 + *x*3 +  + ..*x**f**n*).
    116 
    117 Using sum of Geometric progression we can say that (1 + *x* + *x*2 + *x*3 +  + ..*x**f*1) = (1 - *x*(*f*1 + 1)) / (1 - *x*).
    118 
    119 Substituting in the expression, we get (1 - *x*(*f*1 + 1)) / (1 - *x*) *  *  * (1 - *x*(*f**n* + 1)) / (1 - *x*).
    120 
    121 = (1 - *x*(*f*1 + 1)) * .. * (1 - *x*(*f**n* + 1)) * (1 - *x*)( - *n*).
    122 
    123 Now we can find *x**s* in (1 - *x*)- *n* easily. It is ![](https://espresso.codeforces.com/80d2d6201f529353bf07339a9eff960544560e51.png).
    124 
    125 You can have a look at following [link](http://math.stackexchange.com/questions/85708/negative-exponents-in-binomial-theorem). to understand it better.
    126 
    127 So now as *s* is large, we can not afford to iterate over *s*.
    128 
    129 But *n* is small, we notice that (1 - *x*(*f*1 + 1)) * .. * (1 - *x*(*f**n* + 1)) can have at most 2*n* terms.
    130 
    131 So we will simply find all those terms, they can be very easily computed by maintaining a vector<pair<int, int> > containing pairs of coefficients and their corresponding powers. You can write a recursive function for doing this.
    132 
    133 How to find ![](https://espresso.codeforces.com/27fba0c7c257199b7f3d35fcc17545d0bdfe5bdb.png) % p. As *n* + *s* - 1 is large and s is very small. You can use [lucas's theorem](http://www.cut-the-knot.org/arithmetic/combinatorics/LucasTheorem.shtml). If you understand lucas's theorem, you can note that we simply have to compute ![](https://espresso.codeforces.com/b420dac66e04f57f29954b0b8bb25f5d3f529bd8.png).
    134 
    135 Complexity: *O*(*n* * 2*n*).
    136 
    137 **Another solution based on [inclusion exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle).**
    138 
    139 Please see the following comments to get the complete idea.  
    140 [Comment 1](//codeforces.com/blog/entry/13181#comment-179490)  
    141 [Comment 2](//codeforces.com/blog/entry/13181#comment-179450)  
    142 [Comment 3](//codeforces.com/blog/entry/13181#comment-179491)
    143 
    144 **Solution codes**
    145 
    146 * [my solution (Java)](//codeforces.com/contest/451/submission/7233746)
    147 * [another (C++)](//codeforces.com/contest/451/submission/7233777)
    148 * [Inclusion Exclusion based solution](//codeforces.com/contest/451/submission/7241218)