We will hold AtCoder Beginner Contest 215.
- Contest URL: https://atcoder.jp/contests/abc215
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210821T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: blackyuki, leaf1415, Nyaan, physics0523
- Tester: kyopro_friends, math957963
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
i love atcoder math contest
In my opinion, there should be two 400 points problems and one 600 because it's an ABC contest.
and IMO, the present renewed distribution is better.
How to solve G?
Let $$$cnt_i$$$ be the number of candies with color $$$i$$$. Consider all $$$i$$$ such that $$$cnt_i \gt 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.
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)$$$.
Is there an alternate solution to E without DP ?
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
I think today's contest was awesome, Thanks.
Lesson Learnt: Don't use log2(N) :( Thanks Atcoder!
Did you figure out where does it fail? I also got WA initially with that.
I checked (int)log2((1<<59)-1) and it gave me 59 (It should be 58)
Thanks,any idea why does it happen?
Probably a precision issue as it deals with doubles
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.
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().
You can use
__lginstead.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:
Submission: https://atcoder.jp/contests/abc215/submissions/25284623
Please can you help me why am i getting runtime error on this: https://atcoder.jp/contests/abc215/submissions/25243897
As a writer, I tried to write very short statements in A-D, as you want!
Thanks ! I enjoyed the round so much. Also I turned blue on atcoder :yay:
Problem D is so tight. I got TLE by factorization using precomputed prime set. Is this intended?
Use SPF for prime factorization in O(logn).
Link
How to Solve F ?? Can someone explain it ??
Binary search for answer
ok will try . Thank You
I have participated in 20+ ABC's and yet haven't solved E :(
Nice contest! Thanks!
How to solve D?
Do prime factorization each elements but fast
Use sieve
so first find out prime factors of each of the array element and then go ahead with marking off the multiples of each prime factor till "m"
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"
Could someone explain how this gets WA on F? I couldn't really understand the tutorial. Thanks https://atcoder.jp/contests/abc215/submissions/25240944
the editorial says that ,this is a bitmask dp problem..
you're thinking about E, the tutorial for F says binary search
ohh sorry.frist you should sort in the ascenting order.then you should use binary search+towpointer to the answer. here my submission https://atcoder.jp/contests/abc215/submissions/25249451
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?
The LCM might be very large and overflow, e.g. $$$lcm(99971, 99961, 99929, 99923, 99907) = 9969136729118531781864539$$$ will not fit a 64-bit integer.
[solved]
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 :)
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)
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
.
Now we can compute this in one FFT. I have linked my submission below.
Submission