codeforces-scrape

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

425.md (6663B)


      1 Source: https://codeforces.com/blog/entry/11998
      2 
      3 ### [426A - Sereja and Mugs](/contest/426/problem/A "Codeforces Round 243 (Div. 2)")
      4 
      5 Lets count the sum of all elements *Sum* and value of the maximal element *M*. If *Sum* - *M* ≤ *S* then answer is yes, otherwise — no.
      6 
      7 ### [426B - Sereja and Mirroring](/contest/426/problem/B "Codeforces Round 243 (Div. 2)")
      8 
      9 Lets solve problem from another side. We will try to *cut* of matix as many times as we can. *Cut* means operation, reversed to operation described in statement. To check, can we cut matrix we need to check following conditions:  
     10 1). *n* *mod* 2 = 0  
     11 2). *a**i*, *j* = *a**n* - *i* + 1, *j* for all 1 ≤ *i* ≤ *n*, 1 ≤ *j* ≤ *m*.
     12 
     13 ### [425A - Sereja and Swaps](/contest/425/problem/A "Codeforces Round 243 (Div. 1)")
     14 
     15 Lets backtrack interval on which will contain maximal sum. To improve our sum we can swap not more then *k* minimal elements from the interval to *k* maximal elements that don't belong to interval. As *n* isn't big we can do it in any way. Author solution sort all elemets from interval in increasing order and all elements that don't belong to interval by descreasing order. We will swap elements one by one while we haven't done *k* swaps and we have some unswaped elements in first set and we have some unswaped elemets in second set and swap is optimal(we will optimize the answer after this swap). Author solution works in time *O*(*n*3·*log*(*n*)).
     16 
     17 Is there some ideas how to solve this problem in time *O*(*n*) or *O*(*n*·*log*(*n*)) ?
     18 
     19 ### [425B - Sereja and Table](/contest/425/problem/B "Codeforces Round 243 (Div. 1)")
     20 
     21 Note, that if we have two arrays *x*[1..*n*], 0 ≤ *x**i* ≤ 1 and *y*[1..*m*], 0 ≤ *y**i* ≤ 1, then described matrix can be showed as next one: *a**i*, *j* = *x**i* *xor* *y**j*.  
     22 If *n* ≤ *k*, then we can backtrack array *x* and using greedy find best *y*. Otherwise there will be atleast one *i*, such that we will not change any cell in row number *i*. So we can simply bruteforce some row and use it like *x*. Then we use greedy and find *y*. From all possible rows we choose most optimal. Such row will be as number of mistakes is lower then number of rows, so it isn't possible to have atleast one mistake in each row.
     23 
     24 Greedy means next algorithm: for every element of *y* we will look, will it be better to choose it like 0 or 1. To find better choise, we will count number of different bits in *x* and current(lets it be *j*) column. If number of different if lower then count of same cells we will set *y**j* = 0, otherwise *y**j* = 1.
     25 
     26 ### [425C - Sereja and Two Sequences](/contest/425/problem/C "Codeforces Round 243 (Div. 1)")
     27 
     28 In thgis problem we will use dynamic programming: *dp**i*, *j* — minimal pozition of deleted element in second array, such that we have made first operation *j* times and have deleted not more then *i* elements from first array.
     29 
     30 Lets decided how to calculate transfers. Standing in pozition *dp**i*, *j* we can change nothing and go to pozition *dp**i* + 1, *j*, by other words make transfer *dp**i* + 1, *j*:  = *min*(*dp**i* + 1, *j*, *dp**i*, *j*). What happens when we make first operation with fixed prefix(by *i*-th element) in first array? We should find element in second array with number greater *dp**i*, *j* and value equal to *a**i*, lets its pozition is *t*, so we need to make transfer *dp**i* + 1, *j* + 1:  = *min*(*dp**i* + 1, *j* + 1, *t*).
     31 
     32 How to find required element quickly: lets just do vector of pozition in second array for all different elements that contains in second array. Then we can simply use binary search.
     33 
     34 ### [425D - Sereja and Squares](/contest/425/problem/D "Codeforces Round 243 (Div. 1)")
     35 
     36 Lets line *x* = *k* contain not more then ![](https://espresso.codeforces.com/712f9a224d6c7824add37b6cd766c21f73a40d59.png) points. Then for each pair of points on this line (lets it be (*k*, *y*1) and (*k*, *y*2)) check: is there squere that contain them as vertexes. So we should check: is there(in input) pair of points (*k* - |*y*2 - *y*1|, *y*1) and (*k* - |*y*2 - *y*1|, *y*2), or pair (*k* + |*y*2 - *y*1|, *y*1) and (*k* + |*y*2 - *y*1|, *y*2).
     37 
     38 Lets delete all watched points, and reverse points about line *x* = *y*. Then each line *x* = *k* will contain not more then ![](https://espresso.codeforces.com/712f9a224d6c7824add37b6cd766c21f73a40d59.png) points. Will solve problem in the same way.
     39 
     40 Now we should learn: how to check is some pair of points(on one vertical line) in input. Lets write all of this pairs in vectors. Each vector(for every line) will contain pairs that we should check on it. Suppose, that we check it for line number *k*. Lets mark in some array *u* for all points with x-coordinate equal to *k* *u**y* = *k*. Now to check is our pair with y-coordinates (*y*1, *y*2) on line we can simply check following condition: *u**y*1 = *u**y*2 = *k*.
     41 
     42 ### [425E - Sereja and Sets](/contest/425/problem/E "Codeforces Round 243 (Div. 1)")
     43 
     44 First, lets look at *F*(*S*). First, we sort all intervals by second coordinte and then go by them in sorted order. And if current interval don't intersected with last taken to the optimal set, we get our current to the set.
     45 
     46 Our solution will be based on this greedy. Solution of the problem is next dynamic:  
     47 1). number of position of second coordinte of interval  
     48 2). number of intervals in good set  
     49 3). second coordinate of last taken interval to the optimal set
     50 
     51 How should we make transfers? Lets note that when we know *dp**i*, *count*, *last* we can change *last* by *i*, or not change at all. Lets look what happens in every case. In first case *last* is changed by *i*, so we should take to optimal set atleast one of the inervals: [*last* + 1, *i*], [*last* + 2, *i*], ..., [*i*, *i*], number of such intervals *i* - *last*, number of ways to get at least one of them is 2*i* - *last* - 1. All other intervals: [1, *i*], [2, *i*], ..., [*last*, *i*] we could get as we wish, so we have 2*last* ways. So total number of transfers from *dp**i*, *count*, *last* to *dp**i* + 1, *count* + 1, *i* is (2*i* - *last* - 1)·(2*last*). If we count number of transfers from *dp**i*, *count*, *last* to *dp**i* + 1, *count*, *last*, we can simply use number 2*last*(as described early).
     52 
     53 Also we shouldn't forget about trivial case *dp**i*, 0, 0.
     54 
     55 So now we have quite easy solution.