codeforces-scrape

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

187.md (10613B)


      1 Source: https://codeforces.com/blog/entry/4540
      2 
      3 ### Problem [189A — Cut Ribbon](//www.codeforces.com/problemset/problem/189/A)
      4 
      5 The problem is to maximize *x+y+z* subject to *ax+by+cz=n*. Constraints are low, so simply iterate over two variables (say *x* and *y*) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions.
      6 
      7 Other approaches: Use dynamic programming with each state being the remainder of ribbon. Select the next piece to be *a*, *b* or *c*.
      8 
      9 ### Problem [189B — Counting Rhombi](//www.codeforces.com/problemset/problem/189/B)
     10 
     11 Observe that lots of rhombi have the same shape, but are in different locations.
     12 
     13 What uniquely determines the shape of a rhombus? Its width and its height.
     14 
     15 Is it possible to build a rhombus with every width and every height such that the vertices of the rhombus are in integer points? No, it is possible only if the width and the height are both even.
     16 
     17 How many places we can put a rhombus of width *w0* and height *h0* in a rectangle of width *w* and height *h*? *(w * w0 + 1)(h * h0 + 1)*
     18 
     19 So, iterator over all even widths and heights and for each of them add the number of possible locations to the final result.
     20 
     21 ### Problem [187A — Permutations](//www.codeforces.com/problemset/problem/187/A)
     22 
     23 It is easy to see that if we replace each number in the first permutation with position of that number in the second permutation, the problem reduces to sorting the first permutation.
     24 
     25 Each time we take a number from the end of array, we can postpone its insertion until we know the most suitable position for insertion. Note that it is not good to insert a number and take it again, as we could make a better decision first time we took the number.
     26 
     27 So, as long as the remainder of the array is not in increasing order, we should take more numbers from the end. But as soon as you have an increasing subsequence, you can insert the numbers you have taken to make the array sorted.
     28 
     29 Therefore to solve the problem, we find the largest *i* such the numbers from *1* to *i* are in increasing order. The answer would be *n-i*.
     30 
     31 ### Problem [187B — AlgoRace](//www.codeforces.com/problemset/problem/187/B)
     32 
     33 First we solve the problem when the number of allowed car changes is zero (_k=0_). Let *W(i,j,l)* be the length of shortest path from *i* to *j* with car *l*. We use Floyd-Warshal on graph of each car to find this value. Then answer for the case that we can use only one car for each pair of cities *i* and *j* is:
     34 
     35 *ans(0,i,j) = min W(i,j,l)* for (_1≤l≤m_)
     36 
     37 This part has time complexity *O(m*n^3)*.
     38 
     39 For larger values of maximum number of changes (_k_), we use the following equation:
     40 
     41 *ans(k,i,j) = min (ans(k-1,i,l)+ans(0,l,j))* for (_1≤l≤k_)
     42 
     43 which can be computed in *O(k*n^3)* using dynamic programming.
     44 
     45 But how large can be *k* in worst case? We know that shortest paths are simple paths (i.e. they have no repeated vertices). Because otherwise we could eliminate the path we go between two appearances of one vertex and have a smaller result. This and the fact that we change the car at most once in each vertex, guarantees in any optimal solution we will not need more that *n* car changes. Thus the order of the solution would be *O(m*n^3+n^4)*.
     46 
     47 ### Problem [187C — Weak Memory](//www.codeforces.com/problemset/problem/187/C)
     48 
     49 There were many different correct approaches to this problem during the contest. But I will explain author’s solution.
     50 
     51 First we can use binary search over the value of *q*. Now for a fixed *q* we want to check *s-t* connectivity.
     52 
     53 Let *K* be the set of all intersections with volunteers union s and t. One can use BFS from each *k∈K*, one by one. Then build a graph *G’* with vertices *K*. For each two vertices *k1,k2∈K* add an edge between them, if their shortest distance is less than or equal to *q*. Finally use any path finding algorithm to check the connectivity. Unfortunately this solution has time (and space) complexity of *O(|K|*m)* which is not good enough.
     54 
     55 We can optimize the above solution by initiating BFS from all *k∈K* at once. In other words during the initialization step in BFS algorithm, we push all these vertices in the queue with distance *0*. Each element in the queue also maintains its source (i.e. the source it is originating from). In BFS each time we have have a vertex *u* with source *su* and we want to set the minimum distance to a vertex *v* that is already set from a different path with source *sv*, we connect *su* and *sv* in *G’* if *d(u)+d(v)+1<= q*, where *d(x)* denotes length of the shortest path from a vertex in *K* to *x*. As we are only dealing with connectivity, this approach is correct. (Proof of correctness is left as an exercise)
     56 
     57 BFS takes *O(m)* time and we add at most *O(m)* edges to *G’*, so the overall complexity is *O(m)* for a fixed *q*. As we used binary search to find the smallest *q*, we can solve the problem in *O(m*logn)*.
     58 
     59 ### Problem [187D — BRT Contract](//www.codeforces.com/problemset/problem/187/D)
     60 
     61 We define *ti* as follows: assume a bus starts moving from *i*-th intersection exactly at the time when the light changes to green. The time it takes for the bus to get the final station is *ti*. We call the times when a green interval begins *t0* (so every *g+r* seconds *t0* occurs once)
     62 
     63 If a bus gets to *i*-th intersection during the red phase, it should wait and then start moving at *t0*. So considering the fact that all lights are synchronized (and length of segments are fixed) if we have *ti* for *i*-th intersection, we can compute the time for the bus to get final station.
     64 
     65 Clearly *tn* is the length of the last segments. For computing *ti* we should find the smallest *j* such that if a bus starts at *t0* from *i*-th intersection, it gets to *j*-th intersection during the red phase. So we have:
     66 
     67 *ti=tj+d(i,j)+w*
     68 
     69 where *d(i,j)* is the distance between *i*-th and *j*-th intersections and *w* is the time that the bus should wait behind the red light at *j*-th intersection. The later value can be computed easily.
     70 
     71 The only problem that remains is to find *j* for *i*-th intersection. So we start iterating over *i* for *(n-1)*-th intersection backwards and we compute *ti* for all intersections. Assume *p=g+r* and *ta=d(i,j)%p*. Now if the bus starts from *i*-th intersection at time *t0* and we have *ta>=g*, in this case we are in red phase at *j*-th intersection. Actually *ta* should be in interval [_g, g+r_).
     72 
     73 Here we can use segment trees. That is for all intersections from *i+1* to *n*, we store some values in the tree that helps us find the smallest *j*. But we should note the value of *ta* depends on *d(i,j)* which changes as *i* changes. Thus we cannot use *ta* in the tree. Instead, we define *si* the be the distance of *i*-th intersection to the destination. So we have *d(i,j)=si-sj* and we use the value of *sj* with storing *–sj%p* in the segment tree as the key and the value would be *j* itself. In other words for each intersection we store the key-value pair *(-sj%p, j)* in the tree. According to what we said so far, to be in the red phase at *j*-th intersection we should have:
     74 
     75 *ta=(d(i,j)%p)=((si-sj)%p)∈[g,g+r) => -sj%p ∈ [(g-si)%p, (g+r-si)%p)*
     76 
     77 As we stored *–sj%p* in the tree, we can retrieve the smallest *j* in the above interval with a query in the segment tree.
     78 
     79 This way we can compute *ti* for all intersections. Answering to each query in the problem can be solve in exactly the same way. So the overall complexity would be *O((n+q)logn)*.
     80 
     81 ### Problem [187E — Heaven Tour](//www.codeforces.com/problemset/problem/187/E)
     82 
     83 **Step 1**. Solve the problem if the starting man is the leftmost man and the finishing man is the rightmost man.
     84 
     85 Obviously every segment (the distance between two consecutive men) should be covered at least once. We also argue that at least *l* (the number of left tickets) segments should be covered at least three times.
     86 
     87 *Proof*: Each time you use a left ticket to go to man *i* with *1<i<n-1*, the segment between *i*-th and (_i+1_)-th men is covered at least three times:
     88 
     89 1. Once for you should go after *i* be in a position to come back.
     90 2. Once for you use a left ticked to come back to *i*
     91 3. And once again you should go after *i*, because you want to finish at man number *n*
     92 
     93 Note that in the first and the last segments are always covered once, no matter what we do. But except for these two segments, every other segment can be chosen to be among the segments that are covered three times, and every combination that we choose *l* segments is feasible. (Proof it as practice) So we choose the smallest *l* segments and the problem can be solved with a simple sort in *O(n*logn)*.
     94 
     95 **Step 2**. Solve the problem if the starting man is the leftmost man, but the finishing man can be anywhere.
     96 
     97 To solve this problem we first fix the finishing man. With reasoning similar to that of step 1, we conclude that at least *l* segments should be covered with at least two times if they are after the finishing man or three times if they are before him. But obviously every segment after the finishing man is covered at least two times. So it is always good to waste as many left tickets as possible after the finishing man to prevent them from breaching the left side of finishing man and becoming multiple three.
     98 
     99 So the algorithm would be: iterate over *i*, the number of finishing man, and maintain the *l-(n-i)* smallest segments to the right of finishing man as you progress. This can be implemented in *O(n*logn)*.
    100 
    101 **Step 3**. Solve the problem if the starting man is fixed, but the finishing man can be anywhere.
    102 
    103 Assume that the starting man is not the first man or the last man, otherwise we could use algorithm of step 2 to solve the problem. Without loss of generality assume that you finish your tour to the right side of finishing man. Therefore every segment to the left of starting man is covered at least two times and actually it is always possible to arrange visits such that every segment to right is covered exactly two times. So just like what we said in step 2, it is good to waste as many left tickets as possible in this area.
    104 
    105 So the algorithm would be, choose to finish left or right first, then greedily waste as many bad moves (by bad moves I mean the moves that if breach to the other side will be more costly) as possible there and follow the algorithm in step 2 to solve the whole problem.
    106 
    107 There are some special cases such as when the tour cannot be finished at all, that we left to readers find a way how to handle them.