codeforces-scrape

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

554.md (10909B)


      1 Source: https://codeforces.com/blog/entry/18842
      2 
      3 ## [Div2A: Kyoya and Photobooks](//codeforces.com/contest/554/problem/A)
      4 
      5 Solving this problem just requires us to simulate adding every character at every position at the string, and removing any duplicates. For instance, we can use a HashSet of Strings in Java to do this (a set in C++ or Python works as well).
      6 
      7 Bonus: Prove that the number of ways is always (length of string + 1) * 25 + 1.
      8 
      9 Example code: [http://codeforces.com/contest/554/submission/11767578](//codeforces.com/contest/554/submission/11767578)
     10 
     11 ## [Div2B: Ohana Cleans Up](//codeforces.com/contest/554/problem/B)
     12 
     13 For each row, there is only one set of columns we can sweep so it becomes completely clean. So, there are only *n* configurations of sweeping columns to look at. Checking a configuration takes *O*(*n*2) time to count the number of rows that are completely clean. There are *n* configurations in all, so this takes *O*(*n*3) time total.
     14 
     15 Alternatively, another way of solving this problem is finding the maximum number of rows that are all the same.
     16 
     17 Example code: [http://codeforces.com/contest/554/submission/11767576](//codeforces.com/contest/554/submission/11767576)
     18 
     19 ## [Div2C/Div1A: Kyoya and Colored Balls](//codeforces.com/contest/553/problem/A)
     20 
     21 Let *f**i* be the number of ways to solve the problem using only the first *i* colors. We want to compute *f**n*.
     22 
     23 Initially, we have *f*1  =  1, since we only have a single color, and balls of the same color are indistinguishable. Now, to go from *f**i* to *f**i* + 1, we note that we need to put at a ball of color *i* + 1 at the very end, but the other balls of color *i* + 1 can go anywhere in the sequence. The number of ways to arrange the balls of color *i* + 1 is ![](https://espresso.codeforces.com/b972e15852772c0716522b108c60f7a1cc43554b.png) (minus one because we need to put one ball at the very end). Using this recurrence, we can solve for *f**n*.
     24 
     25 Thus, we need to precompute binomial coefficients then evaluate the product.
     26 
     27 Example code: [http://codeforces.com/contest/553/submission/11767584](//codeforces.com/contest/553/submission/11767584)
     28 
     29 ## [Div2D/Div1B: Kyoya and Permutation](//codeforces.com/contest/553/problem/B)
     30 
     31 Solving this requires making the observation that only swaps between adjacent elements are allowed, and all of these swaps must be disjoint. This can be discovered by writing a brute force program, or just noticing the pattern for small *n*.
     32 
     33 Here's a proof for why this is. Consider the cycle that contains *n*. Since *n* is the largest number, it must be the last cycle in the sequence, and it's the first element of the sequence. If this cycle is length 1, then we're obviously ok (we can always append (*n*) to the end). If the cycle is of length 2, we need *n* to be involved in a cycle with *n* - 1. Lastly, if the cycle is of length 3 or more, we will see we run into a problem. We'll only show this for a cycle of length 3 (though this argument does generalize to cycles of larger length). Let (*nxy*) be the cycle. So that means, *n* is replaced by *x*, *x* is replaced by *y* and *y* is replaced by *n*. So, in other words, the original permutation involving this cycle must look like
     34 
     35 ```
     36 position:   ... y x n
     37 number  :   ... n y x
     38 ```
     39 
     40 However, we need it to look like (*nxy*) so this case is impossible.
     41 
     42 So, once we know that *n* is a in a cycle of length 1 or 2, we can ignore the last 1 or 2 elements of the permutation and repeat our reasoning. Thus, the only valid cases are when we swap adjacent elements, and all swaps are disjoint. After making this observation, we can see the number of valid permutations of length n is fib(n+1). (to see this, write try writing a recurrence).
     43 
     44 To reconstruct the kth permutation in the list, we can do this recursively as follows: If k is less than fib(n), then 1 must be the very first element, and append the *k*th permutation on {1,...,n-1} with 1 added everywhere. Otherwise, add 2, 1 to the very front and append the k-fib(n)th permutation on {1,...,n-2} with 2 added everywhere.
     45 
     46 Example code: [http://codeforces.com/contest/553/submission/11767583](//codeforces.com/contest/553/submission/11767583)
     47 
     48 ## [Div2E/Div1C: Love Triangles](//codeforces.com/contest/553/problem/C)
     49 
     50 Let's look at the graph of characters who love each other. Each love-connected component can be collapsed into a single node, since we know that all characters in the same connected component must love each other.
     51 
     52 Now, we claim that the resulting collapsed graph with the hate edges has a solution if and only if the resulting graph is bipartite.
     53 
     54 To show this, suppose the graph is not bipartite. Then, there is an odd cycle. If the cycle is of length 1, it is a self edge, which clearly isn't allowed (since a node must love itself). For any odd cycle of length more than 1, let's label the nodes in the cycle *a*1, *a*2, *a*3, ..., *a**k*. Then, in general, we must have *a**i* loves *a*(*i* + 2), since *a**i*, *a*(*i* + 1) hate each other and *a*(*i* + 1), *a*(*i* + 2) hate each other (all indicies taken mod *k*). However, we can use the fact that the cycle is odd and eventually get that *a**i* and *a**i* + 1 love each other. However, this is a contradiction, since we said they must originally hate each other.
     55 
     56 For the other direction, suppose the graph is bipartite. Let *X*, *Y* be an arbitrary bipartition of the graph. If we let all nodes in *X* love each other and all nodes in *Y* love each other, and every edge between *X* and *Y* hate each other, then we get a solution. (details are omitted, though I can elaborate if needed).
     57 
     58 Thus, we can see that we have a solution if and only if the graph is bipartite. So, if the graph is not bipartite, the answer is zero. Otherwise, the second part of the proof gives us a way to count. We just need to count the number of different bipartitions of the graph. It's not too hard to see that this is just simply 2^(number of connected components — 1) (once you fix a node, you fix every node connected to it).
     59 
     60 This entire algorithm takes *O*(*N* + *M*) time.
     61 
     62 Example code: [http://codeforces.com/contest/553/submission/11767582](//codeforces.com/contest/553/submission/11767582)
     63 
     64 ## [Div1D: Nudist Beach](//codeforces.com/contest/553/problem/D)
     65 
     66 The algorithm idea works as follows:
     67 
     68 Start with all allowed nodes. Remove the node with the smallest ratio. Repeat. Take the best ratio over all iterations. It's only necessary to consider these subsets. Proof for why.
     69 
     70 We say this process finds a ratio of at least p if and only if there exists a subset with ratio at least p.
     71 
     72 Exists a subset with ratio at least p => algorithm will find answer of at least p. First, observe that the ratio of any particular node only decreases throughout the algorithm. Thus, all nodes in this subset initally have ratio at least p. Then, the very first node that gets removed from this subset must not have ratio smaller than p, thus the above algorithm will record an answer of at least p.
     73 
     74 Exists no subset with ratio at least p => algorithm finds answer at most p. No subset with ratio at least p implies every subset has ratio at most p. Thus, at every iteration of our algorithm, we'll get an answer of at most p, so we're done.
     75 
     76 Thus, we can see these are necessary and sufficient conditions, so we're done.
     77 
     78 Now for efficient implementation, we can use a variant of Dijkstra's. Recording the best subset must be done a bit more carefully as well.
     79 
     80 Example code: [http://codeforces.com/contest/553/submission/11767581](//codeforces.com/contest/553/submission/11767581)
     81 
     82 ## [Div1E: Kyoya and Train](//codeforces.com/contest/553/problem/E)
     83 
     84 The Naive solution is *O*(*MT*2). Let *W**j*(*t*) be the optimal expected time given we are at node *j*, with *t* time units left. Also, let *W**e*(*t*) be the optimal expected time given we use edge *e* at time *t*.
     85 
     86 Now, we have
     87 
     88 ![](https://espresso.codeforces.com/f91fbf28db99bb56f162fa45328fe240044fedf0.png)
     89 
     90 And, if e = (u->v), we have ![](https://espresso.codeforces.com/7258c04856a469a1916ca4c7f7062d61823ea815.png)
     91 
     92 Doing all this naively takes *O*(*MT*2).
     93 
     94 Now, we'll speed this up using FFT. We'll focus on only a single edge for now. The problem here, however, is that not all *W**v* values are given in advance. Namely, the *W**v* values require us to compute the *W**e* values for all edges at a particular time, and vice versa. So we need some sort of fast "online" version of FFT.
     95 
     96 We do this as follows. Let's abstract away the original problem, and let's say we're given two arrays a,b, where a is only revealed one at a time to us, and b is given up front, and we need to compute c, their convolution (in the original problem b is *P**e*, and a is *W**v*, and c is *W**e*). Now, when we get the ith value of a, we need to return the ith value of the convolution of c. We can only get the ith value of a when we compute the i-1th values of c for all c.
     97 
     98 Split up b into a block of size 1, a block of size 1, then a block of size 2, then a block of size 4, then 8, and so on.
     99 
    100 Now, we get *a*0, which will allow us to compute *c*1, which lets us get *a*1, which allows us to compute *c*2, and so on.
    101 
    102 So, now we have the following:
    103 
    104 ```
    105 b_1 | b_2 | b_3 b_4 | b_5 b_6 b_7 b_8 | ...
    106 ```
    107 
    108 We'll describe the processing of a single *a**i*
    109 
    110 When we get *a**i*, we will first convolve it with the first two blocks, and add those to the appropriate entry. Now, suppose *a**i* is multiple of a 2*k* for some k. Then, we will convolve *a**i* - 2*k* .. *a**i* - 1 with the block in b with the same size.
    111 
    112 As an example.
    113 
    114 ```
    115       b_1 | b_2 | b_3 b_4 | b_5 b_6 b_7 b_8 | ...
    116 a_0   a0b1  
    117             a0b2
    118 ```
    119 
    120 This gives us *c*0, which then allows us to get *a*1
    121 
    122 ```
    123       b_1 | b_2 | b_3 b_4 | b_5 b_6 b_7 b_8 | ...
    124 a_0   a0b1  a1b1
    125 a_1         a0b2 a1b2
    126 ```
    127 
    128 This gives us *c*1, which then allows us to get *a*2
    129 
    130 *a*2 is now a power of 2, so this step will also additionally convolve *a*0, *a*1 with *b*3, *b*4
    131 
    132 ```
    133       b_1 | b_2 | b_3      b_4    | b_5 b_6 b_7 b_8 | ...
    134 a_0   a0b1  a1b1  a2b1
    135 a_1         a0b2  a1b2    a2b2
    136 a_2               a0b3 (a1b3+a0b4)  a1b4
    137 ```
    138 
    139 So, we can see this gives us *c*2, which then allowus to get *a*3, and so on and so forth.
    140 
    141 Thus, this process of breaking into blocks works. As for runtime, we run FFT on a block size of B T/B times, so this term contributes (T/B) * B log B = T log B
    142 
    143 So, we sum T log 2 + T log 4 + ... + T log 2\^(log T) <= T log\^2 T
    144 
    145 Thus, the overall time per edge is ![](https://espresso.codeforces.com/e5db2ef4fc30929fb3572c94a575a8dff9061401.png), which gives us a total runtime of ![](https://espresso.codeforces.com/49c7800ef04ffd7c6c67c2e7aea8fcb40547ea9c.png).
    146 
    147 Example code: [http://codeforces.com/contest/553/submission/11767579](//codeforces.com/contest/553/submission/11767579)