codeforces-scrape

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

460.md (9937B)


      1 Source: https://codeforces.com/blog/entry/13465
      2 
      3 [460A - Vasya and Socks](/contest/460/problem/A "Codeforces Round 262 (Div. 2)")
      4 
      5 At this problem you need to model what written in statements. Also, it can be proved, that answer can be calculated using formula: ![](https://espresso.codeforces.com/a8f8243f9be188cbbd61eaa352b7529dea104906.png) , where ⌊ *x*⌋ is the integer part of *x*.
      6 
      7 [7536107](/contest/460/submission/7536107 "Submission 7536107 by vitux")
      8 
      9 [460B - Little Dima and Equation](/contest/460/problem/B "Codeforces Round 262 (Div. 2)")
     10 
     11 Obviously *S*(*x*) can take only integer values and 1 ≤ *S*(*x*) ≤ 81. Let's check *S*(*x*) from 1 to 81, and calculate *B* * *S*(*x*)*A* + *C*. After that if sum of digits of this number is equal to *S*(*x*), it is positive and less than 109, than it is a solution.
     12 
     13 There could be bug because of using C++ pow() function.
     14 
     15 [7536153](/contest/460/submission/7536153 "Submission 7536153 by vitux")
     16 
     17 [460C - Present](/contest/460/problem/C "Codeforces Round 262 (Div. 2)")
     18 
     19 Note,that answer is positive integer not greater than 109 + 105. Using binary search on answer, we will find answer. Really, we can check in *O*(*n*) if some height is achievable. We go from left to right. For current flower we calculate how much times it need to be watered to stand not lower than checking value. If cuurent flower need to be watered for *h* times, we will star *h* segments in current flower. We would keep array, in which *st*[*i*] — number of segments, which starts in *i*-th flower. Also, we will keep variable, in which we will keep number of segments, which cover current flower. This variable could be updated at *O*(1). Really, to get new value we just need to subtract *st*[*i*  -  *w*], and, if we create new segments, to add *st*[*i*]
     20 
     21 Also, it can be proved that simple greedy algorithm works. At every of *m* iterations we can find the leftmost flower with the smallest height and water the segment, which begins in it. Primitive realisation works at *O*(*nm*), so you need to use data structure, which can add on segment and find minimum at segment. For example, you can use segment tree with lazy updation or sqrt-decomposition. Such solutions works longer, but faster than TL
     22 
     23 Prove: Consider any optimal sequence of moves (using which max. answer reachs). Consider initially the leftmost smallest flower, and suppose all segments which covers it.(suppose, there are at least 1 segment, because else answer is initial height of this flower, so we can put a segment to start in this flower, and answer would not change). Suppose that there are no segments, which starts from current flower. Consider the rightests of segments.(If there are more than one, than any of them). Than, we can move this segment to start in the initially leftmost smallest flower, and the answer would not change. Really, flowers, which earlier was at this segments were higher, than leftmost smallest, and were watered not least times. So, after we moved the answer had not decreased. So, new sequence is also optimal. So, there is sequence of moves, which consists the segment, which starts at the initially leftmost smallest flower. So, let use this. Similary to other of *m* days, and it would be optimally. [7536171](/contest/460/submission/7536171 "Submission 7536171 by vitux")
     24 
     25 [460D - Little Victor and Set](/contest/460/problem/D "Codeforces Round 262 (Div. 2)")
     26 
     27 If *r* - *l* ≤ 4 we can all subsets of size not greater than *k*. Else, if *k* = 1, obviously that answer is *l*. If *k* = 2, answer is 1, because *xor* of numbers 2*x* and 2*x* + 1 equls 1. If *k* ≥ 4 answer is 0 because *xor* of to pairs with *xor* 1 is 0.
     28 
     29 If *k* = 3, we can choose numbers 2*x* and 2*x* + 1 with *xor* 1. So we need to know, if we can get *xor* equals 0. Suppose that there are 3 such numbers *x*, *y* and *z* (*r* ≥ *x* > *y* > *z* ≥ *l*) with *xor* equals 0. Consider the most non-zero bit of number *x*. At the same bit of *y* it's also 1, because *xor* equls 0, and *y* > *z*. Consider the next bit of numbers. If *z* have 0 there, we have to do next: set the previous bit of numbers *x* and *y* equals 0, and set current bit equals 1. Obviously *xor* still equals 0, *z* hadn't changed and numbers *x* and *y* stood closer to *z*, so they are still at [*l*, *r*].And *x* > *y*.Consider the next bit of numbers. If *z* has zero here than we will change most bits of *x* и *y* at the same way and so on. *z* > 0, so somewhen we will get to bit in which *z* has 1. Since *xor* equals 0, the same bit of *x* would be 1 because *x* > *y*, and *y* would have 0 there. At the next bits we will change bit in *x* to 0, and in numbers *y* and *z* to 1.Finally *z* would be greater or equal than before, and *x* would be less or greater than before, and *x* > *y* > *z* would be correct. So, we have the next: if such numbers *x*, *y* and *z* exist than also exist numbers:
     30 
     31 1100…000
     32 
     33 1011…111
     34 
     35 0111…111
     36 
     37 with *xor* equals 0. There are not much such triples, so we can check them.
     38 
     39 [7536186](/contest/460/submission/7536186 "Submission 7536186 by vitux")
     40 
     41 [460E - Roland and Rose](/contest/460/problem/E "Codeforces Round 262 (Div. 2)")
     42 
     43 Formal statement: 2 natural numbers are given: *R* — radii, and *N* — number of points. You have to choose *N* unnesessarily distinct points *A*1, *A*2, ...*A**N* which are lying inside or on side of circle, such that
     44 
     45 ![](https://espresso.codeforces.com/768124dab62bb038e7c81134b63823b10557d62f.png)
     46 
     47 takes its maximal value.
     48 
     49 At first let ![](https://espresso.codeforces.com/f859ff9067d614be925fd3da2c9605ce05e6b58e.png) be a vector from (0, 0) to point *A**i*. Value of ![](https://espresso.codeforces.com/768124dab62bb038e7c81134b63823b10557d62f.png) is equal ![](https://espresso.codeforces.com/f7a56dbec1318fb99fa13c8b6af30aa60230329f.png), what is equal to ![](https://espresso.codeforces.com/f585c751e8cf232e3e18b3080f2a4a1b02d74251.png), and it can be rewritten as ![](https://espresso.codeforces.com/9db0de240175d9a6c750f896e486b34ab979f417.png). It makes us think that it is more profitable take point which are close to circle, such that |*a**i*2| would be as big as can, but value of ![](https://espresso.codeforces.com/97303b85054f0be5496a7eecd95ce19f424ec38e.png) as little as can. After that it becomes obvious, that if *N* is even, than it's enough to take any diameter and place half of points to the start and another half to the finish of it. Now we're trying to formulate our guessians strictly. Let's take an optimal set of points. Let's mark coordinats as (*x*1, *y*1), (*x*2, *y*2), ..., (*x**n*, *y**n*).Let's first *N* - 1 points are fixed, and we can move last point — (*x*, *y*). In terms of *x*, *y* we'd like to maximize
     50 
     51 ![](https://espresso.codeforces.com/4cb10e3efa4641e10113c3c2c76f1b708a8b3492.png)
     52 
     53 We left out all squares without *x*, *y*. Maximization of this *x*, *y* function is equivalent to maximization of
     54 
     55 ![](https://espresso.codeforces.com/65209de14dea23e81e4ffb642be39acaa330706c.png) ![](https://espresso.codeforces.com/f3ae87e58c4e76c720f946a1ff18a9139f46b185.png) ![](https://espresso.codeforces.com/871b09996cd3dd6ac196b9c7a66ad69f3e116234.png)
     56 
     57 So, we've reduced our problem to finding the furthest integer point from ![](https://espresso.codeforces.com/2658512b4d0f770f9b405419f7cff8bf815290fa.png). Now we can declare: the furthest point is placed at one vertex of convex hull of all integer points inside the circle.
     58 
     59 Proof. Let ![](https://espresso.codeforces.com/2658512b4d0f770f9b405419f7cff8bf815290fa.png) be a point *T*, and the furthest integer point inside *P* (convex hull) is *X*(obviously, it placed somewhere in convex hull). Lets extend *TX* beyond *X* to intersection with one side of polygon — let it be *AB*, and lets mark point of intersection as *X*'. Clearly *TX*' ≥ *TX*. It's easy to see, that one of angles ![](https://espresso.codeforces.com/fae758dc9c2bad3e2c3fad5a32060fedb8c4b75c.png) and ![](https://espresso.codeforces.com/26606a7b208c8b5085177a8445d0a6796330e8ed.png) is obtuse, so, according to properties of obtuse triangles on of inequalities holds: *TA* ≥ *TX*' ≥ *TX* or *TB* ≥ *TX*' ≥ *TX*, so, we can replace *X* to *A* or *B*, and distanse *TX* will increase.
     60 
     61 So, we can assume, that every point in optimal set belongs to the convex hull. So, solution is check all sets of points from convex hull and check values on this sets. If *R* ≤ 30, then convex hull contains no more than 36 points — it's easy to check with computer. So, brute force will take ![](https://espresso.codeforces.com/07574622c986939c2bef222c6312e0fa1064b6da.png) time, and it passes TL easily (depending on realizations and optimizations).
     62 
     63 For those, who interested in realization of algorithm: at first we place convex hull to some vector(and points become ordered). After that we build recursion function with the next parameters:1) how many points in the set on this iteration 2) vector with points 3) sum *x*-coordinats of points from set 4) sum of squares of *x*- coordinates 5) sum of *y*-coordinates 6) sum of squares of *y*-coordinates.
     64 
     65 On each iteration we take last point from set, and trying to add all points, starting with this, and finishing on the end of convex hull — it starts new iteration of recursion. Also, we recalculate meaning of cur value in fast way using parameters 3, 4, 5 and 6.
     66 
     67 On the last iteration, when we took *N* points, we are comparing value on this set with maximal value. If maximal value is less, than cur value, then *maxvalue* = *curvalue*, and *bestvector* = *cursetofpoints*. After recursion we output *maxvalue* and *bestvector*.
     68 
     69 [7536206](/contest/460/submission/7536206 "Submission 7536206 by vitux")
     70 
     71 **UPD** Editorial of problem C was expanded