codeforces-scrape

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

263.md (4595B)


      1 Source: https://codeforces.com/blog/entry/6419
      2 
      3 [263A - Beautiful Matrix](/contest/263/problem/A "Codeforces Round 161 (Div. 2)")
      4 
      5 If the single 1 is located on the intersection of the *r*-th row and the *c*-th column (1-based numeration), then the answer is |3 - *r*| + |3 - *c*|.
      6 
      7 [263B - Squares](/contest/263/problem/B "Codeforces Round 161 (Div. 2)")
      8 
      9 If *k* > *n*, then the answer doesn't exist. Otherwise let's sort the squares by descending of their sizes. Now you can print any point that belongs to the *k*-th square and doesn't belong to the *k* + 1-th square. One of the possible answers is (*a**k*, 0).
     10 
     11 [263C - Circle of Numbers](/contest/263/problem/C "Codeforces Round 161 (Div. 2)")
     12 
     13 First of all, we have to check that each number occurs in the input exactly 4 times. If it's not true, then the answer definitely doesn't exist.
     14 
     15 Otherwise, let's try to restore the circle. As cyclic shift of circle doesn't matter, let 1 to be the first number. As the second and the third number must be connected to each other and to 1, there are only few possibilities. So let's try them all. And when we know first three numbers, the rest of the circle could be easily and unambiguously restored in *O*(*n*). Just find a number, which is not included in the circle yet, and is connected to the last two numbers of the circle. Add this number to the resulting circle (as new last number), and repeat the procedure while possible. If we succeeded to add all the numbers to the circle, than the resulting circle is the answer.
     16 
     17 [263D - Cycle in Graph](/contest/263/problem/D "Codeforces Round 161 (Div. 2)")
     18 
     19 Consider any simple path *v*1, *v*2, ..., *v**r* which cannot be increased immediately (by adding a node to it's end, *v**r*). In other words, all the neighbours of *v**r* are already included in the path. Let's find the first node of the path (say, *v**l*), which is connected to *v**r*. It is clear that *v**l*, *v**l* + 1, ..., *v**r* is a cycle and it contains all the neighbours of *v**r*. But according to the problem's statement, each node has at least *k* neighbours. So length of the cycle is at least *k* + 1 ( + 1 is for node *v**r* itself).
     20 
     21 [263E - Rhombus](/contest/263/problem/E "Codeforces Round 161 (Div. 2)")
     22 
     23 Divide the rhombus of size *k* into 4 right-angled triangles as shown on a picture below. One of them has size *k*, two — size *k* - 1, and another one — size *k* - 2.
     24 
     25 ![ ](/predownloaded/6a/be/6abe6e1706a6179ad01d640186e867afbedef3c9.png)
     26 
     27 Let's solve the problem separately for each triangle. The most convenient way to do that is to rotate the input 4 times and run the same solving function 4 times. The result of this function will be a 2D array. Cell (*x*, *y*) indicates the answer we get if the right-angled vertex of triangle is located at cell (*x*, *y*). So it will be easy to combine 4 such arrays (just rotating and shifting properly) to get the actual answer for rhombus.
     28 
     29 The main idea of the solution for triangle is the following. If we know the answer for a cell, we can easily move our triangle by one cell in any direction (right, down, left, or up) and recalculate the answer for that new cell in constant time. In fact, we need only 2 directions: right and down. And the values for top left corner should be calculated with straightforward cycles in *O*(*k*2) time.
     30 
     31 ![ ](/predownloaded/98/a3/98a3175dfcae53cecf6ba55498139f1009ef2f21.png)
     32 
     33 More precisely, let's define 5 functions:
     34 
     35 1. The sum on diagonal segment of *k* elements: ![](https://espresso.codeforces.com/fcfc118cd2d4dc165e83d37c1caac18c121439b1.png)
     36 2. The sum on vertical segment of *k* elements: ![](https://espresso.codeforces.com/d422e536177590ee12da600f1b5cc4e6a8b6a0a6.png)
     37 3. The weighted sum on vertical segment of *k* elements: ![](https://espresso.codeforces.com/c37721a14cc0f9a837104266fd05b840f6958c82.png)
     38 4. The sum on a triangle: ![](https://espresso.codeforces.com/8dc3191219b43ea212af5966aa2da53b0f1a8d13.png)
     39 5. The weighted sum on a triangle: ![](https://espresso.codeforces.com/9b59e9a51df7eb1ccda96a4a12f0c16c72b411e9.png)
     40 
     41 Calculating the first 3 functions in *O*(*nm*) in total is quite obvious. Formulas for the others are following:
     42 
     43 *triangle*(*x*, *y* + 1) = *triangle*(*x*, *y*) - *diagonal*(*x*, *y* - *k* + 1) + *vertical*(*x*, *y* + 1)
     44 
     45 *triangleWeighted*(*x*, *y* + 1) = *triangleWeighted*(*x*, *y*) - *triangle*(*x*, *y*) + *verticalWeighted*(*x*, *y* + 1)
     46 
     47 Formulas for moving in other directions are similar.