chokudai's blog

AtCoder Beginner Contest 215 Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 215.

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

We are looking forward to your participation!

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

Comments Comments (42)
| Write comment?
»
3 years ago, # |
  Vote: I like it -31 Vote: I do not like it

i love atcoder math contest

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

In my opinion, there should be two 400 points problems and one 600 because it's an ABC contest.

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

    and IMO, the present renewed distribution is better.

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

How to solve G?

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

    Let $$$cnt_i$$$ be the number of candies with color $$$i$$$. Consider all $$$i$$$ such that $$$cnt_i>0$$$. There are $$$\binom{N-cnt_i}{K}$$$ ways to choose $$$K$$$ candies so that no chosen candy has color $$$i$$$. To choose $$$K$$$ candies, the sum of the number of different colors are $$$\sum_{i}\binom{N}{K}-\binom{N-cnt_i}{K}$$$. There are at most $$$O(\sqrt{N})$$$ different elements in $$$cnt$$$, because the sum of the elements in $$$cnt$$$ are $$$N$$$. For colors with the same $$$cnt$$$ values, we can deal with them together. We can preprocess factorials and the inverses of those in $$$O(N)$$$ time to calculate each binomial coefficient in $$$O(1)$$$ time. So we can solve this problem in $$$O(N\log{N}+N\sqrt{N})$$$ time, which is fast enough.

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

    Alternative solution:

    For a subset of candies $$$S$$$, let $$$w(S)$$$ be the polynomial where the coefficient of $$$x^k$$$ is the number of ways to select $$$k$$$ candies from $$$S$$$ (in this case, that's simply $$$\binom{|S|}{k}$$$) and $$$s(S)$$$ the polynomial where coefficient of $$$x^k$$$ is the sum of the number of distinct colors over all subsets of size $$$k$$$ in $$$S$$$. If $$$S$$$ only contains candies of a single color, then $$$s(S)$$$ is trivial to compute. Also, if the colors in $$$S$$$ are all different from the colors in $$$T$$$, $$$s(S \cup T)$$$ is simply $$$s(S)w(T) + w(S)s(T)$$$. So this gives an algorithm: start with the sets $$$S_c$$$ of candies with color $$$c$$$ and their polynomials and, while we have more than one set, pick two sets $$$S$$$ and $$$T$$$, compute the polynomials of $$$S \cup T$$$ and discard $$$S$$$ and $$$T$$$. If we proceed as in Huffman coding order, this runs in $$$O(N\log(N)^2)$$$.

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

Is there an alternate solution to E without DP ?

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

    I solved the problem using bitmask dp where the mask represents which letters are covered already UPD: The original comment asked for an alternative solution that does not use digit dp

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

I think today's contest was awesome, Thanks.

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

Lesson Learnt: Don't use log2(N) :( Thanks Atcoder!

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

    Did you figure out where does it fail? I also got WA initially with that.

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

      I checked (int)log2((1<<59)-1) and it gave me 59 (It should be 58)

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

        Thanks,any idea why does it happen?

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

          Probably a precision issue as it deals with doubles

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

        Someone might want to read this. I guess (1<<59)-1 just got rounded to $$$2^{59}$$$ as a double before computing the logarithm because $$$2^{59}-1$$$ can't be represented.

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

      After getting WA, I just went ahead by checking powers of 2 in order and got an AC :)

      log2(N) just got added to my list of functions not to use in CP, which includes ceil(), floor() and pow().

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

    You can use __lg instead.

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

The round was quite balanced. Approach for E:

Convert the string to an array of numbers where A = 1, B = 2... J = 10 Let Dp(i,j,k) = total number of combinations for the first i numbers if the last number picked was j and k is the numbers already used so far (ie the ith bit of k is on if the number i has been used). Then there are two options at the ith step:

  1. Pick current number(only possible if a[i]th bit in K is off(a[i] hasnt been picked yet) or the last number picked is a[i])
  2. Skip current number

Submission: https://atcoder.jp/contests/abc215/submissions/25284623

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

Please can you help me why am i getting runtime error on this: https://atcoder.jp/contests/abc215/submissions/25243897

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

As a writer, I tried to write very short statements in A-D, as you want!

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

    Thanks ! I enjoyed the round so much. Also I turned blue on atcoder :yay:

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

    Problem D is so tight. I got TLE by factorization using precomputed prime set. Is this intended?

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

How to Solve F ?? Can someone explain it ??

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

I have participated in 20+ ABC's and yet haven't solved E :(

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

Nice contest! Thanks!

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

How to solve D?

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

    Do prime factorization each elements but fast

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

In the editorial H "In the following editorials, we require the knowledge of Hall’s marriage theorem and Fast Zeta/Möbius transformation." -> I don't think it's a topic on ABC.

Atcoder should consider about difficulty for "Beginner"

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

Could someone explain how this gets WA on F? I couldn't really understand the tutorial. Thanks https://atcoder.jp/contests/abc215/submissions/25240944

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

In Today's D problem If i take lcm of all the array elements and then iterate from 1 to m and store all the elements such that gcd(lcm, i) == 1. Then why this approach is wrong can someone pls explain?

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

    The LCM might be very large and overflow, e.g. $$$lcm(99971, 99961, 99929, 99923, 99907) = 9969136729118531781864539$$$ will not fit a 64-bit integer.

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

[solved]

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

For task E,can anyone point out where this logic is wrong as it didn't even passed on sample testcases:

I make an array v out of the string where v[i]= number of times some character appeared in the input string. Size of v will always be <=10 (as per the conditions mentioned in the task)

Now I iterate over all possible subsets (total possible subsets= 2^(size of v)) of v . Say we are currently processing i-th subset of v and let's say that it has cnt number of elements in it.So I set my temporary_answer to fact[cnt] (since we can participate in cnt number of contests in that many order).

Now I multiply my temporary_answer by v[j] for all j such that j is an element of the current( i-th) subset (since we can choose to play 1...v[j] matches of j-th kind for all j). Then add this temporary_answer to my final answer. I keep doing this for all subsets ( and skip the case where the choosen subset is empty) and finally return the answer. Time complexity: N*(2^N) where (N<=10)

Please point out where I am going wrong. Thanks in advance :)

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

    The position of the chars matter. Consider simple example:

    ABA -> (0),(0,1),(1),(1,2),(2)

    AAB -> (0),(0,1),(0,1,2),(1),(1,2),(2)

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

For G, I haven't seen this solution posted before, and I think it's simpler? You can use FFT to solve G in $$$\mathcal O(N \log N)$$$. Note that you can easily reduce this problem to solving the sum of $$$\binom {a_i}k$$$ for all $$$k$$$ in range $$$[1, N]$$$ with $$$a_i$$$ being at most $$$N$$$. Now let $$$c_x$$$ be the number of occurrences of $$$a_i = x$$$. Then we simply want

$$$\displaystyle\sum_{i = 0}^N c_i\binom ik = \frac 1{k!}\displaystyle\sum_{i = 0}^N (c_i \cdot i!) \cdot \frac 1{(-(k - i))!}$$$

.

Now we can compute this in one FFT. I have linked my submission below.

Submission

→ Reply