codeforces-scrape

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

653.md (12461B)


      1 Source: https://codeforces.com/blog/entry/43886
      2 
      3 Problems ABCG will be described better soon.
      4 
      5 problem A — watch out for test like "1 1 1 2 2 2 2 3 3 3". It shows that it's not enough to sort number and check three neighbouring elements. You must remove repetitions. The easier solution is to write 3 for-loops, without any sorting. Do you see how?
      6 
      7 problem B — you should generate all 6*n* possible starting strings and for each of them check whether you will get "a" at the end. Remember that you should check two first letters, not last ones (there were many questions about it).
      8 
      9 [653C - Bear and Up-Down](/contest/653/problem/C) — Let's call an index *i* bad if the given condition about *t**i* and *t**i* + 1 doesn't hold true. We are given a sequence that has at least one bad place and we should count ways to swap two elements to fix all bad places (and not create new bad places). The shortest (so, maybe easiest) solution doesn't use this fact but one can notice that for more than 4 bad places the answer is 0 because swapping *t**i* and *t**j* can affect only indices *i* - 1, *i*, *j* - 1, *j*.
     10 
     11 With one iteration over the given sequence we can find and count all bad places. Let *x* denote index of the first bad place (or index of some other bad place, it's not important). We must swap *t**x* or *t**x* - 1 with something because otherwise *x* would still be bad. Thus, it's enough to consider *O*(*n*) swaps ~-- for *t**x* and for *t**x* - 1 iterate over index of the second element to swap (note that "the second element" doesn't have to be bad and samples show it). For each of *O*(*n*) swaps we can do the following (let *i* and *j* denote chosen two indices):
     12 
     13 1. Count bad places among four indices: *i* - 1, *i*, *j* - 1, *j*. If it turns out that these all not all initial bad places then we don't have to consider this swap — because some bad place will still exist anyway.
     14 2. Swap *t**i* and *t**j*.
     15 3. Check if there is some bad place among four indices: *i* - 1, *i*, *j* - 1, *j*. If not then we found a correct way.
     16 4. Swap *t**i* and *t**j* again, to get an initial sequence.
     17 
     18 Be careful not to count the same pair of indices twice. In the solution above it's possible to count twice a pair of indices (*x* - 1, *x*) (where *x* was defined in the paragraph above). So, add some `if` or do it more brutally — create a set of pairs and store sorted pairs of indices there.
     19 
     20 TODO — add codes.
     21 
     22 **CHALLENGE** — can you solve this problem if the initial sequence is already nice (if it doesn't have bad places)?
     23 
     24 [653D - Delivery Bears](/contest/653/problem/D) — invented and prepared by [Lewin](/profile/Lewin "International Master Lewin"), also the editorial.
     25 
     26 Java code: [16825205](/contest/653/submission/16825205 "Submission 16825205 by Errichto")  
     27 C++ code solving also the harder version: [16825257](/contest/653/submission/16825257 "Submission 16825257 by Errichto")
     28 
     29 Let's transform this into a flow problem. Here, we transform "weight" into "flow", and each "bear" becomes a "path".
     30 
     31 Suppose we just want to find the answer for a single *x*. We can do this binary search on the flow for each path. To check if a particular flow of *F* is possible, reduce the capacity of each edge from *c**i* to ![](https://espresso.codeforces.com/012613345f808cc65d3d2e7fa134fe6aae22ebcd.png). Then, check if the max flow in this graph is at least *x*. The final answer is then *x* multiplied by the flow value that we found.
     32 
     33 **MUCH HARDER VERSION** — you are also given an integer *k* (1 ≤ *k* ≤ 104) and your task is to find the answer for *x* paths, for *x* + 1 paths, ..., and for *x* + *k* - 1 paths. There should be *k* real values on the output.
     34 
     35 **The solution of the harder version.**
     36 
     37 However, this is not fast enough when we have up to 10^4 values of x to check.
     38 
     39 Instead, we look at a fast way of getting the flow value for x+1 paths given a flow with x paths in only O(m log m) time.
     40 
     41 Suppose we've found the paths for x bears, and we know that the number of bears who use edge number i is w_i. Also, let f_x be the weight that each bear carries, given that there are x bears.
     42 
     43 Then, we can create a residual graph as follows: For each edge (u_i -> v_i) with capacity c_i, create an edge in th residual graph from u_i to v_i with capacity (c_i) / (1 + w_i), and if w_i > 0, a backward edge with capacity f_x.
     44 
     45 Then, we can find the fattest path in this graph with a dijsktra's in O(m log m), giving us f_(x+1). This also allows us to update our paths. In particular, if we use a backwards edge, we subtract the number of times the edge is used by 1, otherwise, we increase it by 1. This allows us to construct a new residual graph. It can be shown that this only results in at most one new path.
     46 
     47 We can prove that this is correct by induction. Suppose the answer is correct for x bears.
     48 
     49 Now, one observation is that f_(x+1) must be less than or equal to f_x, as any plan that x+1 bears follow will also be able to be executed with x bears.
     50 
     51 Suppose the optimal solution for x+1 bears is actually g_(x+1). We just need to argue that f_(x+1) >= g_(x+1) and we are done. In the optimal solution, consider replacing each edge with capacity c_i to floor(c_i/g_(x+1)). Now, consider the optimal paths for x bears in this reduced capacity graph (which we found through induction). Since there are only x bears, but we know we can support x+1 bears, there exists a path in the residual graph from the source to the sink. Let's look at the capacity of this path. If we travel along any backward edge, the capacity of that edge is f_x which is at least g_(x+1). If we travel on a forward edge, we have c_i/(1+w_i) >= g_(x+1) <=> c_i >= (1+w_i)*g_(x+1). The second inequality follows from reversing the "divide by g_(x+1)" step.
     52 
     53 Thus, the overall running time is O(mn^2 * log(m*x) + k*m log m), where the first part comes from the initial binary search, and the second part comes from doing k fattest path computations.
     54 
     55 [653E - Bear and Forgotten Tree 2](/contest/653/problem/E)
     56 
     57 C++ code: [16826422](/contest/653/submission/16826422 "Submission 16826422 by Errichto")
     58 
     59 You are given a big graph with some edges forbidden, and the required degree of vertex 1. We should check whether there exists a spanning tree. Let's first forget about the condition about the degree of vertex 1. The known fact: a spanning tree exists if and only if the graph is connected (spend some time on this fact if it's not obvious for you). So, let's check if the given graph is connected. We will do it with DFS.
     60 
     61 We can't run standard DFS because there are maybe *O*(*n*2) edges (note that the input contains forbidden edges, and there may be many more allowed edges then). We should modify it by adding a set or list of unvisited vertices *s*. When we are at vertex *a* we can't check all edges adjacent to *a* and instead let's iterate over possible candidates for adjacent unvisited vertices (iterate over *s*). For each *b* in *s* we should check whether *a* and *b* are connected by a forbidden edge (you can store input edges in a set of pairs or in a similar structure). If they are connected by a forbidden edge then nothing happens (but for each input edge it can happen only twice, for each end of edge, thus *O*(*m*) in total), and otherwise we get a new vertex. The complexity is ![](https://espresso.codeforces.com/b73a19684d88a96f3a456576c02db5bd7b2ee21f.png) where ![](https://espresso.codeforces.com/cf48c72d2ddb470d0e89f3186f9d1ac3750d7694.png) is from using set of forbidden edges.
     62 
     63 Now we will check for what degree of vertex 1 we can build a tree. We again consider a graph with *n* vertices and *m* forbidden edges. We will first find out what is **the minimum** possible degree of vertex 1 in some spanning tree. After removing vertex 1 we would get some connected components and in the initial graph they could be connected to each other only with edges to vertex 1. With the described DFS we can find *c* (1 ≤ *c* ≤ *n* - 1) — the number of created connected components. Vertex 1 must be adjacent to at least one vertex in each of *c* components. And it would be enough to get some tree because in each component there is some spanning tree — together with edges to vertex 1 they give us one big spanning tree with *n* vertices (we assume that the initial graph is connected).
     64 
     65 And **the maximum** degree of vertex 1 is equal to the number of allowed edges adjacent to this vertex. It's because more and more edges from vertex 1 can only help us (think why). It will be still possible to add some edges in *c* components to get one big spanning tree.
     66 
     67 So, what is the algorithm? Run the described DFS to check if the graph is connected (if not then print "NO"). Remove vertex 1 and count connected components (e.g. starting DFS's from former neighbours of vertex 1). Also, simply count *d* — the number of allowed edges adjacent to vertex 1. If the required degree *k* is between *c* and *d* inclusive then print "YES", and otherwise print "NO".
     68 
     69 [653F - Paper task](/contest/653/problem/F) — invented and prepared by [k790alex](/profile/k790alex "Specialist k790alex"), also the editorial.
     70 
     71 Java code (modify-SA-solution): [16821422](/contest/653/submission/16821422 "Submission 16821422 by k790alex")  
     72 C++ code (compressing-solution): [16826803](/contest/653/submission/16826803 "Submission 16826803 by Errichto")
     73 
     74 There are two solutions. The first and more common solution required understanding how do SA (suffix array) and LCP (longest common prefix) work. The second processed the input string first and then run SA+LCP like a blackbox, without modifying or caring about those algorithms.
     75 
     76 **Modify-SA-solution** — The main idea is to modify the algorithm for computing the number of distinct substrings using SA + LCP.
     77 
     78 Let *query*(*L*, *R*) denote the number of well formed prefixes of *substring*(*L*, *R*). For example, for *substring*(*L*, *R*) = "(())()(" we would have *query*(*L*, *R*) = 2 because we count (()) oraz (())().
     79 
     80 How to be able to get *query*(*L*, *R*) fast? You can treat the opening bracket as  + 1 and the ending bracket as  - 1. Then you are interested in the number of intervals starting in *L*, ending not after *R*, with sum on the interval equal to zero. Additionally, the sum from *L* to any earlier right end can't be less than zero. Maybe you will need some preprocessing here, maybe binary search, maybe segment trees. It's an exercise for you.
     81 
     82 We can iterate over suffix array values and for each suffix we add *query*(*suffix*, *N*) - *query*(*suffix*, *suffix* + *LCP*[*suffix*] - 1) to the answer. In other words we count the number of well formed substrings in the current suffix and subtract the ones we counted in the previous step.
     83 
     84 The complexity is ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) but you could get AC with very fast solution with extra ![](https://espresso.codeforces.com/cf48c72d2ddb470d0e89f3186f9d1ac3750d7694.png).
     85 
     86 **Compressing-solution** — I will slowly compress the input string, changing small well-formed substrings to some new characters (in my code they are represented by integer numbers, not by letters). Let's take a look at the example:  
     87 ![](https://espresso.codeforces.com/5198a17852c0db65a25f29073ee83db4ba05655f.png)  
     88 or equivalently:  
     89 ![](https://espresso.codeforces.com/5785d244d1d261728b5cda932dedc36ff0019354.png)
     90 
     91 Whenever I have a maximum (not possible to expand) substring with single letters only, without any brackets, then I add this substring to some global list of strings. At the end I will count distinct substrings in the found list of strings (using SA+LCP). In the example above I would first add a string "a" and later I would add "baa". Note that each letter represents some well formed substring, e.g. 'b' represents (()) here.
     92 
     93 I must make sure that the same substrings will be compressed to the same letters. To do it, I always move from left to right, and I use trie with map (two know what to get from some two letters).
     94 
     95 problem G — you can consider each prime number separately. Can you find the answer if there are only 1's and 2's in the input? It may be hard to try to iterate over possible placements of the median. Maybe it's better to think how many numbers we will change from 2^p to 2^{p+1}.