rng_58's blog

AtCoder Regular Contest 105 Announcement
By rng_58, history, 4 years ago, In English

We will hold AtCoder Regular Contest 105. From this contest, you don't need to choose the option "(with ACL)" to submit solutions with ACL. (The library is installed by default.)

The point values will be 200-300-500-600-700-900.

We are looking forward to your participation!

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

Comments Comments (60)
| Write comment?
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Notice the unusual start time. Starts one and half later than the usual start time.

Also thanks for integrating ACL library to avoid compilation errors. :)

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

Will there be any plan to retrofit old contests to add ACL option?

When solving some old problems, I had to use expander.py.

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

    Now you can use ACL by default in old contests too.

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

Why is this special starting time?

If it's an hour earlier as usual then I can participate....

I really want to participate in arc&agc but this time it's too late...

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

    It's good that they are experimenting with different time. Good for other timezones. Why should asians have all the fun? :P Though still this time is good for Asia.

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

      But codeforces seldom have a good time for asians....

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

    I guess it is because of GP (thanks!).

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

    Why do you care time if you live in Antarctica?

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

    I have the same problem. As a junior high student,I have to get back to my dormitory before 22:30,which means that I can participate in the contest for at most one hour.

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

how to solve c?????

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

    Solution for C:

    First find for each subset of camels the minimum separation they should have in order not to break any bridge part --> Complexity O(M*2^N)

    Now iterate over all permutations of camels and for each one build an optimal separation

    To do this we iterate over all subsequences of camels in the permutation and push the last one in order for the total separation to be as computed above --> Complexity O(2^N)

    Answer is minimum over all permutation of the separation between first and last camel.

    Total Complexity O(M*2^N + N!2^N)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

AGC (AtCoder Game Contest)

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

Can i know C & D conceptional difficulty according to codeforces ?
And how to solve C & D ??

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Can you help me B

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

      GCD of all the numbers

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -24 Vote: I do not like it

        Yes,if input is (2,4,7) ans the 5 but the GCD =1??

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

          please make sure you understand the problem before asking question.

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

        Can u plz expalin the intution behind it .I am not able that why it is working to just take gcd of all nos in problem B.

        Thnx

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

          Everytime we take onr pair of no and reduce it

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

            It will be helpful if u elaborate a bit. Ur this reply cannot help . Thnx

            → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it
      Simple & easy code just using set
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Doesn't this TLE ? what's the time complexity ?

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

        This code should not have passed
        It just shows that the problem had weak tests

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

        This will obviously get tle for simple case:

        2

        1 1000000000

        You can improve this by adding another binary search to find the max limit upto which you can decrease current largest number.

        Spoiler
        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    For C, try out all possible permutations of the Camels. Construct a DAG where two Camels a and b are connected if the contiguous segment from a to b would make a part of the bridge collapse if they're all in that part. The weight of this edge is the length of the longest such part. Then just find the max distance from 0 to n on this DAG.

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

