codeforces-scrape

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

266.md (5166B)


      1 Source: https://codeforces.com/blog/entry/6499
      2 
      3 [266A - Stones on the Table](/contest/266/problem/A "Codeforces Round 163 (Div. 2)")
      4 
      5 In this problem you should count number of consecutive pairs of equal letters. It can be done using one cycle and *O*(*N*) time.
      6 
      7 [266B - Queue at the School](/contest/266/problem/B "Codeforces Round 163 (Div. 2)")
      8 
      9 In this you should realize the given process. You should *t* times swap elements *i* and *i* + 1 if on the place *i* was a girl and on the place *i* + 1 was a boy. You should not push some girl to the left multiple times at once. The solution can be written using *O*(*N*·*T*) time.
     10 
     11 [266C - Below the Diagonal](/contest/266/problem/C "Codeforces Round 163 (Div. 2)")
     12 
     13 This problem can be solved using constructive algorithm. We will use inductive approach. At first, we have matrix of size *n* and *n* - 1 ones in it. Therefore, there is a column with no ones in it. So, we put this column to *n*-th place. In this case, the lower right element will be 0. Then find any row with at least one integer one and put it to the *n*-th place.
     14 
     15 After these operations the element in cell (*n*, *n*) equals to 0 and the last row has at least one integer one. Therefore, we can reduce the dimension of our problem, that is *n*:  = *n* - 1. In our new problem we have no more than *n* - 2 ones. So, we can solve this problem using the same algorithm. When *n* equals to 1 you should finish algorithm, because there is no ones left. This algorithm uses *O*(*N*) swap operations, no more than two for every *n*.
     16 
     17 [266D - BerDonalds](/contest/266/problem/D "Codeforces Round 163 (Div. 2)")
     18 
     19 I'll tell a few ideas how to solve this problem. Firstly, describe the solution with time *O*(*N*4). Consider every edge (*u*, *v*) of length *len* where could be the answer point. Let this point lie at a distance *x* from vertex *u*. So, the distance from this point to vertex *i* would be *min*(*x* + *d*[*u*][*i*], *len*–*x* + *d*[*v*][*i*]), where *d*[*x*][*y*] — distance between vertices *x* and *y*. Equate these values and get the critical value *x* for vertex *i*, *x* = (*len* + *d*[*v*][*i*]–*d*[*u*][*i*]) / 2. It follows that the answer to the problem is half-integer. So, for every edge and every other vertex we get set of critical points. We should check them all include the vertices of the graph (ends of the segments). This solution may probably pass with some optimizations.
     20 
     21 Another solution with complexity *O*(*N*3·*log*2). Multiply all weights by 2. Consider every edge where should be the answer and make binary search for the answer (in integers). To check some current value you should consider every vertex *i* and assume that the answer is achieved in this vertex. In this case, the answer point must lie on this edge <= some value *l*[*i*] or >= some value *r*[*i*]. This subproblem is solved using offline algorithm using sorting events and maintaining the balance.
     22 
     23 Also, you can use ternary search on every edge of the graph. But you should divide every edge on several segments and find the answer on every segment, because the ternary search is incorrect in this problem.
     24 
     25 The last two solutions can provide accepted, if you realize them carefully. Also note, that there is the solution with complexity *O*(*N*3) by the author [RAD](/profile/RAD "International Master RAD").
     26 
     27 [266E - More Queries to Array...](/contest/266/problem/E "Codeforces Round 163 (Div. 2)")
     28 
     29 This problem can be solved using data structure. We would use segment tree, we will support *k* segment trees for every power. At every vertex we will calculate weighted sum of the appropriate power, also we will save some number that indicates the color of the whole segment, if any.
     30 
     31 User [Egor](/profile/Egor "International Grandmaster Egor") in comments to the post and user [mexmans](/profile/mexmans "Candidate Master mexmans") in comments to the tutorial tell their formula to get the answer. I try to describe how to get them by yourself. Firstly, you should write what value your segment tree gives. The tree can calculate the sum ![](https://espresso.codeforces.com/a5b58e8b23c7841d1d63b86cb9dff69967de47a9.png). You need to calculate the sum ![](https://espresso.codeforces.com/c643f7f8655fd5b92fece5daa272e472e6c8f830.png), you can write it also as ![](https://espresso.codeforces.com/6328f7eee132b5640555cc7d5315c4a3b3a21417.png). Then you should write the last sum for some first powers (at least three) (at piece of paper) and subtract the second sum (what you need) from the first sum (what your tree can calculate). You get an expression that describes what should be subtracted to get the answer from the value what you tree can calculate. This is just the Newton binomial without the highest power.
     32 
     33 So, the answer for power *j* is expressed as the subtraction of the value of query to your segment tree and the Newton binomial, with all powers that are less than *j* (these values can also calculated using your segment tree). Partial sum of the powers and binomial coefficients can be precalced. The solution has the complexity *O*(*N*·*K*·*log*(*N*)).