codeforces-scrape

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

461.md (8317B)


      1 Source: https://codeforces.com/blog/entry/13568
      2 
      3 [Div2 A Appleman and Easy Task](//codeforces.com/contest/462/problem/A) (Author: [EnumerativeCombinatorics](/profile/EnumerativeCombinatorics "Master EnumerativeCombinatorics"))
      4 
      5 This is a simple implementation problem. You can solve by searching adjacent cells of every cell.
      6 
      7 [Div2 B Appleman and Card Game](//codeforces.com/contest/462/problem/B) (Author: [EnumerativeCombinatorics](/profile/EnumerativeCombinatorics "Master EnumerativeCombinatorics"))
      8 
      9 This is simple greedy problem, but it seemed to be reading-hard. The statement says, "Choose K cards from N cards, the score of each card is (the number of cards which has the same character in **K** cards. (not in N cards)"
     10 
     11 It is clear that this total score is (the number of 'A' in K cards)^2 + (the number of 'B' in K cards)^2 + ... + (the number of 'Z' in K cards)^2 This value will be maximized by the simple greedy algorithm, take K cards from most appearred character in N cards, the second most appearred character in N cards, and so on.
     12 
     13 [Div1 A / Div2 C Appleman and Toastman](//codeforces.com/contest/461/problem/A) (Author: [hogloid](/profile/hogloid "International Master hogloid"))
     14 
     15 First I describe the algorithm, and explain why it works.
     16 
     17 * Sort {*a**i*} in non-decreasing order.
     18 * Then, for *i*-th number, add (*i* + 1) * *a**i* to the result.(i=1...n-1)
     19 * For *n*-th number, add *n* * *a**n* to the result.
     20 
     21 Actually, when you multiply all numbers by -1,the answer will be the minimal possible value, multiplied by -1.
     22 
     23 It's Huffman coding problem to find minimal possible value. Solving Huffman coding also can be solved in O(*nlogn*)
     24 
     25 In Huffman coding, push all the numbers to a priority queue. While the size of the queue is larger than 2, delete the minimal and second-minimal element, add the sum of these two to the cost, and push the sum to the queue. Here, since all the numbers are negative, the pushed sum will be remain in the first in the queue. Analyzing this movement will lead to the first algorithm.
     26 
     27 [Div1 B / Div2 D Appleman and Tree](//codeforces.com/contest/461/problem/B) (Author: [hogloid](/profile/hogloid "International Master hogloid"))
     28 
     29 Fill a DP table such as the following bottom-up:
     30 
     31 * DP[v][0] = the number of ways that the subtree rooted at vertex v has no black vertex.
     32 * DP[v][1] = the number of ways that the subtree rooted at vertex v has one black vertex.
     33 
     34 The recursion pseudo code is folloing:
     35 
     36 ```
     37 DFS(v):
     38  DP[v][0] = 1
     39  DP[v][1] = 0
     40  foreach u : the children of vertex v
     41   DFS(u)
     42   DP[v][1] *= DP[u][0]
     43   DP[v][1] += DP[v][0]*DP[u][1]
     44   DP[v][0] *= DP[u][0]
     45  if x[v] == 1:
     46   DP[v][1] = DP[v][0]
     47  else:
     48   DP[v][0] += DP[v][1]
     49 ```
     50 
     51 The answer is DP[root][1].
     52 
     53 UPD:  
     54  The above code calculate the DP table while regarding that the vertex v is white (x[v]==0) in the foreach loop.
     55 
     56 After that the code thinks about the color of vertex v and whether we cut the edge connecting vertex v and its parent or not in "if x[v] == 1: DP[v][1] = DP[v][0] else: DP[v][0] += DP[v][1]".
     57 
     58 [Div1 C / Div2 E Appleman and a Sheet of Paper](//codeforces.com/contest/461/problem/C) (Author: [snuke](/profile/snuke "Grandmaster snuke"))
     59 
     60 For each first type queries that p_i > (the length of the paper) — p_i, you should express the operation in another way: not fold the left side of the paper but fold the right side of the paper. After such query you need to think as the paper is flipped.
     61 
     62 Let's define count[i] as the number of papers piled up at the segment [i,i+1] (absolute position). For each query of first type you can update each changed count[i] naively.
     63 
     64 Use BIT or segment tree for count[i] because you can answer each second type queries in O(log n). The complexity of a first type query is O((the decrement of the length of the paper) log n) so total complexity of a first type query is O(n log n).
     65 
     66 [Div1 D Appleman and Complicated Task](//codeforces.com/contest/461/problem/D) (Author: [EnumerativeCombinatorics](/profile/EnumerativeCombinatorics "Master EnumerativeCombinatorics"),[snuke](/profile/snuke "Grandmaster snuke"))
     67 
     68 First, we ignore the already drawn cell and dependence of cells. If we decide the first row, then the entire board can decided uniquely. We call 'o' is 1, and 'x' is 0. Then,
     69 
     70 a[i][j] = a[i-2][j] xor a[i-1][j-1] xor a[i-1][j+1]
     71 
     72 For example, I'll explain n=5 case. Each column of first row is a, b, c, d, and e. "ac" means a xor c.
     73 
     74 ```
     75 a   b   c   d   e
     76 b   ac  bd  ce  d
     77 c   bd  ace bd  c
     78 d   ce  bd  ac  b
     79 e   d   c   b   a
     80 ```
     81 
     82 Each character affects the following cells (denoted 'o').
     83 
     84 ```
     85 o.... .o... ..o.. ...o. ....o
     86 .o... o.o.. .o.o. ..o.o ...o.
     87 ..o.. .o.o. o.o.o .o.o. ..o..
     88 ...o. ..o.o .o.o. o.o.. .o...
     89 ....o ...o. ..o.. .o... o....
     90 ```
     91 
     92 Generally we can prove the dependence that a[0][k] affects a[i][j] if k<=i+j<=2(n-1)-k and |i-j|<=k and k%2==(i+j)%2. ... (*)
     93 
     94 We can separate the problems by (i+j) is odd or even.
     95 
     96 Each (i,j), we can get the range of k that affects the cell (i,j) by using formula (*). So the essence of this problem is that "There is a sequence with n integers, each of them is 0 or 1. We know some (i,j,k) where a[i]^a[i+1]^...^a[j]=k. How many possible this sequences are there?" We can solve this problem by using union-find. At first, there is n*2 vertices. If k is 1, we'll connect (i*2,(j+1)*2+1) and (i*2+1,(j+1)*2), if k is 0, we'll connect (i*2,(j+1)*2) and (i*2+1,(j+1)*2+1) (note that i<=j). If both i*2 and i*2+1 are in the same set for any i, the answer is 0. Otherwise the answer is 2^((the number of sets-2)/2).
     97 
     98 Also, it is possible to solve odd number version. (How many ways to fill all the empty cells with 'x' or 'o' (each cell must contain only one character in the end) are there, such that for each cell the number of adjacent cells with 'o' will be "odd"? ) I'll hope for your challenge for odd-number version!!
     99 
    100 [Div1 E Appleman and a Game](//codeforces.com/contest/461/problem/E) (Author: [hogloid](/profile/hogloid "International Master hogloid"),[snuke](/profile/snuke "Grandmaster snuke"))
    101 
    102 Let C be the number of characters(here, C=4)
    103 
    104 Given string S, the way to achieve minimum steps is as follows: Append one of the longest substring of T that fits current position of string S. Appending a not-longest substring can be replaced by appending longest substring and shortening the next substring appended.
    105 
    106 Let dp[K][c1][c2] be defined as :
    107 
    108 the minimum length of string that can be obtained by appending a string K times and that starts by character c1 and whose next character is c2. Note that next character is not counted in the length.
    109 
    110 dp[1] can be calculated as follows:
    111 
    112 For every string of length L expressed by C characters, if the string is not included in T, update the dp table as dp[1][the string's first character][its last character]=min(dp[1][its first character][its last character],L-1)
    113 
    114 For any (c1,c2), dp[1][c1][c2] is smaller than or equal to log_C(T+1)+2 (since the kind of strings of length log_C(T+1)+2 that start by c1 and end by c2 is equals to T+1). Therefore for L=1...log(T+1)+2, try all the strings as described above.
    115 
    116 Also we can use trie that contains all substrings of T of length log_C(T+1)+2, and find what can't be described as a substring of T by one step.
    117 
    118 Since dp[k+1][c1][c2]=min(dp[k][c1][c3]+dp[1][c3][c2] | c3=1...C), we can use matrix multiplication to get dp[K].
    119 
    120 For a integer K, if there is (c1,c2) such that dp[K][c1][c2]<|S|, the answer is greater than K. Otherwise,the answer is smaller than or equal to K.
    121 
    122 Since answer is bigger or equal to 1 and smaller or equal to |S|, we can use binary search to find the ansewr.
    123 
    124 O(T*((log T)^2+C^2)+C^3(log |S|)^2)
    125 
    126 BONUS: Is there any algorithm that solves in O(1) or O(C^foo)(that is, not depended on |S|) for each |S| with pre-calc?
    127 
    128 Some hints: Maximal value of dp[1][*][*] — Minimal value of dp[1][*][*] <= 2
    129 
    130 (let's call the maximal value dp[1][i][j]=L. Here, any C^(L-2) strings are contained in T as substring, so for any (c1,c2), dp[1][c1][c2]>=L-2)
    131 
    132 Maximal value of dp[1][k][*] — minimal value of dp[1][k][*] <=1 ( k=1...C)
    133 
    134 Maximal value of dp[1][*][k] — minimal value of dp[1][*][k] <=1 ( k=1...C)
    135 
    136 Even if we use these hints and make C=3, the implementation would be not easy.
    137 
    138 If you come up with smart way, please comment here :)