codeforces-scrape

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

258.md (5289B)


      1 Source: https://codeforces.com/blog/entry/6213
      2 
      3 ### [259A - Little Elephant and Chess](/contest/259/problem/A "Codeforces Round 157 (Div. 2)")
      4 
      5 Obviously, the only correct rows are rows WBWBWBWB and BWBWBWBW. Only thing you need to do is to check whether each string is one of these. If yes then print YES, else print NO.
      6 
      7 ### [259B - Little Elephant and Magic Square](/contest/259/problem/B "Codeforces Round 157 (Div. 2)")
      8 
      9 Since each number is less than or equal to 105, you can loop all possible *a*1, 1 values, the rest of cells can be calculated from this.
     10 
     11 ### [258A - Little Elephant and Bits](/contest/258/problem/A "Codeforces Round 157 (Div. 1)")
     12 
     13 It's pretty easy to notice that you need to delete the first (from the left) 0-digit. The only catchy case is 111...111 — here you need to delete any of 1-digits.
     14 
     15 ### [258B - Little Elephant and Elections](/contest/258/problem/B "Codeforces Round 157 (Div. 1)")
     16 
     17 First of all, lets think about the problem of finding array *c**i* — the number of integers from 1 to *m* such, that the number of lucky digits is equal to *i*. It's pretty standart dynamic programminc problem, which can be solved with state [position][less][count].
     18 
     19 It can be solved directly using DP, but to simplify a bit you can use brute force (recursion) to brute all possible assignments of numbers of lucky digits in for all paries (up to 9 digits). Now you can divide all parties in several indepentent groups, each of which should contain the same number of lucky digits. Consider that the party of Litte Elephant is with number 1. Than assignment for the first position should have more digits than the sum of the rest (because of the statement). Since all groups are indepented (because there is no number that can have different number of lucky digits, obviously) you can find the number of resulting assignments for each group and find the final result by multiplying these all numbers and taking modulo 109 + 7.
     20 
     21 Consider that you have group of size *t*, each number of which should contain *l* lucky digits. That it's pretty easy to understand that the number of assignment is equal to (*c**l*) * (*c**l* - 1) * (*c**l* - 2) * ... * (*c**l* - *t* + 1).
     22 
     23 ### [258C - Little Elephant and LCM](/contest/258/problem/C "Codeforces Round 157 (Div. 1)")
     24 
     25 The complexity of the possible solution is *O*(*n* * *sqrt*(*n*) * *log*(*n*)). You can see that statement *lcm*(*b*1, *b*2, ..., *b**n*) = *max*(*b*1, *b*2, ..., *b**n*) is equal to statement "All the numbers *b*1, *b*2, ..., *b**n* must divide *max*(*b*1, *b*2, ..., *b**n*)". You can iterate that *max*(*b*1, *b*2, ..., *b**n*), let it be equal to *m*. Find all divisors of *m* and sort them — *p*1, *p*2, ..., *p**k*. For each *i* between 1 and *k* you can find (using simple DP) the number of numbers *a**j* that *p**i* ≤ *a**j* < *p**i* + 1 (if *i* = *k* than *p**i* + 1 = *max*(*a*1, *a*2, ..., *a**n*) + 1), denote it as *q**i*. Then the reuslt is equal to 1*q*1 * 2*q*2 * 3*q*3 * ... * *p**q**p*, because for each of the *q*1 numbers there is 1 way to assign, for each of *q*2 numbers there is 2 ways of assignments, and so on. But you should notice that if doing this problem in such way, you need to garantee that there is some *i* such *b**i* = *m*. Hance you need from the last multiplier (*p**q**p*) subtract (*p* - 1)*q**p* — all the ways that there is no number equal to *m*.
     26 
     27 ### [258D - Little Elephant and Broken Sorting](/contest/258/problem/D "Codeforces Round 157 (Div. 1)")
     28 
     29 ### [258E - Little Elephant and Tree](/contest/258/problem/E "Codeforces Round 157 (Div. 1)")
     30 
     31 Very useful thing in this problem is ordering all vertices in DFS order (preorped). After that any subtree can be represented as a some sequence of continuous vertices. Consider that we have some fixed vertex *v*. Which vertices should be included in *c**v*? Obviously, if in the path from the root to *v* is some non-empty vertex (i. e. such that has at least one integer in its list) than each vertex from substree *v* should be included in *c**i*, but since we now working with preorder traversal of the tree, we consider that every vertex from some segment [*l**v*, *r**v*] must be included to *c**i*. More generally, let for each vertex keep some set of segments (*l**k*;*r**k*). If on the *i*-th operation we have two vertices *a* and *b*, we add segment (*l**b*;*r**b*) to vertex *a*, and (*l**a*;*r**a*) to vertex *b*. Also for each vertex *i* (*i* = 1..*n*) we add segment (*l**i*;*r**i*), where (*l**i*;*r**i*) is a segment in our preored traversal for subtree *i*. After that, you can see that, if we unite all segments from all vertices on the path from the root to some vertex *v*, we find the result for *v*, which will be the size of the resulting set.
     32 
     33 So now we need some data structure that would support three operations: add(l, r), subtract(l, r), count(). The first one should add 1 to all positions from *l* to *r*, inclusive. The second should subtract 1 from all positions from *l* to *r*, inclusive. The last should count the number of non-zero element. This all can be done either with segment tree or sqrt-decomposition.