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

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

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!

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

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

i love atcoder math contest

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

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

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

How to solve G?

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

    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.

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

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

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

Is there an alternate solution to E without DP ?

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

    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

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

I think today's contest was awesome, Thanks.

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

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

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

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

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

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

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

        Thanks,any idea why does it happen?

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

        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.

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

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

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

    You can use __lg instead.

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

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

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

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

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

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

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

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

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

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

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

Nice contest! Thanks!

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

How to solve D?

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

    Do prime factorization each elements but fast

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

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"

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

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

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

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?

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

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

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

[solved]

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

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

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

    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)

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

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