codeforces-scrape

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

453.md (8696B)


      1 Source: https://codeforces.com/blog/entry/13190
      2 
      3 # Overview
      4 
      5 There are 3 normal tasks accompanied with 2 challenge tasks in div 1 as we usually do. You can check the [Statistics](//codeforces.com/blog/entry/13271) by By [DmitriyH](/profile/DmitriyH "Expert DmitriyH") for detail.
      6 
      7 Problem B, C is by [sevenkplus](/profile/sevenkplus "Grandmaster sevenkplus"), problem D is by [xlk](/profile/xlk "International Master xlk") and problem A, E is by me.
      8 
      9 Problem E is rather complicated then hard, it means if you carefully broke down the problem into smaller ones, it became quite straightforward. During the contest, only [kcm1700](/profile/kcm1700 "Grandmaster kcm1700") managed to solve it successfully.
     10 
     11 Problem D, which decided the round boiled down to the following nice Dynamic Programming subproblem: you are given 220 numbers. For each position i between 0 and 220 - 1, and for each distance *j* between 0 and 20, what is the sum of the numbers with such indexes *k* that *k* and *i* differ in exactly *j* bits? The fun part is not how to do it *T* times, it is how to do it even once on 106 numbers.
     12 
     13 [Petr](/profile/Petr "International Grandmaster Petr") solve A, B, C, D steadily and fast who indisputably, is the winner of the round. The second place came to [msg555](/profile/msg555 "Grandmaster msg555"), closely followed by [cgy4ever](/profile/cgy4ever "Grandmaster cgy4ever"). It is worth mentioning that, [cgy4ever](/profile/cgy4ever "Grandmaster cgy4ever") solved Problem D in the last few seconds which is quite impressive.
     14 
     15 # Editorial
     16 
     17 ### [Problem 2A. Little Pony and Crystal Mine](//codeforces.com/problemset/problem/454/A)
     18 
     19 #### Brief description:
     20 
     21 Draw the grid graph as the problem said.
     22 
     23 #### Analysis:
     24 
     25 Just a few basics of your programming language. It's easy.
     26 
     27 ### [Problem 2B. Little Pony and Sort by Shift](//codeforces.com/problemset/problem/454/B)
     28 
     29 #### Brief description:
     30 
     31 Ask the minimum unit shift you need to sort a array.
     32 
     33 #### Analysis:
     34 
     35 Just a few basics of your programming language. It's not hard.
     36 
     37 ### [Problem A. Little Pony and Expected Maximum](//codeforces.com/problemset/problem/453/A)
     38 
     39 #### Brief description:
     40 
     41 Calculate the expected maximum number after tossing a *m* faces dice *n* times.
     42 
     43 #### Analysis:
     44 
     45 Take *m* = 6, *n* = 2 as a instance.
     46 
     47 ```
     48 6 6 6 6 6 6
     49 5 5 5 5 5 6
     50 4 4 4 4 5 6
     51 3 3 3 4 5 6
     52 2 2 3 4 5 6
     53 1 2 3 4 5 6
     54 ```
     55 
     56 Enumerate the maximum number, the distribution will be a *n*-dimensional super-cube with *m*-length-side. Each layer will be a large cube minus a smaller cube. So we have:
     57 
     58 ![](https://espresso.codeforces.com/72c2f17ff97963ac2e45bfe1b09ea6d75aacbed1.png)
     59 
     60 Calculate *i**n* may cause overflow, we could move the divisor into the sum and calculate (*i* / *m*)*n* instead.
     61 
     62 ### [Problem B. Little Pony and Harmony Chest](//codeforces.com/problemset/problem/453/B)
     63 
     64 #### Brief description:
     65 
     66 You are given sequence *a**i*, find a pairwise coprime sequence *b**i* which minimizes ![](https://espresso.codeforces.com/5331e97de229b75f7e048dc3743c158557e6dbcc.png)
     67 
     68 #### Analysis:
     69 
     70 Since {1, 1 ..., 1} is a pairwise coprime sequence, the maximum element of *b**i* can never greater then 2*mx* - 1. Here *mx* is the maximum elements in *a**i*. So what we need consider is the first a few prime factors. It is not hard to use bitmask-dp to solve this:
     71 
     72 ```
     73     for (int i = 1 ; i <= n ; i ++) {
     74     	for (int k = 1 ; k < 60 ; k ++) {
     75     		int x = (~fact[k]) & ((1 << 17) - 1);
     76     		for (int s = x ; ; s = (s - 1) & x) {
     77                 if (dp[i - 1][s] + abs(a[i] - k) < dp[i][s | fact[k]]){
     78                     dp[i][s | fact[k]] = dp[i-1][s] + abs(a[i]-k);
     79                 }
     80     		if (s == 0) break;
     81             }
     82     	}
     83     }
     84 ```
     85 
     86 Here `dp[i][s]`: means the first *i* items of the sequence, and the prime factor have already existed. And `fact[k]`: means the prime factor set of number *k*.
     87 
     88 ### [Problem C. Little Pony and Summer Sun Celebration](//codeforces.com/problemset/problem/453/C)
     89 
     90 #### Brief description:
     91 
     92 Given a undirected graph with *n* nodes and the parity of the number of times that each place is visited. Construct a consistent path.
     93 
     94 #### Analysis:
     95 
     96 There is no solution if there is more than 1 connected component which have odd node (because we can't move between two component), otherwise it is always solvable.
     97 
     98 This fact is not obvious, let's focus on one component. You can select any node to start, denoted it as *r* (root). Start from *r*, you can go to any other odd node then back. Each time you can eliminate one odd node. After that, if *r* itself is odd, you can simply delete the first or last element in your path (it must be *r*).
     99 
    100 The only spot of the above method is the size of the path can been large as *O*(*n*2). We need a more local observation. Let's check the following dfs() function:
    101 
    102 ```
    103 void dfs(int u = r, int p = -1){
    104     
    105     vis[u] = true;
    106     add_to_path(u);
    107 
    108     for_each(v in adj[u]) if (!vis[v]){
    109         dfs(v, u);
    110         add_to_path(u);
    111     }
    112 
    113     if (odd[u] && p != -1){
    114         add_to_path(p);
    115         add_to_path(u);
    116     }
    117 }
    118 ```
    119 
    120 This `dfs()` maintain the following loop invariant: before we leave a node *u*, we clear all odd node in the sub-tree rooted at *u* as well as *u* itself.
    121 
    122 The only *u* can break the invariant is the root itself. So after dfs(), we use O(1) time to check weather root is still a odd node, if yes, delete the first or last element of the path (it must be *r*).
    123 
    124 After that, all the node will been clear, each node can involve at most 4 items in the path. So the size of the path will less than or equal to 4*n*. Thus the overall complexity is *O*(*n* + *m*).
    125 
    126 ### [Problem D. Little Pony and Elements of Harmony](//codeforces.com/problemset/problem/453/D)
    127 
    128 #### Brief description:
    129 
    130 Given you a vector *e* and a transformation matrix *A*. Caculate *eA**t* under modulo *p*.
    131 
    132 #### Analysis:
    133 
    134 Let's consider the *e* = [1 1 ... 1]. After a period, it will be *ke* where *k* is a const. So we know that [1 1, ..., 1] is an eigenvector and *k* is the corresponding an eigenvalue.
    135 
    136 The linear transformation has 2*m* eigenvectors.
    137 
    138 The *i*(0 ≤ *i* < 2*m*)-th
    139 
    140 eigenvector is [(-1)^f(0, i) (-1)^f(1, i) ... (-1)^f(2^m-1, i)], where *f*(*x*, *y*) means that the number of ones in the binary notation of *x* and *y*.
    141 
    142 We notice that the eigenvalue is only related to the number of ones in *i*, and it is not hard to calc one eigenvalue in *O*(*m*) time. To decompose the initial vector to the eigenvectors, we need [Fast Walsh–Hadamard transform](https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform).
    143 
    144 Also check SRM 518 1000 for how to use FWT. <http://apps.topcoder.com/wiki/display/tc/SRM+518>
    145 
    146 In the last step, we need divide n. We can mod (p * n) in the precedure and divide n directly.
    147 
    148 ### [Problem E. Little Pony and Lord Tirek](//codeforces.com/problemset/problem/453/E)
    149 
    150 #### Brief description:
    151 
    152 *n* ponies (from 1 to *n*) in a line, each pony has:
    153 
    154 * *s**i*: the start mana.
    155 * *m**i*: the maximum mana.
    156 * *r**i*: mana regeneration per unit time.
    157 
    158 Also, you have *m* operations called Absorb Mana *t* *l* *r*. For each operations, at time *t*, count how many mana from *l* to *r*. After that, reset each pony's mana to 0.
    159 
    160 #### Analysis:
    161 
    162 ##### Key Observation
    163 
    164 The income of a operation, is only relevant with the previous operation. In other words, what we focus on is the difference time between adjacent operations.
    165 
    166 ##### Weaken the problem
    167 
    168 Let us assume *s**i* = 0 and *r**i* = 1 at the beginning to avoid disrupting when we try to find the main direction of the algorithm. Also it will be much easier if the problem only ask the sum of all query. One of the accepted method is following:
    169 
    170 Firstly, for each operation (*t*, *l*, *r*), we split it into a insert event on *l*, and a delete event *r* + 1. Secondly, we use scanning from left to right to accumulate the contributions of each pony.
    171 
    172 In order to do that, you need a balanced tree to maintenance the difference time between adjacent operations, and a second balanced tree to maintenance some kind of prefixes sum according to those "difference".
    173 
    174 The first balanced tree could been implemented by STL::SET. For each operation, you need only constant insert and delete operations on those balanced tree, thus the overall complexity is *O*(*nlogn*).
    175 
    176 ##### General solution
    177 
    178 Instead of scanning, now we use a balanced tree to maintenance the intervals which have same previous operation time and use a functional interval tree to maintenance those ponies. For each operation, we use binary search on the first balanced tree, and query on the second balanced tree. Thus the overall complexity is *O*(*nlog*2*n*).