codeforces-scrape

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

543.md (8547B)


      1 Source: https://codeforces.com/blog/entry/17773
      2 
      3 ### [544A - Set of Strings](/contest/544/problem/A "Codeforces Round 302 (Div. 2)")
      4 
      5 In that task you need to implement what was written in the statements. Let's iterate over all characters of string and keep array *used*. Also let's keep current string. If current character was not used previously, then let's put current string to the answer and after that we need to clear current string. Otherwise, let's append current character to the current string. If array, that contain answer will have more then *k* elements, we will concatenate few last strings.
      6 
      7 The jury solution: [11035685](/contest/544/submission/11035685 "Submission 11035685 by gridnevvvit")
      8 
      9 ### [544B - Sea and Islands](/contest/544/problem/B "Codeforces Round 302 (Div. 2)")
     10 
     11 It's clear to understand, that optimal answer will consists of simple cells, for which following condition fullfills: the sum of indices of row and column is even. We will try to put *k* islands in such way, and if it's impossible, we will report that answer is NO. Try to prove that this solution is optimal.
     12 
     13 The jury solution: [11035691](/contest/544/submission/11035691 "Submission 11035691 by gridnevvvit")
     14 
     15 ### [543A - Writing Code](/contest/543/problem/A "Codeforces Round 302 (Div. 1)")
     16 
     17 Let's create the solution, which will work too slow, but after that we will improve it. Let's calculate the following dynamic programming *z*[*i*][*j*][*k*] — answer to the problem, if we already used exactly *i* programmers, writed exactly *j* lines of code, and there are exactly *k* bugs. How we can do transitions in such dp? We can suppose that we *i*-th programmer will write *r* lines of code, then we should add to *z*[*i*][*j*][*k*] value *z*[*i* - 1][*j* - *r*][*k* - *ra*[*i*]]
     18 
     19 But let's look at transitions from the other side. It's clear, that there are exactly 2 cases. The first case, we will give any task for *i*-th programmer. So, we should add to *z*[*i*][*j*][*k*] value *z*[*i* - 1][*j*][*k*]. The second case, is to give at least one task to *i*-th programmer. So, this value will be included in that state: *z*[*i*][*j* - 1][*k* - *a*[*i*]]. In that solution we use same idea, which is used to calculate binomial coefficients using Pascal's triangle. So overall solution will have complexity: *O*(*n*3)
     20 
     21 The jury solution: [11035704](/contest/543/submission/11035704 "Submission 11035704 by gridnevvvit")
     22 
     23 ### [543B - Destroying Roads](/contest/543/problem/B "Codeforces Round 302 (Div. 1)")
     24 
     25 Let's solve easiest task. We have only one pair of vertices, and we need to calculate smallest amout of edges, such that there is a path from first of vertex to the second. It's clear, that the answer for that problem equals to shortest distance from first vertex to the second.
     26 
     27 Let's come back to initial task. Let's *d*[*i*][*j*] — shortest distance between *i* and *j*. You can calculate such matrix using bfs from each vertex.
     28 
     29 Now we need to handle two cases:
     30 
     31 1. Paths doesn't intersects. In such way we can update the answer with the following value: *m* - *d*[*s*0][*t*0] - *d*[*s*1][*t*1] (just in case wheh conditions on the paths lengths fullfills).
     32 2. Otherwise paths are intersecting, and the correct answer looks like a letter 'H'. More formally, at the start two paths will consists wiht different edges, after that paths will consists with same edges, and will finish with different edges. Let's iterate over pairs (*i*, *j*) — the start and the finish vertices of the same part of paths. Then we can update answer with the following value: *m* - *d*[*s*0][*i*] - *d*[*i*][*j*] - *d*[*j*][*t*0] - *d*[*s*1][*i*] - *d*[*j*][*t*1] (just in case wheh conditions on the paths lengths fullfills).
     33 
     34 Please note, that we need to swap vertices *s*0 and *t*0, and recheck the second case, because in some situations it's better to connect vertex *t*0 with vertex *i* and *s*0 with vertex *j*. Solutions, which didn't handle that case failed system test on testcase 11.
     35 
     36 The jury solution: [11035716](/contest/543/submission/11035716 "Submission 11035716 by gridnevvvit")
     37 
     38 ### [543C - Remembering Strings](/contest/543/problem/C "Codeforces Round 302 (Div. 1)")
     39 
     40 First that we need to notice, that is amout of strings is smaller then alphabet size. It means, that we can always change some character to another, because at least one character is not used by some string.
     41 
     42 After that we need handle two cases:
     43 
     44 1. We can change exactly one character to another. The cost of such operation equals to *a*[*i*][*j*] (which depends on chosed column) After that we can remember string very easy.
     45 2. We can choose some column, and choose some set of strings, that have same character in that column, By one move we can make all these strings are easy to remember.The cost of such move equals to cost of all characters, except most expensive.
     46 
     47 As the result, we will have following solution: d[mask] — answer to the problem, when we make all strings from set *mask* easy to remember. We can calculate this dp in following way: let *lowbit* — smallest element of set *mask*. It's clear, that we can do this string easy to remember using first or second move. So we need just iterate over possible columns, and try first or second move (in second move we should choose set that contain string *lowbit*) Overall complexity is *O*(*m*2*n*), where *m* — is length of strings.
     48 
     49 The jury solution: [11035719](/contest/543/submission/11035719 "Submission 11035719 by gridnevvvit")
     50 
     51 ### [543D - Road Improvement](/contest/543/problem/D "Codeforces Round 302 (Div. 1)")
     52 
     53 Let's suppose *i* is a root of tree. Let's calculate extra dynamic programming *d*[*i*] — answer to the problem for sub-tree with root *i* We can understand, that d[i] equals to the following value: ![](https://espresso.codeforces.com/f11cebcf8276d2343d36e85a52d71bc2174f103e.png) — where *j* is a child of the vertex *i*. It's nice. After that answer to problem for first vertex equal to *d*[1].
     54 
     55 After that let's study how to make child *j* of current root *i* as new root of tree. We need to recalculate only two values *d*[*i*] and *d*[*j*]. First value we can recalculate using following formula *d*[*i*]: *suf*[*i*][*j*] * *pref*[*i*][*j*] * *d*[*parent*], where *parent* — is the parent of vertex *i*, (for vertex 1 *d*[*parent*] = 1), and array *suf*[*i*][*j*] — is the product of values *d*[*k*], for all childs of vertex *i* and *k* < *j* (*pref*[*i*][*j*] have same definition, but *k* > *j*). And after we can calculate *d*[*j*] as *d*[*j*] * (*d*[*i*] + 1). That is all, *j* is root now, and answer to vertex *j* equals to current value *d*[*j*]
     56 
     57 The jury solution: [11035737](/contest/543/submission/11035737 "Submission 11035737 by gridnevvvit")
     58 
     59 ### [543E - Listening to Music](/contest/543/problem/E "Codeforces Round 302 (Div. 1)")
     60 
     61 Let's sort all songs in decreasing order. We will iterate over songs, and each time we will say, that now current song will fully satisfy our conditions. So, let's *s**i* = 0, is song *i* was not processed yet and *s**i* = 1 otherwise. Let ![](https://espresso.codeforces.com/215b36a22889b3c464f08f17bdc7f7ae1486dd73.png). It's clear, when we add new song in position *idx* then we should do  + 1 for all on segment [*max*(0, *idx* - *m* + 1), *idx*] in our array *v*. So, when we need to implement some data structure, which can restore our array *v* to the position when all strings have quality  ≥ *q*. It also should use very small amout of memory. So, answer to the query will be *m* - *max*(*v**i*), *l**j* ≤ *i* ≤ *r**j*.
     62 
     63 We will store this data structure in the following way. Let's beat all positions of songs in blocks of length ![](https://espresso.codeforces.com/909ec83af66a546b3f5db58ea951d4a6289ac97d.png). Each time, when we added about ![](https://espresso.codeforces.com/909ec83af66a546b3f5db58ea951d4a6289ac97d.png) songs as good, we will store three arrays: first array will contain value *v**i* of first element of the block of indices. second array will contain maximum value of *v* on each block and also we will keep about ![](https://espresso.codeforces.com/ba2f98320949073edadb09c55ed8c3df9726083c.png) of ''small'' updates which doesn't cover full block. Using this information array *v* will be restored and we process current query in easy way.
     64 
     65 The jury solution: [11035739](/contest/543/submission/11035739 "Submission 11035739 by gridnevvvit")