chokudai's blog

By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 134.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the approach for E . I gave it an hour but still not able to figure out

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

      i did exactly same link, but it gave me tle , but then later i changed used maps it gave AC. map link Do you know why ?

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

      Good article, learned a new thing. but why answer will be the size of longest decreasing subsequence.

      proof!

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

        It is not. It is the number of subsequences, not the length of the longest. Edit: The minimum number of...

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

          but what it mean

          "If we focus on the example we can see that the Minimum number of increasing subsequences equals to the length of longest decreasing subsequence where each element from the longest decreasing subsequence represents an increasing subsequence"

          it is written in g4g article.

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

            For better understanding, look for Dilworth's Theorem. it says that the size of a maximal antichain equals the size of a minimal chain cover of a partial ordered set

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

    Use multiset in C++ STL

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

      when considering Ai,if ther are such j that Aj<Ai(Aj is the last one in another array),choose the MAX Aj. if you don't you may waste smaller one ,smaller one is more useful than bigger one . to do this you can use multiset

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

    Iterate from a1 to an. For each element a_i color it with the color which has the largest last element smaller than a_i. If there isn't any, color it with a new color.

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

    Greedy works for E. Make another array, X.

    In step $$$1$$$, place $$$A_1$$$ in X. In step $$$i$$$, check if $$$X$$$ contains an element that is strictly less than $$$A_i$$$. If there exists such an element in $$$X$$$, replace the first such element in $$$X$$$ with $$$A_i$$$ else append $$$A_i$$$ to $$$X$$$.

    The answer will be the final size of $$$X$$$.

    Note that the array $$$X$$$ will always remain sorted and hence you can use binary search in each step, giving a final time complexity of $$$O(n \log n)$$$.

    You can visualise it as stacking number of discs on top of each other, the array $$$X$$$ contains only the top of each stack, the "representative" element. Each new stack corresponds to a new colour and we can add an element to a stack only if it is larger than every element in that stack. However since the representative element is the largest element of the stack you just need to check if the element to be added is larger than the representative element of the stack.

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

      can u post submission link.

      and can u tell why the answer will always be length of longest decreasing subsequence?

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

        Here's my submission.

        As for a proof of this, I couldn't come up with one which doesn't require Dilworth's Theorem or replicated a proof of Dilworth's Theorem.

        Consider the set

        $$$S = \{(A_i, i) | 1 \le i \le n\}.$$$

        Now for any $(A_j, j), (A_i, i) \in S$, we say $$$(A_i, i) < (A_j, j)$$$ if and only if $$$A_i < A_j$$$ and $$$i < j$$$. Then by Dilworth's Theorem on this partially ordered set, we get our result.

        For a longer explanation, our problem now becomes to find the minimal partition $$$S_1, S_2, \dots, S_r$$$ of $$$S$$$ such that for any $$$a, b \in S_i$$$ $$$a < b$$$. Such a partition is called a chain decomposition of $$$S$$$. Our aim is to find the size of the smallest chain decomposition of $$$S$$$. Dilworth's theorem states that the size of the smallest chain decompostion is equal to the size of the largest anti-chain. An antichain of a partially ordered set is a set of elements of the poset such that for any two element $$$a, b$$$ of the antichain neither $$$a < b$$$ or $$$b < a$$$. From our setup, an antichain would be a decreasing sequence and hence the longest antichain will be the longest decreasing sequence. Now it's not hard to prove that the above algorithm does indeed give the longest decreasing subsequence.

        You can read more about Dilworth's Theorem and partial orders here or on its wikipedia page.

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

        You can prove it by coloring each integer according to the length of the longest non-increasing subsequence ending at that integer. If $$$i < j$$$ and $$$A_i \geq A_j$$$, the longest non-increasing subsequence ending at $$$A_j$$$ is strictly longer than the longest ending at $$$A_i$$$.

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

    The problem gets reduced to finding longest non increasing sub-sequence of the given sequence. The reason being Dilworth's Theorem

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the answer to the D problem be -1. i.e when will we not have a good set of choices?

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

    Never

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

    Answer is never -1.

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

      can you explain your approach for D..(Preparing Box) I was thinking that the answer will be the same array which is given to us as input? Please correct me if I am wrong

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

        For indices greater than $$$n/2$$$, whether to put a ball or not is decided by $$$a[i]$$$ itself (because there are no more multiples of it less than $$$n$$$). For the remaining ones, run a loop from $$$n/2$$$ to $$$1$$$. Sum all the box-values of indices which are multiples of the current index. If the parity of the sum and a[i] are same, then we need not put any ball in that box. Else, we need to put a ball in the box.

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

          I did the same thing but I am getting WA for testcase_12,testcase_4 ,testcase_5,testcase_6 .

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

            Can I see your submission, please?

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

    The answer always exist.

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

    There is always a good set of choice.

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

      But how can we work it out? I've tryed 5 times but failed.

  • »
    »
    5 years ago, # ^ |
    Rev. 5   Vote: I like it +1 Vote: I do not like it

    Never.

    If $$$x_i$$$ is the number of balls in the box $$$i$$$. The problem is equivalent to finding equivalent to solving a system of $$$n$$$ linear equations in $$$x_1, x_2, \dots, x_n$$$ modulo $$$2$$$.

    The matrix of this sysetm of linear equation was upper triangular and all the diagonal elements were non-zero and hence it will always have a solution. The proof of this is the algorithm used to solve the problem. You can find $$$x_i$$$ by simply setting

    $$$\displaystyle x_i = a_i - \sum_{k = 2}^{ik \le n} x_{ik} \mod 2.$$$

    Then simply iterate from bottom to top, first find $$$x_n$$$, then $$$x_{n - 1}$$$, then $$$x_[n - 2}$$$ and so on... This is known as back substitution.

    The time complexity will be

    $$$\displaystyle O\left(\sum_{i = 1}^n \left\lfloor\frac{n}{i}\right\rfloor\right) \approx O\left(\sum_{i = 1}^n \frac{n}{i}\right) = O(n H_n) \approx O(n (1 + \ln n)) = O(n\log n)$$$
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For any with box you always have the option to make the total ball in its multiples odd or even depending on whether you fill the with box with ball or not. So answer can never be -1

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

