When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

HolkinPV's blog

By HolkinPV, 12 years ago, translation, In English

165A - Supercentral Point

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(N2).

165B - Burning Midnight Oil

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(log2(N)).

165C - Another Problem on Strings

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).

165D - Beard Graph

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.

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.

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).

165E - Compatible Numbers

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.

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.

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(2K * K), where K – length of bit representation of numbers (K <  = 22).

  • Vote: I like it
  • +12
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm trying to solve problem D "Beard Graph". I understand the idea but i don't see how to use a segment/fenwick tree in this case. Probably my problem is on understanding what HolkinPV means by " index of path from the root where v is situated". Can anyone give me some help on this please?

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the idea behind this O(n) solution for problem C by Scott Wu: http://ideone.com/sysG1b Thanks.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually this solution is incorrect. It gives wrong answer even on test #1, anyway idea is quite simple. If for position i sum of 1's from position 0 to i is equal s and s >= k then you need to find number of positions with sum of 1's equal s-k (let's denote it as C[s-k]) and add it to the result. We will get full result after processing all positions.

    Instead of processing each position individually we can count the number of positions with sum of 1's equal to 1, 2, ... etc. and iterate over them. Then if we are processing some sum equal s we should add to the result value C[s]*C[s-k]. This solution will not work for k = 0. In this case we should add value (C[s]-1)*C[s]/2. Why? Because if we've got C[s] positions with sum equal to s then one of this position contains 1, so we need to find how many different sub strings we can get from C[s]-1 0's.

    Correct solution: 11487947

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please again the idea behind adding C[s]*C[s-k] to the result. This part is not clear to me.

      Why we are adding C[s-k] to the result ? What does it represent ?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I will try to explain my solution using the following example:

        2

        10100100010000

        First, let's calculate prefix sums of 1's. We get the following values:

        11222333344444

        Our C table looks like this:

        C[0] = 1

        C[1] = 2

        C[2] = 3

        C[3] = 4

        C[4] = 5

        Now we iterate over C table starting from i = 2 (which is our k) to 4 (which is maximum sum of 1's). Value C[i] is the count of positions which can be right end of our substring. Now we need to find the number of positions which can be left end of the substring. Number of such positions is C[i — k]. For example for i = 3 we get the following possible left and right end positions:

        1 0 1 0 0 1 0 0 0 1 0 0 0 0

        So for any i we've got C[i — k] (left ends) * C[i] (right ends) possible substrings with k 1's. Answer is the sum of such values for all i.

        Special case is k = 0. If I have for example C[2] = 3 it means that I have one position with 1 and two positions with 0s. So what I need to do now is to count number of all substrings of these two 0's. If Let's say I have n 0s, then I will have:

        n substrings of length 1 n — 1 substrings of length 2 n — 2 substrings of length 3 ... 1 substring of length n

        so generally the number of substrings of string of length n is sum of numbers from 1 to n which is n*(n+1)/2.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Wow! You explained it soo nicely! O:) Thanks..

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Very nice explanation!! I tried two pointer (sliding window) but no luck

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please Explain why is C[0] = 1 in your solution

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is needed for substrings which begin from the first character of the original string. C[0] = 1 means that I have one left end with 0 1's = the empty string. Of course if the original string begins with some 0's the value of the C[0] will be bigger.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain 165C — Another Problem on Strings. Unable to understand approach.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Problem -C . Not getting the approach

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider two different cases when k=0 and when k!=0; When k=0, it is simple to calculate the number of strings by storing the position of occurrence of '1' in a vector and then iterate over the string and calculate the answer.(try it yourself it is simple). When k!=0,let's assume dp[i] = number of strings ending at position i and containing k 1's. Make a vector which stores the position of occurrence of 1 and use to calculate the answer. try it yourself.

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

A lot of sources which got AC at problem D returns different answers on this input :

7 1 5 6 4 2 3 3 5 5 6 3 7 1 3 4 2

I think is a good idea to introduce this test-case as official test.

UPD : Three samples of codes which got AC : First Second Third

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain more detail problem E?thanks.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's suppose you have a number X and we invert the binary digits of X, now we have a number Y that has some 1s and some 0s, we want to find another number Z that has a 0 in every position where Y has a 0. It is important to note that every 0 in Y must strictly be a 0 in Z, but each 1 can be either a 1 or a 0 in Z.

    A naive solution would be for every number Y in the range [1-4*10^6] iterate over every number Z in the same range, and for every valid pair, check if that number exists in a, if it exists you found an answer for Y, otherwise it's -1. Then you can just iterate over a and look at the solutions you precalculated by inverting the bits of each a[i].

    Of course, this wouldn't work because it's too slow, time complexity would be O(2^2*maxBits) if you iterate over all numbers in the range [1-4*10^6], or O(3^maxBits) if you use bitwise operations to ignore invalid Zs. Both too slow, so we need to optimize it.

    We will take similar idea, but change it slightly, for every Y that has an answer we say that we can propagate the answer to another number W, if and only if Y&W=Y and W has exactly 1 more bit turned on compared to Y. This works because as we stated earlier, we want Z to have zeros where Y has zeros, but if Y has a 1, we don't care what we have in Z, and because W is the same as Y, except that one 0 is now a 1, we know that Z will still be valid. We code this idea with DP and it becomes O(maxBits*2^maxBits)

    http://www.codeforces.com/contest/165/submission/18102743

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      thanks for great explanation.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      The man who gave such great explanation didn't get any upvote(before I gave one), but the man who thanked him for his great explanation got 5 upvotes(now 6 including mine) !! Just wow !!!

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can't we solve E using bit trie? But the complexity is 2^23 i guess which is less than 10^7??

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I get the idea in problem D but i don't understand the segment tree part. Can anyone help me out with this part?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Worrst tutorial ever!No one couldn't understand any problem specially problem C.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read code of top rating, maybe it helps (at least for me) =))

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain Problem -B . Not getting the approach.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can use binary search as given in the editorial but i have another approach -->

    think of it as

    find min v, such that:-
    
    1) n <= v*(1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...)         
    consider this:-
    
    2) n <= v*(1 + 1/k + 1/k^2 + 1/k^3 + ...)
    
    lets just keep lhs aside for now, think about try to keep the rhs constant on going from eq 1 to eq 2.
    like:- 
    3) v1*(1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...) = v2*(1 + 1/k + 1/k^2 + 1/k^3 + ...)
    
    as we can easily find (1 + 1/k + 1/k^2 + 1/k^3 + ...) == (k)/(k-1) and we can see from eq 3 that v1 >= v2 as (1 + flr(1/k) + flr(1/k^2) + flr(1/k^3) ...) <= (1 + 1/k + 1/k^2 + 1/k^3 + ...)
    
    so we can find v2 very easily using v2 = n*(k-1)/(k)
    v2 is the lower limit for our ans (==v1)
    now just run a loop from v2, as soon as the sum becomes >= n, break and you have the answer
    

    please correct me if my logics wrong here is the code 83607371

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C using binary search ??

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just did, you can see my solution here — 87349681

    Here is my logic —

    Basically, we do a 2 pointer theorem approach, in that we find the sum of substring starting with index i with the help of binary search for all i (Maintain a prefix sum array, to easily calculate required sum in a given interval starting from i).

    When that sum is same as k, we take 'mid' element we have obtained via binary search (corresponding to the right end of the substring) and take the left and right extremities of adjacent elements having the same value as the 'mid' element in the prefix sum array (Notice that each pair of extremities would have a unique identifier as the values in prefix array are increasing).

    For better understanding, I would recommend you to see the solution