Endagorion's blog

By Endagorion, history, 4 weeks ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial of VK Cup 2018 - Round 3
 
 
 
 
  • Vote: I like it  
  • +83
  • Vote: I do not like it  

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

In the first line of the solution to Div1.D, does the word "formualate" mean "formulate"?

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

for div 1 C i chose greedily the minimum value with which we should xor so that we can find the next value in a which is greater than the previous value. I used trie with deletion. Here is the code . http://codeforces.com/contest/967/submission/37730673. Why doesnt it work ?

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

In 967B — Watering System, if we are sorting the holes, shouldn't the complexity be O(n * log(n)).

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Sure, it should be O(nlogn) were we using a comparison based sort. Here though, we can use a linear time sorting algorithm such as counting sort. The complexity in that case would be O(n).

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone explain div 2E ? Not able to understand from editorial.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, I think div2 E is really an instructive problem though I can't figure out the solution during content.

    First, Let's define some functions that can be used in my explanation.

    Let P(x) denote the position of leading bit of x, 0-indexed. (You can also consider P(x) is the length of x (binary representation) minus 1). Formally, if x is in the range [2k, 2k + 1), then P(x) = k. For example, P(5) = 2, since the leading bit of 5(101b) denotes 22.

    Let F(x, n) denote the nth least significant bit of x, 0-indexed, or, the nth bit from right in the binary representation of x. For example, suppose x = 13, then F(x, 0) = 1, F(x, 1) = 0, F(x, 2) = 1, F(x, 3) = 1, since 13 = 1101b.

    Note that F(x, P(x)) is always 1.

    Then, Let's consider a basic problem. Suppose we have a sequence a1, a2, a3, ...ak meeting the strictly increasing condition and the current xor sum is s. We are going to append a number x to the sequence, making a new xor sum . In which condition, the sequence after appending x is still strictly increasing, or, in other words, s' > s?

    The answer is easily to find. if and only if F(s, P(x)) = 0. For example, if x = 5 = 101b, to make sequence increasing, the 22 bit of s should be 0. If s = 1101b, the 22 bit is 1, then after xor x, the 22 bit will be set to 0, making the sequence decreasing.

    So we can get such a solution for div 2E. Initially, we consider the sequence is empty and s = 0, and select a number x in all n numbers which meets the condition F(s, P(x)) = 0. Then append the number x to sequence and update s. Repeat n times, the answer is got.

    However, when there are more than one number that is able to select, which one should be selected first? The answer is simple. Just select the one with least P(x).

    For example, if the current s = 1010b, and we have two numbers x1 = 101b and x2 = 1 to select. P(x_1)=2, P(x_2)=0. So we should select 1. Why?

    Because if we first select x2 = 1 (the one with less P(x)), it will not modify the most significant bit of x1 in s , in other words, F(s, P(x1)) will be change by the operation . So that we can append x1 after appending x2.

    Otherwise, if x1 is selected first, s will become , then we can't append x2.

    Last question, if there are more than one number that is able to select and has least P(x), which one should be selected first? The answer is that it doesn't matter. In that case, we can choose any one of them. Why? Remain for thinking.

    Here is my solution:37857270

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks a lot for sharing this :)