What's the solution for F?

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

ABC like 15 minutes...then no idea at all. Gap from C to D much to big.

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

    and D to E ?

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

      idk, thats kind of out of my eysight ;) People solving D must tell.

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

        Well for me D was not that easier but doable as compared to E, I understood what to do in E but due to my shortage of knowledge in STLs, I couldn't implement E but I did D in contest.

        What I did was, I ran a first loop from n to 1 and then inside this loop I ran another loop from the last multiple of i nearest to n and then came to i. Something like

        for(int j=last_multiple;j>=i;j-=i)

        and then counted the multiples which are filled with ball or not if the count was of same parity with ith box I needed to do nothing but if the parity was different I needed to fill the ith box with a ball

        My solution to D

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

      i found E easier than D, possibly because E's solution came intuitively and i wrote buggy D

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        D was just a simple brute force.

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

          After like 15 minutes trying to understand the bony language I decided to work on E. After another like 30 minutes I found that I need to count the number of inc subsequences, but had absolutly no idea how to do it in time limit. So I switched back to D... but still was not able to see the simple implementation needs.

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

How to solve problem F?

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

F anyone? ?

»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

How to solve D please :)

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

    For D, you can start from N and go backwards till 1, at each stage check the parity of all multiples of the current number which are <=N, and accordingly set or don't set the bit for the current number depending on Ai.

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

      You mean check all the divisors of the current number...then I guess its complexity must be O(n*sqrt(n)) Please correct me if I am wrong

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

        Actually it's O (N log N), since the amount of iterations you have to do is $$$\sum_{i = 1}^{N} N / i = N \cdot \sum_{i = 1}^{N} 1 / i$$$, which is just N * Harmonic Sequence, which is O (N log N).

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

          Not sure if this is an amateur question, but how is the harmonic series = log N?

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

            I'm not sure if I'll be able to explain this clearly but I'll try.

            The Summation of elements of the Harmonic Sequence is: $$$S_1 = 1 / 1 + 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5 + 1 / 6 + 1 / 7 + 1 / 8 \dots + 1 / n$$$

            Suppose we generate another sequence bigger than the Harmonic Sequence by rounding the denominators down to their nearest power of 2. The summation of this sequence will be: $$$S_2 = 1 / 1 + 1 / 2 + 1 / 2 + 1 / 4 + 1 / 4 + 1 / 4 + 1 / 4 + 1 / 8 \dots + 1 / n$$$

            The value of $$$S_2$$$ is close to $$$\log_2 N$$$ since the amount of elements required to get to the next integer value doubles for every integer. Since $$$S_1 \leq S_2$$$, we conclude that $$$S_1$$$ is also close to $$$\log_2 N$$$.

            EDIT: I believe this is explained better on an Algorithms Live! video, but I can't recall which one.

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

              Understood, in fact that's a fairly standard proof, it's just that it's been a while since I've dealt with this kind of math so I had to jog my memory.

              Thank you!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to look at other's solutions at AtCoder?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I tried to solve F using DP but it only passed 30 test cases out of 50 other 20 gave TLE. Is there a solution to the problem which does not involve dp or what were the states of the dp which passed all the test cases?

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

    Could you tell me your DP solution please? I haven't any idea about it.

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

      Basically my dp had 3 states which were the current index, bitmask which stores the values already used and the third state was the sum which had already been created using the already used values. And then the transitions were pretty simple after that.

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Here's everything about Problem F: https://arxiv.org/pdf/1202.4765.pdf

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My code for problem C returns TLE for the second half of the test cases (probably longer inputs?), any advice to make it more efficient?

