codeforces-scrape

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

506.md (29680B)


      1 Source: https://codeforces.com/blog/entry/15889
      2 
      3 **Edit (Jan 22, 2:45 AM UTC):** Added Div1E and the editorial is now complete. I am sorry for the delay.
      4 
      5 **Edit (Jan 21, 9:45 AM UTC):** Added the explanation for Div1C/2E, and the problem setters' codes. Div1E will need several more hours. Thank you again for your patience.
      6 
      7 First, here are some statistics on this round:
      8 
      9 |  |  |  |  |  |  |  |  |
     10 | --- | --- | --- | --- | --- | --- | --- | --- |
     11 | Division | Registrants | Participants | A Accepted | B Accepted | C Accepted | D Accepted | E Accepted |
     12 | 1 | 1364 | 572 (*) | 294 | 199 | 8 | 113 | 1 |
     13 | (Estimated number of AC by me) | | | 800 (wrong) | 500 (wrong) | 70 (FAIL) | 90 (ok) | 5 (wrong) |
     14 | 2 | 4016 | 2028 | 1355 | 945 | 41 | 5 | 0 |
     15 
     16 (*) Where did the remaining 792 people go? :)   
     17    
     18  We are sorry for terribly underestimating the difficulty of the problems (except Div1D), especially Div1A/2C and Div1C/2E.   
     19    
     20    
     21 
     22 ### Div.2 A: [505A - Mr. Kitayuta's Gift](/contest/505/problem/A "Codeforces Round 286 (Div. 2)")
     23 
     24 [Problem] Given a string, turn it into a palindrome by inserting one letter or state that it is impossible.
     25 
     26 (Problem by [evima](/profile/evima "Master evima"))
     27 
     28 Since the string is short (at most 10 characters), you can simply try every possible way of inserting a letter ("where" and "what" to insert), and check if the resulting string is a palindrome.
     29 
     30 The writer's code (C++): [9501249](/contest/505/submission/9501249 "Submission 9501249 by evima")  
     31 ~~Note: For some strange reason, we (contest managers) cannot submit solutions so that everyone can see them.~~ [PraveenDhinwa](/profile/PraveenDhinwa "Candidate Master PraveenDhinwa") told us how to do so. Thank you!
     32 
     33 ### Div.2 B: [505B - Mr. Kitayuta's Colorful Graph](/contest/505/problem/B "Codeforces Round 286 (Div. 2)")
     34 
     35 [Problem] Given an undirected graph whose edges are painted in colors, process the queries of the following form:
     36 
     37 * Given two vertices *u**i* and *v**i*, find the number of the colors that satisfies the following condition: the edges of that color connect *u**i* and *v**i* (possibly indirectly).
     38 
     39 (Problem by [hogloid](/profile/hogloid "Grandmaster hogloid"))
     40 
     41 Since neither the graph nor the number of queries is too large, for each query you can simply count the number of the "good" colors (the colors that satisfies the condition) by checking if each color is "good". To do that, you can perform Depth First Search (or Breadth First Search) and verify whether you can reach *v**i* from *u**i* traversing only the edges of that color. If you prefer using Union-Find, it will also do the job.
     42 
     43 [The writer's code (DFS, C++)](http://ideone.com/tZU3kZ)  
     44 [The writer's code (Union-Find, C++)](http://ideone.com/NyCK8v)
     45 
     46 ### Div.2 C / Div.1 A: [505C - Mr. Kitayuta, the Treasure Hunter](/contest/505/problem/C "Codeforces Round 286 (Div. 2)")
     47 
     48 [Problem] Since it is hard to summarize this problem, please refer to the official statement.
     49 
     50 (Problem by [yosupo](/profile/yosupo "Master yosupo"))
     51 
     52 Below is the explanation from [yosupo](/profile/yosupo "Master yosupo"), translated by me.
     53 
     54 [From here]
     55 
     56 Let *m* be the number of the islands (that is, 30001). First, let us describe a solution with time and memory complexity of *O*(*m*2).
     57 
     58 We will apply Dynamic Programming. let *dp*[*i*][*j*] be the number of the gems that Mr. Kitayuta can collect after he jumps to island *i*, when the length of his previous jump is *j* (let us assume that he have not collect the gems on island *i*). Then, you can calculate the values of the table *dp* by the following:
     59 
     60 * *dp*[*i*][*j*] = 0, if *i* ≥ *m*  
     61   (actually these islands do not exist, but we can suppose that they exist and when Mr. Kitayuta jumps to these islands, he stops jumping)
     62 * *dp*[*i*][*j*] =  (the number of the gems on island *i*)  + *max*(*dp*[*i* + *j*][*j*], *dp*[*i* + *j* + 1][*j* + 1]), if *i* < *m*, *j* = 1  
     63   (he cannot perform a jump of length 0)
     64 * *dp*[*i*][*j*] =  (the number of the gems on island *i*)  + *max*(*dp*[*i* + *j* - 1][*j* - 1], *dp*[*i* + *j*][*j*], *dp*[*i* + *j* + 1][*j* + 1]), if *i* < *m*, *j* ≥ 2
     65 
     66 This solution is unfeasible in terms of both time and memory. However, the following observation makes it an Accepted solution: there are only 491 values of *j* that we have to consider, which are *d* - 245, *d* - 244, *d* - 243, ..., *d* + 244 and *d* + 245.
     67 
     68 Why? First, let us find the upper bound of *j*. Suppose Mr. Kitayuta always performs the "*l* + 1" jump (*l*: the length of the previous jump). Then, he will reach the end of the islands before he performs a jump of length *d* + 246, because  
     69 *d* + (*d* + 1) + (*d* + 2) + ... + (*d* + 245) ≥ 1 + 2 + ... + 245 = 245·(245 + 1) / 2 = 30135 > 30000. Thus, he will never be able to perform a jump of length *d* + 246 or longer.
     70 
     71 Next, let us consider the lower bound of *j* in a similar way. If *d* ≤ 246, then obviously he will not be able to perform a jump of length *d* - 246 or shorter, because the length of a jump must be positive. Suppose Mr. Kitayuta always performs the "*l* - 1" jump, where *d* ≥ 247. Then, again he will reach the end of the islands before he performs a jump of length *d* - 246, because  
     72 *d* + (*d* - 1) + (*d* - 2) + ... + (*d* - 245) ≥ 245 + 244 + ... + 1 = 245·(245 + 1) / 2 = 30135 > 30000. Thus, he will never be able to perform a jump of length *d* - 246 or shorter.
     73 
     74 Therefore, we have obtained a working solution: similar to the *O*(*m*2) one, but we will only consider the value of *j* between *d* - 245 and *d* + 245. The time and memory complexity of this solution will be *O*(*m*1.5), since the value "245" is slightly larger than ![](https://espresso.codeforces.com/c226e9a3b079284d829070957e74c22fc7f4d852.png).
     75 
     76 This solution can be implemented by, for example, using a "normal" two dimensional array with a offset like this: `dp[i][j - offset]`. The time limit is set tight in order to fail most of naive solutions with search using std::map or something, so using hash maps (unordered_map) will be risky although the complexity will be the same as the described solution.
     77 
     78 [End]
     79 
     80 [The writer's code (memoized recursion, C++)](https://ideone.com/GLXkVj)
     81 
     82 ### Div.2 D / Div.1 B: [505D - Mr. Kitayuta's Technology](/contest/505/problem/D "Codeforces Round 286 (Div. 2)")
     83 
     84 [Problem] Given an integer *n* and *m* pairs of integers (*a**i*, *b**i*) (1 ≤ *a**i*, *b**i* ≤ *n*), find the minimum number of edges in a directed graph that satisfies the following condition:
     85 
     86 * For each *i*, there exists a path from vertex *a**i* to vertex *b**i*.
     87 
     88 (Problem from [evima](/profile/evima "Master evima"))
     89 
     90 Let *G*1 be the directed graph built from the input, and *G*2 be a directed graph that satisfies the given conditions. What we seek is the minimum number of edges in *G*2. Also, we say that two vertices *u* and *v* in a directed graph are "weakly connected" if we can reach *v* from *u* by traversing edges, not considering their directions.
     91 
     92 If a pair (*u*, *v*) is present in the input, then vertices *u* and *v* must be weakly connected in *G*2. Therefore, for each weakly connected component (abbreviated to wcc) in *G*1, the vertices in that component must also be in the same wcc in *G*2. We can "merge" multiple wccs in *G*1 and create a larger wcc in *G*2, but for now, let us find the minimum number of edges required in *G*2 for each wcc in *G*1 when we do not "merge" them. There are two cases to consider:
     93 
     94 1. If a wcc in *G*1 does not have cycles, then we can perform topological sort on that wcc, and we can make a "chain" (see the image below) using the topological order to satisfy the conditions. We need (the number of the vertices in the wcc)  - 1 edges, which is the minimum required number since any connected graph with *V* vertices has at least *V* - 1 edges. ![ ](/predownloaded/d1/3a/d13a1e2a1a994ff456366be43e362c065c931e6a.png)
     95 2. If a wcc in *G*1 has cycles, then topological sort cannot be applied. We need at least (the number of the vertices in the wcc) edges this time, since any connected graph with *V* vertices and *V* - 1 edges is a tree, which does not contain cycles. Actually, this number (the number of the vertices in the wcc) is always achievable by connecting the vertices into a "ring" (see the image below), thus it is the minimum required number that we seek. ![ ](/predownloaded/04/bb/04bb15a7098daa90f029e322bb49b45a85356a66.png)
     96 
     97 We have found the minimum required number of edges for each wcc in *G*1 when we do not "merge" them. Let us show that "merging" wccs in *G*1 do not reduce the number of required edges. Suppose we combine *k*( > 1) wccs *C*1, *C*2, ..., *C**k* in *G*1 into one wcc *C* in *G*2. Again, there are two cases to consider:
     98 
     99 1. If none of *C*1, *C*2, ..., *C**k* contains cycles, then *C* will need |*C*1| + |*C*2| + ... + |*C**k*| - 1 edges. However, if we do not combine them, we will only need (|*C*1| - 1) + (|*C*2| - 1) + ... + (|*C**k*| - 1) edges in total, which is fewer.
    100 2. If some of *C*1, *C*2, ..., *C**k* contain cycles, then *C* will need |*C*1| + |*C*2| + ... + |*C**k*| edges. However, if we do not combine them, we will need  
    101    (|*C*1| - *noCycles*(*C*1)) + (|*C*2| - *noCycles*(*C*2)) + ... + (|*C**k*| - *noCycles*(*C**k*)  ≤ |*C*1| + |*C*2| + ... + |*C**k*| edges  
    102    (here, *noCycles*(*C**i*) is 1 if *C**i* do not contain cycles, otherwise 0), thus combining them does not reduce the number of required edges.
    103 
    104 Thus, we do not need to combine multiple wccs into one wcc in *G*2 in order to obtain the optimal solution. That is, the final answer to the problem is the sum of the minimum required number of edges for each wcc in *G*1, when they are considered separately.
    105 
    106 As for the implementation, detecting cycles in a directed graph with 105 vertices and edges might be a problem if this is your first encounter with it. One possible way is to paste a code that decomposes a graph into strongly connected components. If the size of a strongly connected component is more than one, then that means the component contains cycles.
    107 
    108 The writer's code (strongly connected component decomposition, C++): [9501202](/contest/506/submission/9501202 "Submission 9501202 by evima")
    109 
    110 ### Div.2 E / Div.1 C: [505E - Mr. Kitayuta vs. Bamboos](/contest/505/problem/E "Codeforces Round 286 (Div. 2)")
    111 
    112 [Problem] Since it is hard to summarize this problem, please refer to the official statement.
    113 
    114 (Problem from [yosupo](/profile/yosupo "Master yosupo"))
    115 
    116 Below is the explanation from [yosupo](/profile/yosupo "Master yosupo"), translated by me.
    117 
    118 [From here]
    119 
    120 Let us begin by applying Binary Search. The problem becomes: "is it possible that all the bamboos are at most *X* meters after *m* days?" It is complicated by the fact that the height does not become negative; the excessive decrease will be wasted. We have found two approaches to this problem.
    121 
    122 * Solution 1
    123 
    124 Mr. Kitayuta must beat the *i*-th bamboo at least *max*(0, ⌈(*h**i* + *m*·*a**i* - *X*) / *P*⌉) times (let this number *t**i*). Actually, it is not necessary for him to beat it more than this number of times. Thus, let us assume that he beat the *i*-th bamboo exactly *t**i* times. Also, for each *j* (1 ≤ *j* ≤ *t**i*), find the day *d**i*, *j* such that, if the *j*-th beat on the *i*-th bamboo is performed before day *d**i*, it will be no longer possible to keep the *i*-th bamboo's height after *m* days at most *X* (it can be found by doing simple math). If Mr. Kitayuta can beat the bamboos under this constraint, all the bamboos' heights will become *X* meters or less after *m* days. Otherwise, some bamboos' heights will exceed *X* meters.
    125 
    126 The time complexity of this solution will be ![](https://espresso.codeforces.com/a8d87458958e2b4284a03279f35698be7a6eb0f8.png), if we first calculate only *t**i*, then if the sum of *t**i* exceeds *km*, we skip finding *d**i*, *j* (the answer is "NO").
    127 
    128 * Solution 2
    129 
    130 This problem becomes simpler if we simulate Mr. Kitayuta's fight backwards, that is, from day *m* to day 1. It looks like this:
    131 
    132 [Problem'] There are *n* bamboos. At the moment, the height of the *i*-th bamboo is *X* meters, and it *shrinks* *a**i* meters at the *beginning* of each day. Mr. Kitayuta will play a game. He can use Magic Hammer at most *k* times per day to *increase* the height of a bamboo by *p* meters. If some bamboo's height becomes negative at any moment, he will lose the game immediately. Also, in order for him to win the game, the *i*-th bamboo's height must be *at least* *h**i* meters after *m* days. Is victory possible?
    133 
    134 Below is an illustration of this "reverse simulation":
    135 
    136 ![ ](/predownloaded/cd/69/cd69947d5aa851d6dbc167eef817e7741834ebc8.png)
    137 
    138 This version is simpler because he is increasing the heights instead of decreasing, thus we do not need to take into account the "excessive decrease beyond 0 meters" which will be wasted. Let us consider an optimal strategy. If there exist bamboos whose heights would become negative after day *m*, he should beat the one that is the earliest to make him lose. Otherwise, he can choose any bamboo whose height would be less than *h**i* meters after day *m*. Repeat beating the bamboos following this strategy, and see if he can actually claim victory.
    139 
    140 The writer's implementation of this solution uses a priority queue, and its time complexity is ![](https://espresso.codeforces.com/f41158cd7133a06f39ddfa2aa5839a417edea2b0.png).
    141 
    142 [End]
    143 
    144 The tester's code (Solution 1, C++): [9501229](/contest/506/submission/9501229 "Submission 9501229 by evima")  
    145 [The writer's code (Solution 2, C++)](https://ideone.com/AGflsb)
    146 
    147 ### Div.1 D: [506D - Mr. Kitayuta's Colorful Graph](/contest/506/problem/D "Codeforces Round 286 (Div. 1)")
    148 
    149 [Problem] Given an undirected graph whose edges are painted in colors, process the queries of the following form:
    150 
    151 * Given two vertices *u**i* and *v**i*, find the number of the colors that satisfies the following condition: the edges of that color connect *u**i* and *v**i* (possibly indirectly).
    152 
    153 Note: this is the exact same problem as Div.2 B except the constraints, which are 105 instead of 100.
    154 
    155 (Problem from [hogloid](/profile/hogloid "Grandmaster hogloid"))
    156 
    157 Below is the explanation from [hogloid](/profile/hogloid "Grandmaster hogloid").
    158 
    159 [From here]
    160 
    161 For each color, make a new graph that consists of the edges of the color and vertices connected by the edges. Make UnionFind for each graph, and you can check whether a color connects vertex *A* and *B* , using it. For each query, find a vertex which has smaller degree(let this vertex *A*, and the other vertex *B*) For each colors such that a edge of the color connects to *A*, check whether *A* and *B* is connected by the color. After answering the query, memorize its tuple — (*A*, *B*, *answer*). If the same query is requested, answer using this information.
    162 
    163 This will lead to ![](https://espresso.codeforces.com/da0f1b517a8e7d6aa04342c4e43c266866d04f61.png) solution.
    164 
    165 For each query, the complexity is ![](https://espresso.codeforces.com/10347386f6dc0e038f756b94d6808149d8e7eea7.png) (For each color connects *A*, find a vertex of *B* of the color & check whether they are connected) The queries that require longest computing time are, to ask every pair among ![](https://espresso.codeforces.com/cc36dccfe8c0168c9a297666c47c2329cbd10095.png) vertices which have largest degrees. Let the indices of the ![](https://espresso.codeforces.com/cc36dccfe8c0168c9a297666c47c2329cbd10095.png) vertices be ![](https://espresso.codeforces.com/02716c38518cbfe47950ab23292531c2d5a3f5c7.png), and degrees of the ![](https://espresso.codeforces.com/cc36dccfe8c0168c9a297666c47c2329cbd10095.png) vertices be *d*1, *d*2, ...*d**k*. Now, let's fix vertex *B* as *i*. The total computing time of the queries such that *B* is vertex *i* is  
    166 ![](https://espresso.codeforces.com/9c232df45b21c186f407e37c723e62033c419801.png) ![](https://espresso.codeforces.com/df6f07cc93de09ee4052218f05e72e3d3943ecc7.png).  
    167  Vertex *B* can vary from 2 to *k*. Hence, the total complexity is at most ![](https://espresso.codeforces.com/59d7a1672cad8ea119693cc34d66e190ad3f85a4.png). This complexity is at most ![](https://espresso.codeforces.com/fe6bc353a1ab706b5a82a177d10d455d147036b9.png).
    168 
    169 By the way, in C++, using unordered_map, total complexity would be ![](https://espresso.codeforces.com/ab0d2bd1fdb11f55601fc55919edf468b30d93f5.png).
    170 
    171 [End]
    172 
    173 There will be many other solutions. I will briefly explain one of them which I think is typical.
    174 
    175 Let *c**i* be the number of colors of the edges incident to vertex *i*. The sum of all *c**i* does not exceed 2*m* since each edge increases this sum by at most 2. Thus, there will be at most 450 values of *i* such that *c**i* ≥ 450 (let *B* = 450). We will call these vertices *large*, and the remaining ones *small*. Using *O*(*m* / *B*·*m*) = *O*(*m*2 / *B*) time and memory, we can precalculate and store the answer for all the possible queries where at least one of *u**i* and *v**i* is *large*, then we can immediately answer these queries. For the remaining queries, both *u**i* and *v**i* will be *small*, therefore it is enough to directly count the color that connects vertices *u**i* and *v**i* in *O*(*B*) time. The total time required will be *O*(*m*2 / *B* + *Bq*). If we choose ![](https://espresso.codeforces.com/3858eab4580fc7aedc51a2d6bdc19ca83431f77e.png), we can solve the problem in ![](https://espresso.codeforces.com/a1f72b7a38dfabfdd1f4bf017e76568f493f87c0.png) time.
    176 
    177 [The writer's code (the first solution, C++)](http://ideone.com/Uh7oXa)  
    178 The tester's code (the second solution, C++): [9501240](/contest/506/submission/9501240 "Submission 9501240 by evima")
    179 
    180 ### Div.1 E: [506E - Mr. Kitayuta's Gift](/contest/506/problem/E "Codeforces Round 286 (Div. 1)")
    181 
    182 [Problem] Given a string *s* and an integer *n*, find the number of the palindromes that can be obtained by inserting exactly *n* letters into *s*.
    183 
    184 Note: Div.2 A is a similar problem, where *n* is fixed to 1.
    185 
    186 (Problem from [evima](/profile/evima "Master evima"))
    187 
    188 First of all, let us note that we are asked to count the resulting palindromes, not the ways to obtain them. For example, if we are to insert "b" into "abba", there are 5 possible positions, but only 3 strings will be produced ("babba", "abbba" and "abbab"). Rather than trying to count the ways of inserting a letter *n* times and removing the duplicated results, we should directly count the resulting palindrome. To do that, let us reformulate the problem:
    189 
    190 [Problem'] Given a string *s* and an integer *n*, find the number of the palindromes of length |*s*| + *n* (let this number be *N*) that contains *s* as a subsequence (not necessarily contiguous).
    191 
    192 Consider constructing a palindrome from both ends, and matching it to *s* from both left and right. For example, let *s* = "abaac" and *N* = 11. Let us call the final resulting string *t*. We first decide what letter to use as *t*1 and *t*11 (they must be equal in order for *t* to be a palindrome). Let us say '**c**' is chosen. Now, we have to construct the remaining part of *t*, that is, *t*2..*t*10, so that *t*2..*t*10 contains "abaa" as a substring (note that the 'c' at the end of *s* is discarded). Again, we decide what letter to use as *t*2 and *t*10. This time we choose '**a**'. Then, we have to construct *t*3..*t*9, so that it contains "ba" as a substring (this time the two 'a's at the both ends of *s* are discarded). We choose *t*3 = *t*9 = '**c**'. Next, we construct *t*4..*t*8, so that it contains "ba" as a substring (this time *s* remains unchanged). We choose *t*4 = *t*8 = '**b**'. Then, we construct *t*5..*t*7, so that it contains "a" as a substring. We choose *t*5 = *t*7 = '**a**' (it is becoming repetitive, isn't it?). The last part of *t*, that is, *t*6, has no restriction (this time we choose a letter for only one position of *t*, not two). We choose '**d**', and we have obtained a palindrome "**cacbadabcac**" that contains *s* = "abaac" as a subsequence.
    193 
    194 This problem is mostly about analyzing this process carefully.
    195 
    196 The most naive solution other than literally enumerating all palindromes of length *N* would be the following Dynamic Programming: let *dp*[*i*][*left*][*right*] be the number of the palindromes *t* that can be obtained if you have already decided the leftmost and the rightmost *i* letters (2*i* in total), and the substring *s**left**s**left* + 1..*s**right* of *s* remains unmatched. Each value in this table can be computed in *O*(1) time. Of course, since *i* can be up to ⌊*n* / 2⌋ (*n* ≤ 109), this solution is far from our goal.
    197 
    198 Notice that the transitions from *dp*[*i*] to *dp*[*i* + 1] are the same regardless of *i*, thus we can calculate the table by matrix exponentiation. However, since there are *O*(|*s*|2) possible pairs for (*left*, *right*), we will need ![](https://espresso.codeforces.com/9aab90589adc61960fcdda97b83c2a6c917fbeab.png) time, which is actually worse than the naive calculation considering that |*s*| can be up to 200.
    199 
    200 This is where we need to observe the process which we have gone through at the beginning more carefully. Let us build a automaton corresponding to the process (the image below).
    201 
    202 ![ ](/predownloaded/61/e9/61e9c25b977bad7af00165b92070a9acabf16704.png)  
    203 (*) An self-loop with a number means that there are actually that number of edges.
    204 
    205 A process of producing a palindrome of length *N* that contains *s* as a subsequence corresponds to a path of length ⌈*N* / 2⌉ from the upper-right vertex to the lower-left vertex. Each red vertex has 24 self-loops since the letters at the both ends of the remaining part of *s* is different, which correspond to two non-self-loop transitions. Similarly, each green vertex has 25 self-loops since the first letter and the last letter of the remaining string is the same, and the blue vertex, the destination, has 26 self-loops, as there are no more non-self-loop transitions available.
    206 
    207 Here is an important fact: there are not so many possible combination of (*n*24, *n*25), where *n*24 and *n*25 are the number of times a path from START to GOAL visits a red vertex (with 24 self-loops) and a green vertex (with 25 self-loops), respectively. Why? Each time we leave a red vertex, the length of the remaining unmatched part of *s* decreases by 1, since exactly one of the two letters at the ends of the remaining part is matched and discarded. Similarly, each time we leave a green vertex, the length of the remaining string decreases by 2, since both of the two letters at the ends are matched and discarded. There is a exception, however: if the length of the remaining string is 1, then it will be a green vertex, but in this case the length will decrease by 1. Thus, for any path from START to GOAL, *n*24 + 2·*n*25 will be equal to either |*s*| or |*s*| + 1. If we fix *n*24, then *n*25 will be uniquely determined by *n*25 = ⌈(|*s*| - *n*24) / 2⌉. Since *n*24 can only take the value between 0 and |*s*| - 1, there are at most |*s*| possible pairs of (*n*24, *n*25).
    208 
    209 With this fact, we are ready to count the paths: let us classify them by the value of *n*24. For each possible pair of (*n*24, *n*25), let us count the number of corresponding paths. To do that, we divide each paths into two parts: first we count the number of paths from START to GOAL, using only non-self-loop transitions. Then, we count the ways of inserting self-loop transitions into each of these paths. The product of these two numbers will be the number that we seek.
    210 
    211 The first part is straightforward to solve: let *dp*[*left*][*right*][*n*24] be the number of paths from the vertex that corresponds to the substring *s**left**s**left* + 1..*s**right*, visiting exactly *n*24 red vertices using only non-self-loop transitions. Each value of the table can be found in *O*(1) time, thus the whole table can be computed in *O*(|*s*|3) time, which is fast enough for the input size (|*s*| ≤ 200).
    212 
    213 The main obstacle will be the second part. For example, let us consider the case where *s* = "abaac", *N* = 11, *n*24 = 2, which corresponds to the example at the beginning. From the fact we found earlier, *n*25 = ⌈(|*s*| - *n*24) / 2⌉ = ⌈(5 - 2) / 2⌉ = 2. Thus, we have to insert ⌈*N* / 2⌉ - *n*24 - *n*25 = 6 - 2 - 2 = 2 self-loop transitions into this path (the image):
    214 
    215 ![ ](/predownloaded/1a/46/1a46a6e5a205f97d99f47d51742923169cd65aa4.png)
    216 
    217 The order in which red, green and blue vertices appears in this path does not affect the number of ways of insertion, and can be arbitrary. The number of ways to insert 2 self-loop transitions will be equal to the number of the path of length ⌈*N* / 2⌉ = 6 from START to GOAL in this automaton (we have to take into account the non-self-loop transitions in it), which can be calculated by matrix exponentiation.
    218 
    219 Are we done? No! Consider the case *s* = "abbb..(|*s*| - 1 times)..bb". There are |*s*| - 1 possible values of *n*24 (*n*24 = 1 corresponds to the case where you match and discard the 'a' first, and *n*24 = |*s*| - 1 corresponds to the case where you keep the 'a' until *s* becomes "ab"). Thus, you need to perform matrix exponentiation |*s*| - 1 times, which results in a total of ![](https://espresso.codeforces.com/0035c11989babc7d8d0ba55cc26ddd5ec82a2f50.png) time, which will be too much under the given constraints.
    220 
    221 There is still hope, though, and here is the climax. Notice that these automata are very similar to each other, and they differ only in the number of the red and green vertices. We can combine these automata into one larger automaton like this (the image):
    222 
    223 ![ ](/predownloaded/5e/54/5e54f2c067227e74f7a2c1338e076f3b2a0874aa.png)  
    224 The combined automaton should have |*s*| - 1 red, ⌈|*s*| / 2⌉ green and ⌈|*s*| / 2⌉ blue vertices.
    225 
    226 By performing matrix exponentiation on this automaton instead of many small automata, we can find all the required value in ![](https://espresso.codeforces.com/e8972394f2eb29775355e17c6a09511f58766e1b.png) time, which should be enough. We recommend speeding up matrix multiplication by noticing that the matrix will be upper triangular (6 times faster on paper), since the time limit is not so generous (in order to reject ![](https://espresso.codeforces.com/0035c11989babc7d8d0ba55cc26ddd5ec82a2f50.png) solutions).
    227 
    228 The problem is almost solved, but there is one more challenge. When *N* is odd, the situation becomes a little complicated: as we have seen at the beginning, in the last (⌈*N* / 2⌉-th) step of producing a palindrome we choose a letter for only one position of the resulting string, that is, the center of that string. In other words, the last transition in the path in the automaton we have first built must not be one from a green vertex with a string of length 2 (for example, "aa") to GOAL.
    229 
    230 Let us find the number of the paths that violates this condition and subtract it from the answer. As previously mentioned, for each path *n*24 + 2·*n*25 will be equal to either |*s*| or |*s*| + 1, and if we fix the value of *n*24, *n*25 will be uniquely determined by *n*25 = ⌈(|*s*| - *n*24) / 2⌉. If |*s*| - *n*24 is odd, then it means that the last non-self-loop transition is one from a green vertex with a string of length 1, therefore in this case no path will violate the condition. If |*s*| - *n*24 is even, then the last non-self-loop trantision is from a green vertex with a string of length 2, thus the paths that does not contain the self-loop from GOAL to itself violate the condition. It will be equal to the number of the paths of length ⌈*N* / 2⌉ - 1 from START to the vertex just before GOAL, which can be found in a similar way to the second part of the solution.
    231 
    232 The journey has finally come to an end. Actually, it is also possible to solve this problem in ![](https://espresso.codeforces.com/8bcadca0abfe6b4adc9de2b3b2454522796b931d.png) time without matrix exponentiation, but this margin is too small to explain it. I will just paste the link to the code.
    233 
    234 The writer's code (matrix exponentiation, C++): [9501164](/contest/506/submission/9501164 "Submission 9501164 by evima")  
    235 The writer's code (without matrix exponentiation, C++): [9501177](/contest/506/submission/9501177 "Submission 9501177 by evima")
    236 
    237 Congratulations again to [Petr](/profile/Petr "International Grandmaster Petr") who was the only participant to solve this problem in 108 minutes. Also, I would like to give a special mention to [rng_58](/profile/rng_58 "International Grandmaster rng_58"), who was VERY close to solving it in only 63 minutes. He was just one byte away from getting AC (compare [9460984](/contest/506/submission/9460984 "Submission 9460984 by rng_58") and [9465440](/contest/506/submission/9465440 "Submission 9465440 by rng_58"))!   
    238    
    239    
    240    
    241  If you find a possible error, or have a question, please feel free to ask here. Alternative solutions are also welcome.