codeforces-scrape

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

524.md (8275B)


      1 Source: https://codeforces.com/blog/entry/17065
      2 
      3 Problemsets slightly differ in main round and in an online mirror, in editorial problems follow in an order of the main round.
      4 
      5 # [524A - Возможно, вы знаете этих людей?](/contest/524/problem/A "VK Cup 2015 - Round 1")
      6 
      7 This problem didn't appear in an online mirror. Its editorial will be left as an exercise in Russian language for those who are curious what it is about =)
      8 
      9 # [524B - Фото на память - 2 (round version)](/contest/524/problem/B "VK Cup 2015 - Round 1")
     10 
     11 In an original version there was no constraint that no more than n / 2 friends should lie. This version can be solved pretty easy. Iterate over all possible values of *H*. For a fixed *H* we have to minimize total width of all rectangles on the photo. So, for each rectangle we need to choose in which orientation it fits into photo having the minimum possible width.
     12 
     13 # [529B - Group Photo 2 (online mirror version)](/contest/529/problem/B "VK Cup 2015 - Round 1 (unofficial online mirror, Div. 1 only)")
     14 
     15 In an online mirror version the problem was slightly harder. Let's call people with *w* ≤ *h* \textit{high}, and remaining people \textit{wide}. Let's fix photo height *H*. Let's consider several following cases:
     16 
     17 * If a high person fits into height *H*, we leave him as is.
     18 * If a high person doesn't fit into height *H*, the we have to ask him to lie down, increasing the counter of such people by 1.
     19 * If a wide person fits into height *H*, but doesn't fit lying on the ground, then we leave him staying.
     20 * If a wide person fits into height *H* in both ways, then we first ask him to stay and write into a separate array value of answer decrease if we ask him to lie on the ground: *w* - *h*.
     21 * If somebody doesn't fit in both ways, then such value of *H* is impossible.
     22 
     23 Now we have several people that have to lie on the ground (from second case) and if there are too many of them (more than *n* / 2) then such value of *H* is impossible.
     24 
     25 After we put down people from second case there can still be some vacant ground positions, we distribute them to the people from fourth case with highest values of *w* - *h*. Then we calculate the total area of the photo and relax the answer.
     26 
     27 # [524C - The Art of Dealing with ATM](/contest/524/problem/C "VK Cup 2015 - Round 1")
     28 
     29 Intended solution has the complexity ![](https://espresso.codeforces.com/b8323556f48760eb97cdcd57ebbf2337bc4bdf88.png) or ![](https://espresso.codeforces.com/f72a0cba7f2043a3979207ac40dbe6342839ff25.png). For each possible value *x* that we can get write a pair (*x*, *m*) where *m* is number of bills to achieve this value. Sort this array in ascending order of *x* and leave only the best possible number of bills for each value of *x*. Then to answer a query we should iterate over the first summand in resulting sum and look for the remainder using binary search. The alternate way is the method of two pointers for looking in an array for a pair of numbers with a given sum that works in amortized *O*(1) time. Check that we used no more than *k* bills totally and relax the answer if needed.
     30 
     31 # [524D - Social Network](/contest/524/problem/D "VK Cup 2015 - Round 1")
     32 
     33 Let's follow greedily in following way. Iterate over all requests in a chronological order. Let's try to associate each query to the new person. Of course we can't always do that: when there are already *M* active users on a site, we should associate this request with some existing person. Now we need to choose, who it will be.
     34 
     35 Let's show that the best way is to associate a request with the most recently active person. Indeed, such "critical" state can be represented as a vector consisting of *M* numbers that are times since the last request for each of the active people in descending order. If we are currently in the state (*a*1, *a*2, ..., *a**M*), then we can move to the one of the *M* new states (*a*1, *a*2, ..., *a**M* - 1, 0), (*a*1, *a*2, ..., *a**M* - 2, *a**M*, 0), ... , (*a*2, *a*3, ..., *a**M*, 0) depending on who we will associate the new request with. We can see that the first vector is component-wise larger then other ones, so it is better than other states (since the largest number in some component of vector means that this person will probably disappear earlier giving us more freedom in further operations).
     36 
     37 So, all we have to do is to simulate the process keeping all active people in some data structure with times of their last activity. As a such structure one can use anything implementing the priority queue interface (priority_queue, set, segment tree or anything else). Complexity of such solution is ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png).
     38 
     39 # [524E - Rooks and Rectangles](/contest/524/problem/E "VK Cup 2015 - Round 1")
     40 
     41 Let's understand what does it mean that some cell isn't attacked by any rook. It means that there exists row and column of the rectangle without rooks on them. It's hard to check this condition, so it is a good idea to check the opposite for it. We just shown that the rectangle is good if on of the two conditions holds: there should be a rook in each row of it or there should be a rook in each column.
     42 
     43 We can check those conditions separately. How can we check that for a set of rectangles there is a point in each row? This can be done by sweeping vertical line from left to right. Suppose we are standing in the right side of a rectangle located in rows from *a* to *b* with the left side in a column *y*. Then if you denote as *last*[*i*] the position of the last rook appeared in a row number *i*, the criteria for a rectangle looks like ![](https://espresso.codeforces.com/7eebb15026e46fa483efab0202b62510bd2a3385.png). That means that we can keep the values *last*[*i*] in a segment tree and answer for all rectangles in logarithmic-time. Similarly for columns. This solution answers all queries in off-line in time *O*((*q* + *k*)*log*(*n* + *m*)).
     44 
     45 # [524F - And Yet Another Bracket Sequence](/contest/524/problem/F "VK Cup 2015 - Round 1")
     46 
     47 The main idea is that the bracket sequence can be seen as a sequence of prefix balances, i. e sequence (*a**i*) such that *a**i* + 1 = *a**i* ± 1.
     48 
     49 Calculate the number of opening brackets *A* and closing brackets *B* in original string. It is true that if *A* >  = *B* then the string can be fixed by adding *A* - *B* closing brackets at the end and shifting the resulting string to the point of balance minimum, and if *A* ≤ *B*, then the string can be similarly fixed by adding *B* - *A* opening brackets to the beginning and then properly shifting the whole string. It's obvious that it is impossible to fix the string by using the less number of brackets. So we know the value of the answer, now we need to figure out how it looks like.
     50 
     51 Suppose that we first circularly shift and only then add brackets. Suppose that we add *x* closing brackets. Consider the following two facts:
     52 
     53 * If it is possible to fix a string by adding closing bracket to some *x* positions then it is possible to fix it by adding *x* closing brackets to the end of the string.
     54 * From all strings obtained from a give one by adding closing brackets to *x* positions, the minimum is one that obtained by putting *x* closing brackets to the end.
     55 
     56 Each of those statements is easy to prove. They give us the fact that in the optimal answer we put closing brackets at the end of the string (after rotating the initial string). So we have to consider the set of the original string circular shifts such that they transform to the correct bracket sequence by adding *x* = *A* - *B* closing brackets to the end and choose the lexicographically least among them. Comparing circular shifts of the string is the problem that can be solved by a suffix array. The other way is to find lexicographical minimum among them by using hashing and binary search to compare two circular shifts.
     57 
     58 The case when *A* ≤ *B* is similar except that opening brackets should be put into the beginning of the string.
     59 
     60 So, overall complexity is ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png).