Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | Petr | 3353 |

2 | fateice | 3306 |

3 | Syloviaely | 3274 |

4 | tourist | 3235 |

5 | OO0OOO00O0OOO0O0…O | 3181 |

6 | Um_nik | 3158 |

7 | V--o_o--V | 3148 |

8 | dotorya | 3145 |

9 | LHiC | 3115 |

10 | mnbvmar | 3096 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 168 |

3 | Petr | 158 |

4 | csacademy | 157 |

5 | lewin | 150 |

5 | Swistakk | 150 |

7 | Errichto | 140 |

8 | ko_osaga | 139 |

8 | matthew99 | 139 |

10 | adamant | 138 |

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

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2018 21:33:59 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

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

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 ?

Tried to find bugs of your solutions but made some mistakes. Sorry for that :(

I got AC in the same way, Here is my solution: http://codeforces.com/contest/967/submission/37739371

but I can't prove it, can someone gives me a proof?

In 967B — Watering System, if we are sorting the holes, shouldn't the complexity be

O(n*log(n)).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 beO(n).Got it. Thanks.

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

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 ofx, 0-indexed. (You can also consider P(x) is the length ofx(binary representation) minus 1). Formally, ifxis in the range [2^{k}, 2^{k + 1}), thenP(x) =k. For example,P(5) = 2, since the leading bit of 5(101b) denotes 2^{2}.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, supposex= 13, thenF(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

a_{1},a_{2},a_{3}, ...a_{k}meeting the strictly increasing condition and the current xor sum iss. We are going to append a numberxto the sequence, making a new xor sum . In which condition, the sequence after appendingxis 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, ifx= 5 = 101b, to make sequence increasing, the 2^{2}bit of s should be 0. Ifs= 1101b, the 2^{2}bit is 1, then after xor x, the 2^{2}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 numberxin allnnumbers which meets the conditionF(s,P(x)) = 0. Then append the numberxto sequence and updates. 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 numbersx_{1}= 101bandx2 = 1 to select. P(x_1)=2, P(x_2)=0. So we should select 1. Why?Because if we first select

x_{2}= 1 (the one with lessP(x)), it will not modify the most significant bit ofx_{1}ins, in other words,F(s,P(x_{1})) will be change by the operation . So that we can appendx_{1}after appendingx_{2}.Otherwise, if

x_{1}is selected first,swill become , then we can't appendx_{2}.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

thanks a lot for sharing this :)