codeforces-scrape

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

333.md (7617B)


      1 Source: https://codeforces.com/blog/entry/8418
      2 
      3 [334A - Candy Bags](/contest/334/problem/A "Codeforces Round 194 (Div. 2)")
      4 
      5 In this problem one must divide all natural numbers from 1 to *n*2 to groups size of *n* with the same sums.
      6 
      7 Lets divide all this numbers to pairs ![](https://espresso.codeforces.com/5f0b6b6f65fadfd885c927767b74b2b8b5d5e800.png). We can to do it since *n* is even and therefore *n*2 is even too. Then we can just make *n* groups consists of ![](https://espresso.codeforces.com/4ea28aaba551d7b5beb0ab75bf818d9a52485ee1.png) of these pairs.
      8 
      9 [334B - Eight Point Sets](/contest/334/problem/B "Codeforces Round 194 (Div. 2)")
     10 
     11 In this problem you must to do only what's written — you must to define does this set of points sutisfies to decribed conditions.
     12 
     13 There are many ways to define it. For instance:
     14 
     15 1. Check if there are exactly 3 discinct *x*'s and *y*'s. One can put all *x*'s to set and then get it size to find amount of distinct *x*'s (as well as *y*'s). Then print ``ugly'' if this amount isn't equals to 3.
     16 2. Finally we have *x*1, *x*2 и *x*3 as well as *y*1, *y*2 и *y*3. Now lets check if for every pair (*x**i*, *y**j*) (except (*x*2, *y*2)) such point exist in given set of points.
     17 
     18 But I think that to read editoral of this problem is not good idea. It is better to just look at the implementation.
     19 
     20 [334C - Secrets](/contest/334/problem/C "Codeforces Round 194 (Div. 2)") / [333A - Secrets](/contest/333/problem/A "Codeforces Round 194 (Div. 1)")
     21 
     22 Actually we are looking for longest sequence of natural number *a*1, *a*2, ..., *a**k*, so that every number in it sequence is the power of three, sum of all numbers is more then *n* and if we remove any number sum will be less then *n*. To be precise we are looking for length of this sequence.
     23 
     24 Consider minimal number *a**i* = *A* in the sequence. All this numbers are divides to *A* since them all are powers of 3. And then, sum *S* of all this number is divides to *A* too. Suppose that *n* is divide to *A* too. Then, since *S* > *n*, then *S* - *A* ≥ *n*. And then if we remove *A* from sequence, sum of other number not less then *n* — contradist with second condition.
     25 
     26 Well, we now that *n* is not divide to none element in sequence. Now lets find minimal *k* so that ![](https://espresso.codeforces.com/d1947ed3d55920511f16461c94f23557b0db4c75.png), and answer is ![](https://espresso.codeforces.com/1a70a560eaaff99531b0e64894685e8fc59a40a1.png).
     27 
     28 [334D - Chips](/contest/334/problem/D "Codeforces Round 194 (Div. 2)") / [333B - Chips](/contest/333/problem/B "Codeforces Round 194 (Div. 1)")
     29 
     30 At first lets make two remarks:
     31 
     32 1. On every (vertical of horizontal) line we can put only one chip.
     33 2. If there is at least one forbidden cell on the line then we can't put chip on this line.
     34 
     35 Follow last remark we will avoid hits chip on forbidden cells. Lets avoid ``collisions'' of chips.
     36 
     37 Lets consider these four line: vertical lines number *i* and *n* + 1 - *i* and horizontal lines with the same numbers. Chips on these lines can collides together, but con't collides to another chip. Therefore we can solve the problem for these four line independently. And finally lets observe that we can put the chip on each of these lines without cillisions as well as on the picture.
     38 
     39 ![ ](/predownloaded/28/34/2834caca67a96477e870b0280e893ec9fff6afec.jpg)
     40 
     41 So, we can iterate all possible fours and put chip on every possible line. And don't fogot about case of two middle line in case of *n* is odd.
     42 
     43 [334E - Lucky Tickets](/contest/334/problem/E "Codeforces Round 194 (Div. 2)") / [333C - Lucky Tickets](/contest/333/problem/C "Codeforces Round 194 (Div. 1)")
     44 
     45 In this problem we can find the right amount of lucky tickets.
     46 
     47 Lets consider amount of different numbers we can get from one four-digit ticket number. It is easy to iterate all this tickets, since it amount only 104. It happened that we can get almost 60 numbers from ticket on the average.
     48 
     49 Suppose we can get number *x* from ticket *n*. It is clearly that either *x* - *k* ≥ 0 or *k* - *x* ≥ 0. If *k* - *x* ≥ 0 we can write eight-digit ticket number who will have *k* - *x* in the first four digits and *n* in the last four digits. It is clearly that such ticket is *k*-lucky. This method allows us to get almost 600 000 lucky tickets and it is enough.
     50 
     51 [333D - Characteristics of Rectangles](/contest/333/problem/D "Codeforces Round 194 (Div. 1)")
     52 
     53 In this problem we must to find maximal value of minimum of values on four intersections of two rows and two columns of table.
     54 
     55 In another words, we are looking for maximum value of *min*(*a**i*1, *j*1, *a**i*1, *j*2, *a**i*2, *j*1, *a**i*2, *j*2) for all *i*1, *i*2, *j*1, *j*2 such that 1 ≤ *i*1, *i*2 ≤ *n*, 1 ≤ *j*1, *j*2 ≤ *m*, *i*1 ≠ *i*2, *j*1 ≠ *j*2. Lets us binary search of the answer. For us it we must can define is there two rows and two colums with ones on all four its intersections; in other words, integers *i*1, *i*2, *j*1, *j*2 so that *a**i*1, *j*1 = *a**i*1, *j*2 = *a**i*2, *j*1 = *a**i*2, *j*2 = 1.
     56 
     57 Lets consider all pair of natural numbers (*i*1, *i*2) so that there exist nutural number *j* so that *a**i*1, *j* = *a**i*2, *j* = 1. Existence of two equals such pairs is equals to existence of above four numbers. But it is can be only ![](https://espresso.codeforces.com/02131ef812b8bba0d2666b46e129b3b04787d841.png) such pairs. Therefore we can make the array where we will mark pair who were meets. Lets iterate all pairs in any order until we meet repeated pair or pairs are ends. So we have solution of time ![](https://espresso.codeforces.com/d0aa31e71a0ffc1693c98e862a289510d01c69f5.png).
     58 
     59 [333E - Summer Earnings](/contest/333/problem/E "Codeforces Round 194 (Div. 1)")
     60 
     61 In this problem it is need to draw three circle equals together with maximum possible radius with centers in given points. In another words it is need to find triangle wich minimum side is maximal.
     62 
     63 Unfortunately solution with bit optimize is not expected for us.
     64 
     65 Lets call to memory two simple geometric facts. Firstly, sum of alnges of trianle is equals to ![](https://espresso.codeforces.com/1c3cae67283d1071ec1f2ce60e06353b280fadb4.png). Secondly, minimal angle is opposit to minimal side of triangle.
     66 
     67 Since, at leats one side of angles of triangle not less then ![](https://espresso.codeforces.com/4593add39953064c1c18aa7c891fc412f061bede.png) and this anlge is not least one. And side opposite to it is not least side. Therefore, if in ![](https://espresso.codeforces.com/29330ac23972c3ef4ca3605987f3266218f36cc2.png) ![](https://espresso.codeforces.com/07af4cd9733ab8f202e4aa6f9dcc017c17378c15.png) then *min*(|*AB*|, |*BC*|, |*CA*|) = *min*(|*AB*|, |*BC*|).
     68 
     69 And then lets do the follows. Lets iterate apex *B* and for each *B* lets find triangle with maximal minimum of sides when *B* is the apex of triangle and ![](https://espresso.codeforces.com/93b00154c9c5da34eaf1e9e700e9665f7a46aee5.png). For it lets sort all other points by the angle relative to *B*, and for each point *A* lets find point *C* most distant to *B* among such points that ![](https://espresso.codeforces.com/07af4cd9733ab8f202e4aa6f9dcc017c17378c15.png). We have to use segment tree for maximum and two pointers or binary searsh to now left and right bound of possible points *C* during iterating *A*.
     70 
     71 Finally, we have solution of time ![](https://espresso.codeforces.com/d0aa31e71a0ffc1693c98e862a289510d01c69f5.png).