I only know the basics of C++, I have looked at a few of others' submissions, but they used vector lists. I know what they are but I haven't learnt how to use them in code yet, so I prefer something I could code & understand.

Thanks.

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

    All you need to do is find the largest and second largest numbers. The second largest number can be equal to the largest number. Thus if the current number is equal to the largest number, then print the second largest number; else, print the largest number.

    Here is my code: https://atcoder.jp/contests/abc134/submissions/6467493

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

https://pastebin.com/NLHwAzXC for problem d i did the same as the nomral solution but instead of looping trough all the multiples of i it loops through primes i and sum up prime * i and decide to put 1 or no but it givs wa

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

    just bcoz ur approach is wrong. why r u asking the wrong approach to be a correct.

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

      why its wrong

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

        why not to apply dp on seg tree problems. its wrong so its wrong . if u want correct one simply take all multiples of i. tc will be nlogn.

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

          taking primes only should do the same as taking multiplis

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Firstly, I taught that F can be solved using dp[i][j] — number of permutations using numbers from 1 to i having the permutation's depth j, but I figured out that is not enough. Can anybody explain the dynamic with 3 states?

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I tried problem E by applying LIS twice. But I keep getting wa. Any idea what's the problem?

Submission-wa

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

    Look at this 12 1 1 2 2 3 3 3 3 2 2 1 1 Answer:8 Output:9 Expect 8 find 9

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

Can anybody please explain the state of DP used to solve problem F.

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

    The editorial in japanese says that we should assume the problem as pairing task.
    The state of dynamic can be

    • i: i-th pair we are looking at (<=n)
    • j: number of pairs you skipped and kept unconnected (<=n)
    • k: determined oddness till i-th operation (<=n^2)

    then we can update the state like dp[i+1][j][k+j] = dp[i][j][k] in O(n^4).
    My code here https://atcoder.jp/contests/abc134/submissions/6504932

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

chokudai please write an editorial explaining F

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

chokudai Editorial please.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone please translate editorial for problem F in English?

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

If you find official editorial and AC submissions for F is so damn painful to look at, you can try to find out the idea in this editorial. Although it's in Japanese but it has an really intuitive example picture and you can use Google Translate to get the idea.

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

    thanks man.

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

    This one helps a lot, Thanks! it's so cool to reshape it into another equivalent solvable one. after the reshape, the transition of DP becomes comparatively clearer.

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

Could you tell me what the problem D actually ask to do? I couldn't understand the requirement. Thanks!