Блог пользователя rng_58

Автор rng_58, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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. :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +195 Проголосовать: не нравится

    Why do you care time if you live in Antarctica?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve c?????

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

AGC (AtCoder Game Contest)

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -24 Проголосовать: не нравится

    Can you help me B

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      GCD of all the numbers

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится -24 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          please make sure you understand the problem before asking question.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Everytime we take onr pair of no and reduce it

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -14 Проголосовать: не нравится
      Simple & easy code just using set
      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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)?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Editorial is already posted here.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Naive approach for B gave AC for me.

Code
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +77 Проголосовать: не нравится

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) $$$
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +196 Проголосовать: не нравится

    I have noticed that "trivial" can mean anything.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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