codeforces-scrape

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

231.md (7056B)


      1 Source: https://codeforces.com/blog/entry/5486
      2 
      3 [231A - Team](/contest/231/problem/A "Codeforces Round 143 (Div. 2)")
      4 
      5 It is needed just to implement actions described in statement. You had to read data and to calculate number of members of team, which were sure about the solution, for every task. If this number is greater than one, the answer must be increased by one.
      6 
      7 [231B - Magic, Wizardry and Wonders](/contest/231/problem/B "Codeforces Round 143 (Div. 2)")
      8 
      9 Let's see, what will be the last number of array after *i* iterations. After the first iteration it will be *a**n* - 1–*a**n* (and total number of elements will be decreased by one). After the second iteration the last number will be *a**n* - 2–*a**n* - 1 + *a**n*. It is not hard to see, that after *n* - 1 iterations remain *a*1–*a*2 + *a*3–*a*4 + ... + ( - 1)*n* + 1·*a**n*. In a such way, our task is to put numbers from 1 to *l* in array so, that sum of numbers in odd positions minus sum of numbers in even positions will equal to given *d*. This means sum of numbers in odd positions must be equal ![](https://espresso.codeforces.com/c52d2beca32f773c159cc652170671932186d715.png). But the minimal sum can be ![](https://espresso.codeforces.com/134337e86251c81b8d5bea0749afa8813627ab50.png), and the maximal — ![](https://espresso.codeforces.com/8d68f3dfd461b73904b8a0f10317bc65687a1a14.png).
     10 
     11 Because of this we should choose *a*2·*k* so, that *s* fits the boundaries. Constrains allow to do it in a such manner. Firstly, put ones on the even positions. If *s* > *maxv* after that, the answer is  - 1. Otherwise, let's increase each *a*2·*k* by one until *s* = *minv*. If we put *l* in all even positions and *s* < *minv*, than answer is  - 1 too. After we put numbers on even positions, let's write 1 in all odd positions, and while sum of this elements is less than *s* increase each one by fitting value.
     12 
     13 [231C - To Add or Not to Add](/contest/231/problem/C "Codeforces Round 143 (Div. 2)")
     14 
     15 One of the main observations, needed to solve this problem, is that the second number in answer always coincides with someone *a**j*. Let's see why it is true. Suppose, the second number of the answer is *a**j* + *d* for someone *j* and *a**j* + *d* ≠ *a**i* for all *i*. This means, we increased some numbers, which is less than *a**j*, so that they became equal to *a**j*, and then all this numbers and some numbers, which is equal to *a**j*, we increased to *a**j* + *d*. But if we didn't increase all this numbers to *a**j* + *d* and remain they equal to *a**j*, we'd perform less operations and the answer would be better.
     16 
     17 Due to this fact we can solve problem in a such manner. Sort array in non-decreasing order. Iterate over *a**i* and calculate, what is the maximal number of *a**i* we can obtain. For maximizing first number of answer, we must increase some lesser numbers to *a**i* and perform not greater than *k* operations. It is obvious that firstly we should increase such *a**j* that *a**i*–*a**j* is minimal. So, if we can solve problem in *O*(*n*2), we would iterate *j* from *i* to 0 and increase *a**j* to *a**i*, while we could. But the solution must be faster, and we will use binary search. We will brute the number of numbers, which we must do equal to *a**i*. Suppose we fix *cnt* this value. Now we have to check if we can do *cnt* numbers equal to *a**i* by not greater than *k* operations. For doing this, let’s calculate ![](https://espresso.codeforces.com/272539ca9f3d0303f9307df0f5668c98b0c3c93f.png). If this value not greater than *k*, we can do it. For calculating sum quickly, we can save prefix sums and than *s**i* - *cnt* + 1, *i* = *s**i*–*s**i*–*cnt*. Finally we solved this problem in *O*(*n*·*logn*).
     18 
     19 [231D - Magic Box](/contest/231/problem/D "Codeforces Round 143 (Div. 2)")
     20 
     21 The main subtask of this problem is to check whether we can observe the center of face of parallelepiped from point *p* = (*x*, *y*, *z*). Let’s see the case, when the face belongs to plane *z* = *z*1. For performing all calculations in integer numbers, multiply all coordinates *x*, *y*, *z*, *x*1, *y*1, *z*1 by 2. Take the point ![](https://espresso.codeforces.com/1a43d340fb2b13759775f3d5d385e9c4051cd3cd.png) and normal to plane, containing the fixed face, which is directed out of interior of parallelepiped, that is ![](https://espresso.codeforces.com/6ee0e34ea41fab9eced9646a67305e16bc28fed9.png). Also take vector ![](https://espresso.codeforces.com/530770842bae0062c0778b4eedd7bf4ca0a5eb71.png). If undirected angle between this vectors is less than 90 degrees, we can observe *a* from *p*. For checking this we can use scalar product. If scalar product of ![](https://espresso.codeforces.com/a767d7d8f7dbd42b197dfac092d904539b2c51fd.png) and ![](https://espresso.codeforces.com/f2c528db1bc08d0c4ac88bf5527c7bc5ffd2db7c.png) is strictly greater than zero, than that angle is fitting.
     22 
     23 [231E - Cactus](/contest/231/problem/E "Codeforces Round 143 (Div. 2)")
     24 
     25 In this problem you should find the number of simple paths between some pair of vertices in vertex cactus. If you learn the structure of these graphs, it is not hard to see, that if we’ll squeeze each cycle in one vertex, we get a tree. So let’s squeeze all cycles in source graph and get this tree. Also every vertex of this tree we’ll mark, if it is squeezed cycle (let’s call this vertices *1-vertices*) or single vertex in source graph (this vertices we’ll call *0-vertices*).
     26 
     27 Then, we’ll do the following to find the number of paths between vertices *a* and *b* in source graph. Suppose *c* is a vertex, corresponding to *a* in obtained tree (it can be a single vertex or a vertex, corresponding to a squeezed cycle with *a*), and *d* is a vertex, corresponding to *b*. Let’s denote *deg* is the number of 1-vertices in path from *c* to *d* in tree. Than it is easy to understand, that the answer for query is ![](https://espresso.codeforces.com/4af8baec2e4620302278788f35d8ca481cab04be.png), because every cycle (1-vertex) increase the number of possible ways twice (you can go from one vertex to other by two ways in cycle).
     28 
     29 It means that we need to count the number of 1-vertex on the path from one vertex to other in tree quickly to answer a query. We can do it in a following way. Hang our tree for one vertex, which we’ll call a root. Denote for every vertex *cnt**v* is the number of 1-vertex on the way to the root (including root and vertex itself). Suppose we want to find the number of 1-vertex on the path from *a* to *b*. Denote *c* is the least common ancestor of vertices *a* and *b*. Than number of 1-vertex on the way from *a* to *b* is equal to *cnt**a* + *cnt**b*–2·*cnt**c*, if *c* is 0-vertex and *cnt**a* + *cnt**b*–2·*cnt**c* + 1, if *c* is 1-vertex. The least common ancestor can be found by standard method — binary method recovery. Finally we have *O*(*m* + *k*·*logn*) solution.