atcoder_official's blog

AtCoder Beginner Contest 308 Announcement
By atcoder_official, history, 18 months 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 (43)
| Write comment?
»
18 months ago, # |
  Vote: I like it +108 Vote: I do not like it

is this account legit? maroonrk

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

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

→ Reply
»
18 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Can C be solved by using modulo inverse?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    C is simple sorting ,why do you need modular inverse?

    → Reply
»
18 months ago, # |
  Vote: I like it +19 Vote: I do not like it

You can use trie to do G right?

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

    just simple set will do the trick.

    → Reply
  • »
    »
    18 months ago, # ^ |
      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
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No, using multiset.

    → Reply
  • »
    »
    18 months ago, # ^ |
      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
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Curious to know your approach. Can you explain it?

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          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
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok explain then, my tiny brain can't comprehend dynamic connectivity

          → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
        ← 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
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
          ← 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
          • »
            »
            »
            »
            »
            »
            18 months ago, # ^ |
              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
  • »
    »
    18 months ago, # ^ |
    ← 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
  • »
    »
    18 months ago, # ^ |
    ← 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
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          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
»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Hints for E,F,G please :)

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

Can anyone explain the DP soln for F?

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

    I did Greedy + bs

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

      what you were looking for with bs? How do you retrive the max discount availble for a given price? I am doing lower bound on coupons looking for the closest one (with threshold just below the price and max discount) but its not working

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

      My bad, I meant E, didn't notice it until now and was wondering how did bs came into play T-T

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

        well the dp function will be like this dp(pos,current subsequence size, mask) — size : dp[200000][3][8] , although I didn't do dp during contest ; did brute force

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

          Can you please help me out with the recursive function.

          This is my submission from the contest. I know this is wrong since I am not calculating the dp till the i'th index , but I just couldn't find a way to do it properly.

          → Reply
»
18 months ago, # |
  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
»
18 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
18 months ago, # |
  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
»
18 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Why E requires DP, but F only requires greedy?

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

    I did F : Greedy + Bs and doing dp in E is overkill , E is just brute force

    → Reply
»
18 months ago, # |
  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
  • »
    »
    18 months ago, # ^ |
      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
»
18 months ago, # |
  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
  • »
    »
    18 months ago, # ^ |
      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