How to solve D?

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

    Second wins iff n % 2 == 1 or quantity of each element is even.

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

    if n is odd, the second player will always win.

    if n is even, the second player only win if the frequency for each number in A[i] is even

    example : A = {2 2 4 4 9 9 1 1} then the second player will win.

    example : B = {2 2 4 4 9 9 1 2} then the first player will win.

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

    Solution for D:

    if n is odd the second player can always win. (think of it this way: in the last move the second player makes he has enough degrees of freedom in order to make it impossible for the first player to get xor 0 with his last move)

    if n is even there are two case:

    if every number appears an even number of time in the array the second player has a winning strategy which is to always copy what the first player did in his move (You'll see that after each move of the second player XOR of created sequence is 0)

    Otherwise the first player can win by the same logic used in the case where n is odd

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

      Thank you for the solution. Can you please explain "in the last move the second player makes he has enough degrees of freedom in order to make it impossible for the first player to get xor 0 with his last move". How should second player play in order to have "enough degree of freedom"? In editorial they do propose a strategy (seems some sort of heavy light trick) but I did't fully understand it. Can you please elaborate it perhaps?

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

        In the editorial the strategy is to always take the maximum available bag and put it in the biggest dish and this way he'll guarantee to have more than half the coins in one bag and in that case you can't get a XOR of zero.

        During the contest I didn't came up with that strategy but intuitively I thought that adding and XOR are very independent so if the numbers are random there should be no strategy to always get xor of 0. This doesn't prove anything but just encouraged me to try the solution I described.

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

          Thank you for the reply, I understand your intuition now but can you tell me why does following this strategy "take the maximum available bag and put it in the biggest dish" guarantee to have more than half the coins in one bag? It feels right but not able to wrap my head around it (how to prove as in or any simple intuition/induction)?

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

            Assume you're the one who's starting (i.e. strategy when n is even)

            Each time you take the maximum available coins and put them in one bag. If your bags are sorted in decreasing order a1, a2, a3, ..., a2n; You'll get a1, a3, ..., a2n-1 in one dish and it is easy to see that the sum of all the other are less than it since a2 <= a1, a4 <= a3, ..., a2n <= a2n-1

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

Editorial is already posted here.

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

How to get rid of TLE in C. I keep getting TLE in C. my complexity is O((n-2)!*n*n*m) ~ 4*10^9. Here is my submission. How should I optimize my solution?

I fixed the first and the last camel by taking 2 highest weights and getting every permutation possible for the rest of n-2. For every permutation, I assign x coordinate to ith camels by traversing from ith to 1st camel and getting a hold on every m conditions. Can I optimize this approach?

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

    Yes, you don't need to check every condition every time. Only $$$O(2^N)$$$ constraints are ever actually relevant.

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

      Can you explain it in more detail?

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

        For each subset of camels you only care about the maximum length of a bridge they can't go on.

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

    4*(10^9) definitely not good enough for 2 seconds.

    for each permutation you can find the minimum distance between every camel in O(N^2 log M) with loops and binary search

    total complexity is about O(N! N^2 log M)

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

for B ,if input is (2,4,7) ans the 5 but the GCD =1??

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

    $$$2,\space 4,\space 7\space \implies\space 4, \space 5 \space \implies \space 1$$$

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

Naive approach for B gave AC for me.

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

    If test cases contain 2 1 10^9 the solution will be TLE

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

      Yes, you are right. Can you please explain why exactly this type of small test cases are giving TLE?

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +77 Vote: I do not like it

F has a trivial $$$\Theta(n^2 2^n)$$$ solution under the view of "set power series".

Let's call $$$E(S) (S\subseteq V)$$$ be the edges of the induced subgraph of the given graph $$$G = (V, E)$$$.

Let $$$f_S$$$ be the number of the coloring of $$$S$$$ and a subset of $$$E' \subseteq E(S)$$$ satisfying $$$\forall (u,v)\in E', color(u) \neq color(v)$$$. We can see that

$$$ f_S = \sum_{T\subseteq S} 2^{E(S)-E(T)-E(S\backslash T)} $$$

hence

$$$ \sum_S 2^{-E(S)}f_S x^S = \left(\sum_T 2^{-E(T)} x^T\right)^2 $$$

and the answer is just

$$$ \frac 12\ln\left( \sum_S f_S x^S \right) $$$
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +196 Vote: I do not like it

    I have noticed that "trivial" can mean anything.

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

    What's the definition of logarithm of 'set power series'? Is it a function

    $$$g(x)=\sum_{S} g_{S} x^{S}$$$

    , such that

    $$$f(x) = \sum_{S} (\sum_{\mathcal{P}} \prod_{P_i \in \mathcal{P}} g_{P_i}) x^{S}$$$

    where the inner summation goes over all partitions

    $$$\mathcal{P}$$$ of $$$S$$$

    ? Did I, perhaps, miss some division by some factorial?

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

      Yes. There is no factorial. Because a partition is not ordered.

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

    This is very cool (but definitely nontrivial!).

    For anyone (like me when I first read this comment) who does not know how to implement the operations in $$$O(N^22^N)$$$ (the subset-convolution and the logarithm): think of the standard xor-convolution (via Walsh-Hadamard transform) applied independently on the entries with a fixed number of bits.

    More precisely, to compute the subset-convolution between $$$f$$$ and $$$g$$$ (both are functions on the subsets of $$$\{0,1,\dots, n-1\}$$$), one splits $$$f$$$ as $$$f_0+f_1+\cdots+f_n$$$ where $$$f_i(S)=f(S)$$$ if and only if $$$|S|=i$$$ (and otherwise $$$f_i(S)=0$$$) and computes the Walsh-Hadamard transform of $$$f_0,f_1,\dots,f_n$$$. Then, it is not hard to check that the subset-convolution can be obtained easily if one has the xor-convolution between $$$f_i$$$ and $$$g_j$$$ for all $$$i+j\le n$$$.

    I am not sure this is the standard way to compute the subset-convolution. If there is a more clever way, I would like to know.

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

    This is so fucking cool, wow.

    Do you know any other problems(on some online judge) that can be solved using this stuff? Especially if they require finding exp or square root of "set power series"?

    UPD: After reading your solution and Lu Kaifeng's report it seems that the ranked Möbius transform is much more powerful than "Fourier meets Möbius" suggests: looks like you can apply any function to the set power series by applying it to a "ranked" vector for each mask independently. At the very least it works for subset convolution and logarithm so it would be very surprising if this doesn't hold in general.

    But what is this witchcraft??? Why does it work?

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

Can someone please explain time complexity of https://atcoder.jp/contests/arc105/submissions/17342664? Shouldn't it be TLE with case $$$n = 2$$$, $$$a = [1, 1e9]$$$? Edit — Another user mentioned this above

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

In Task B, it is said that, "Under the constraints in this problem, it can be proved that the procedure will eventually terminate."

Can someone tell me how to find the number of operations?? Especially, for cases where the gcd of the input array is 1.

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

    I think to find the number of operations we need to brute force. Once the smallest number in the array is 1 it is trivial as each number a[i] will be decremented a[i]-1 times.

    But if the smallest number is bigger than 1 we need to try and count all other numbers.

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

There is a fast way to simulate problem B in O(N*logN*log(maxA))). It's gotta be somehow equivalent to finding the GCD, but that's beside the point. I wasn't going to implement it, but when I viewed the editorial saying it can't be simulated, I implemented it and it ACd. I was also super wasteful as you'll see.

