codeforces-scrape

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

165.md (3794B)


      1 Source: https://codeforces.com/blog/entry/4124
      2 
      3 [165A - Supercentral Point](/contest/165/problem/A "Codeforces Round 112 (Div. 2)")
      4 
      5 In this problem you should just code what was written in the problem. For every point you can check if it is supercentral. Consider every point consecutively and find neighbors from every side. The complexity is *O*(*N*2).
      6 
      7 [165B - Burning Midnight Oil](/contest/165/problem/B "Codeforces Round 112 (Div. 2)")
      8 
      9 This problem can be solved using binary search for the answer. obviously, if number *v* is an answer than every number *w* > *v* is also the answer, because the number of written lines of code could only become more. To check some number *v* you can use formula given in the problem, because it will have less than *O*(*logN*) positive elements. The complexity is *O*(*log*2(*N*)).
     10 
     11 [165C - Another Problem on Strings](/contest/165/problem/C "Codeforces Round 112 (Div. 2)")
     12 
     13 You was to find number of segments [*lf*;*rg*] of the strings on which the sum equals to *k* (we are working with array of integers 0 and 1). We will count array *sum* where the value *sum*[*i*] equals to sum on segment [0;*i*]. We will count the answer going from left to right. Let's say we are in position *pos*. Now we will add the number of segments on which the sum equals to *k* and ends in position *pos*. To do it we will count array *cnt* where *cnt*[*i*] — number of occurrences of *sum*[*i*]. Then in position *pos* we add *cnt*[*sum*[*pos*] - *k*] to the answer. The complexity is *O*(*N*).
     14 
     15 [165D - Beard Graph](/contest/165/problem/D "Codeforces Round 112 (Div. 2)")
     16 
     17 Beard-graph is a tree. It consists of one root and several paths from this root. There is a single path between every pair of vertices. That's why you should check whether every edge on the path between two vertices is black. If some edge is white there is no path between two vertices now.
     18 
     19 The distances could be found separately. For every vertex *v* precalc such information: index of path from the root where *v* is situated and *d*[*v*] distance between root and *v*. If you know such information you can find distance between any two vertices.
     20 
     21 To check whether every edge on the path between two vertices is black we will use segment tree. Mark black edge with value 0 and white with 1. Than repainting some edge — update in some point. The query — sum on some segment (the path between two vertices). If the sum equals to 0 there is a single path. Else the answer is -1 now. Complexity is *O*(*NlogN*).
     22 
     23 [165E - Compatible Numbers](/contest/165/problem/E "Codeforces Round 112 (Div. 2)")
     24 
     25 Consider some number *x* from the array. Inverse all bits in *x* and say it is number *y*. Consider an integer *a*[*i*] from array. It can be an answer to the number *x* if for every position of zero bit from *y* there is zero bit in *a*[*i*] in the same position. Other bits in *a*[*i*] we can change to ones.
     26 
     27 Then we will use such dynamic programming *z*[*mask*] = {0, 1} which means if we can change some zero bits to ones in some integer from given array *a* and get mask *mask*. Initial states are all integers from array *a* (*z*[*a*[*i*]] = 1). To go from one state to another we consider every bit in *mask* and try to change it to one. The length of bit representation of all integers in *a* is less or equal than 22.
     28 
     29 To answer the question YES or NO for some number *x* you need to get value [*z*(*y*)&(1«22) - 1] (inverse all bits in *x* and make the length of the number 22). If you want to know the exact answer what number *a*[*i*] you should choose you can save previous states for every state *z*[*mask*] or just save it in *z*[*mask*]. Complexity *O*(2*K* * *K*), where *K* – length of bit representation of numbers (*K* <  = 22).