atcoder_official's blog

AtCoder Beginner Contest 308 Announcement
By atcoder_official, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 308.

We are looking forward to your participation!

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

Comments Comments (44)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +108 Vote: I do not like it

is this account legit? maroonrk

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem were relatively easy this time especially F and G. Nice round.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

Can C be solved by using modulo inverse?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

You can use trie to do G right?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    just simple set will do the trick.

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

    It can be done with a multiset.I'm not sure how to do it with trie.

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

    No, using multiset.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    Yes, I solved it with divide and conquer + trie.

    At first I completely misunderstood the problem and started thinking in wrong direction, but still it is interesting approach I think.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Curious to know your approach. Can you explain it?

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        He probably used segment tree. You see, the problem would be trivial if the "remove" query was a "roll-back" query. So the idea is just the same as dynamic connectivity. The complexity is $$$O(N * log ^ 2 N)$$$, which is not too bad considering the time constraint is $$$3$$$ seconds

        → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        We notice, that writing $$$x$$$ on the blackboard and erasing $$$x$$$ from the blackboard means that $$$x$$$ is spanned on some segment of queries, so we can use similar trick that we use in offline dynamic connectivity.

        With a segment tree add $$$x$$$ on some range and when you traverse the segment tree recursively you want to do following:

        • Insert $$$x$$$ in a trie.
        • Find minimum $$$y$$$ $$$xor$$$ $$$x$$$.
        • Roll back all the inserted nodes from trie.

        All of this can be done in $$$O(N*log(N)*log(x))$$$

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it +8 Vote: I do not like it

          I have a better approach.

          Make each node of the trie, store the answer for the suffixes of all the numbers that are in its subset (sub-tree or sub-trie, whatever). The idea is something similar to the merge operations we do in segment trees. Every time we insert or delete a number, we update the answer for all the nodes that are affected by its insertion or deletion. This works in O(NlogN). Here is a link to my submission: link

          PS: But, it feels really silly to use a trie for this problem after reading the editorial.

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

            "PS: But, it feels really silly to use a trie for this problem after reading the editorial."

            Don't worry, it might be useful for other hard problems in future.

            → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    I did using a set, Code

    The main idea is that it suffices to check every adjacent elements in a sorted array to get the minimum Xor

    → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +19 Vote: I do not like it

    Yes, I solved it with dp on trie, using the fact that when we add/remove a number, at most 30 nodes need to recompute their dp value. Here is the code :)

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Can you elaborate a bit about dp state and you idea?

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it +8 Vote: I do not like it

        The problem asks to find two paths to leaves of the trie with minimum xor value. We compute the dp value for each node, assuming that both paths go through it. Answer is the value of the root.

        If a node has two possible paths when adding a 0 (or a 1), it’s never optimal to choose one path with 0 and the other one with 1.

        We are left with the case when there is only one path with 0 and one with 1. Given that each path the only one in its subtree, we can mantain the value of the number it represents and use it to compute the xor of the two possible paths (we can update this value when we add/remove numbers).

        Refer to my code for more details :)

        → Reply
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Hints for E,F,G please :)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone explain the DP soln for F?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Lmao, I finished F like 10 minutes after the contest was over and F took me less time than any of C-E.

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

In the editorial of G, shouldn't it say "more significant bits" instead of "less significant bits"

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Why E requires DP, but F only requires greedy?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc308/submissions/43142095 can anyone tell me whats problem here 4/39 case are failing i am not able to figure out problem wasted a hell lot of time in this done E late but haven't solved D

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    check line 10.

    Also dp is redundant, It does nothing here plus format your code. It's a headache to read.

    → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone please tell why I am getting runtime error on problem D. I have used simple DFS with dp, some pass but mostly give me Runtime error. https://atcoder.jp/contests/abc308/submissions/43178624

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    you are visiting the same nodes again and again

    it will give run time error for this case

    2 6

    sekunf

    nukesn

    first you will start at (1,1) you will reach (2,5) from there one dfs will be to (2,6) and another to (1,5)

    consider (1,5), you will again go to (1,1) but at(1,1) dp[1][1] will still be equal to -1 as the dfs from (1,1) is not completed fully so you will again start dfs from (1,1) and it goes on .

    → Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hello AtCoder,

Please stop blocking kenkoooo thanks. Or please add pages like My Submissions and Friends' Submissions on AtCoder. Thank you!

→ Reply