gepardo's blog

By gepardo, history, 4 days ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +79
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for the editorial ^^

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    Input
    Expected Output
    Your Output
    Comment
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank it was mistaken with which pointer(mo_left/mo_right), should we move first. Moved Mo_right first and then Mo_left for query, finally AC. Thanks

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

My O(max(n,q) * sqrt(n) * log(max(q,sqrt(n))) solution to E1

This solution works even when the segment asked in query is not a RBS. Note that log factor can be removed on using pointers and using prefix sum(for heavy chains).

»
4 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Can someone explain the Binary Spiders solutions.

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

    +. more detail if it's possible. cause I'm dealing with tries first time. and i watching about tries there. i got the gist of the idea. but here the process of finding the maximum subset for i in the trie is little bit complicated. thanks in advance

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

      let's give it a trie.
      this is my solution which is a little different than the one in the editorial.
      First, let's focus on the MSB of K and try to group the number based on bits starting from the MSB position to the end. for example, if we have K=00010101
      so we're interested in the prefix part till the first 1 bit, split k like that.
      0001 | 0101
      and we split numbers at the same position to height bits and lowest bits
      0110 | 1000
      0110 | 1001
      1010 | 1100
      1011 | 1010
      0001 | 1001
      0111 | 1000
      group numbers by the first part.

      observation-1 look at the left part (highest bits) if this part is equal then XOR will be zero and it's bad as it will make our XOR lower than K, so the max we can get from this group is only one element.
      observation-2 if the left part only differs at the lowest bit then we can get one element from each group, we just need to know that the XOR between these two elements is >=K and we can do this using trie (later I will explain how).
      observation-3 if the bits are different then it's guaranteed that it will produce a number greater than K.
      so getting to the Trie part, the trie is only needed in observation two, if we found two numbers have the same prefix and differ only in the first bit.
      so to check that we're checking two groups A, B and trying to find if we have any two pairs that have XOR >=k. put all the numbers in group A in a trie, our binary trie will have left as zero bit, right as 1 bit. now iterate over numbers in group B, for each number try to find the MAX XOR you can get, basically you iterate over the bits in this number from left to write and try to go to the opposite if possible.
      if the current bit is 1 then try to go to 0 in the trie (this will maximize the XOR value).
      hope this helped out.
      my submission for ref: https://codeforces.com/contest/1625/submission/142621030

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

Do anyone have the implementation of problem D, using the approach explained in the editorial?

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

Sorry for copying my previous comment from the round announcement page. Hello, can anyone point out the error in my code: 142652368 for problem B, it seems I'm calculating less than it's expected to be but I can't find an error. I'm using the same approach of finding the pair of equal elements whose distance is minimum. Any short testcase that yields wrong output for my code would be appreciated. Thank you.

  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected Output
    Your Output
    Comment
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot, I got that my approach to the third repetition of a number was incorrect. I modified my code (142746835) and it works against your testcase but it still fails on the exact same testcase as it did before.

»
4 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Please upload the codes also.

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

For C, I think "min(dp[n][j]) over all 0 <= j <= k" is not the final answer, because that is forcing the n-th sign to be taken (not removed). To get the final answer, we have to enumerate the last taken sign, add the remaining road section's time to each one, and finally take the minimum value among all of them.

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

    We are indexing from $$$0$$$ so element at at index $$$n$$$ is destination city (or simply it's $$$l$$$).

»
4 days ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

I think problem D memory limit should've been higher if bit-trie solutions were intended to be accepted. Fitting $$$O(n \log A)$$$ memory into 256 MiB is quite a challenge, especially for Java and Python

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

I was trying O(n^2) solution for Problem C by having additional DP state for propagating last selected speed limit. I am not looking for solution, but if someone can take a look and tell if this would work or not, that would help. Thanks.

142748551

  • »
    »
    3 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hey, I am also doing this only. But unable to figure out the mistake. Did you get to know why this will not work. Or anybody else can help us out! Please!! Thank you so much!

    My Code -> 142787581 (Similar to @i_will_be_expert's)

    PLEASE PLEASE, help us out!

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

I find E1 really hard for me.

»
4 days ago, # |
  Vote: I like it +24 Vote: I do not like it

On D

To solve the problem, we need the following well-known fact. Suppose we have a set of numbers and we need to find minimal possible xor over all the pairs. It is true that, if we sort the numbers in non-descending order, the answer will be equal to minimal xor over neighboring numbers.

Is it actually well known? Does anyone have a proof for why that is the case? Afaik the most common way to solve this problem is by making a bit trie.

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

    In bitwise xor, same bits give us 0, while different bits give us 1. If we try to find minimal xor pair, neighboring numbers have more of the same bits starting from the MSB, which makes the xor value smaller.

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

      Not always true.

      Consider 6 7 8, (7^8) is greater than (6^8).

      But still the overall minimum comes out as (6^7) which are still the neighboring elements. Its so confusing lol.

  • »
    »
    3 days ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    Let a,b and c be three numbers such that a<b<c. Let the first bit where a and c differ be the kth bit, then kth bit in a must be unset and it must be set in c. Then depending upon whether kth bit is set in b or not we get (b xor c) <(a xor c) or (b xor a) <(a xor c)

»
3 days ago, # |
  Vote: I like it +16 Vote: I do not like it

I think in E2,it is more natural for me to think up the $$$O((n+q)\log n)$$$ solution than the $$$O((n+q)\sqrt n)$$$ solution.

  • »
    »
    3 days ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    Another thing I've noticed, converting RBS to tree is pretty much the inverse operation of DFS/finding the Eulerian path of a tree. So instead of building the tree explicitly, I found it much more efficient to simply compute the statistics for each node/open bracket in place.

    142753393 link to my submission

»
3 days ago, # |
  Vote: I like it +15 Vote: I do not like it

E2 can still be solved if not only leaves are erased, but each pair must form a matching.

If we build the bracket tree, the erase operation can be transformed to erase a node and link all its sons to its father. The queries can be transformed to sum up $$$k*(k+1)/2$$$ for each node in the interval. We can use unionset to deal with father changes and a Fenwichtree to deal with subtree sum except the root. Degree of the root of each interval can be transformed to occurrences of minumum prefix sum in the interval. It can be maintained by segment tree.

Here is the code.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In question B, the answer seem to be n - min(v - u).

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why doesn't greedy algorithm work for problem C in which we remove the sign which causes a maximum decrease in time. If someone can provide a short test case which I can visualize that would be helpful. Here is my code 142511895

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C I ran a nested loop. Outer one from 0 to k-1 and inner from 1 to n-1(because we can't remove the first sign). I then checked that by removing which sign I will save maximum time and then adjusted the array accordingly for removing another sign. But this approach was not working. Can someone give me some test cases where it will not work?142507173

»
3 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Some hints for people stuck at debugging problems B and C.

Iizy Problem: B

Input
Expected Output
Your Output
Comment

i_will_be_expert nitigya Problem: C

Input
Expected Output
Your Output
Comment

umanggupta1975 Problem: C

Input
Expected Output
Your Output
Comment

HaidRam Problem: C

Input
Expected Output
Your Output
Comment
»
23 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.