Code:

Explanation: let min be the minimum, which element will be the first to create a new minimum?
It's an element x s.t. x mod min is largest! that's because until all elements in the array are < 2*min, no element can create a new min. As long as there are elements with value >= 2*min, one of them will be chosen.
how do we reach the point that for all i, min <= a[i] < 2*min?
Stage 1: simply iterate over the array and set a[i] = a[i]%min + min; now, either all elements are the same, or the next operation will lower the minimum.
Stage 2: Sort the array from greater to smaller while maintaining the current minimum, and simulate the operation (reduce current minimum from each item).

Complexity: why is it nlog^2(n)? (it's probably less tbh)
I'll prove that after performing one iteration of the above algorithm (Stage 1 + 2), the minimum of the array is at least cut by half. At stage 2, max is a[0] and min is a[n-1]. We iterate from 0 to n-1, doing a[i]-=cur_min. If when we reach a[n-1], cur_min <= min/2, we are done. Otherwise, cur_min > min/2, and then a[n-1]-cur_min < min/2 definitely hold, because a[n-1] is min.

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

    Can u elaborate how minimum is cut by at least half?

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

      When the array is already sorted, and you perform the subtractions, there are two options that may happen when you reach the original minimum, which is at index n-1.

      If when reaching it, new_min is already <= original_min/2, then the overall minimum is already cut in half, agree?
      For example, if the sorted array is [11,9,9,8], then right before reaching 8 it becomes [3,6,6,8]. the new minimum is already 3, which is <= 4=8/2.

      If when reaching it, new_min > original_min/2, then after performing original_min — new_min, it must be cut in half. Look at the equation "new_min > orig_min/2", subtract orig_min from both sides to get "new_min-orig_min > -orig_min/2" now multiply by -1 and get "orig_min-new_min < orig_min/2".
      For example, if the sorted array is [14,13,13,8], then right before reaching 8 it becomes [6,5,5,8], and the new_min=5>4. now, after performing orig_min-new_min=8-5, the new_min will be 3 <= 4.

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

E — Keep Graph Disconnected Editorial Why the answer of 1 6 1 1 2 is “First” ? Thanks a lot.

→ Reply