We will hold AtCoder Regular Contest 114.
- Contest URL: https://atcoder.jp/contests/arc114
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210314T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: satashun
- Tester: gazelle, kobae964
- Rated range: — 2799
The point values will be 300-400-600-600-700-900.
We are looking forward to your participation!
Like we Chinese, the time is really good for us. Hope to get a nice rated change!
Time is also good for central asia
Why still no editorial for ABC 193????... Please provide it, or else can anyone explain Problem E ??
Just commented here so that author can see this
Link to the editorial : https://atcoder.jp/contests/abc194/editorial/863
This may be my last (full) contest as I'm supposed to start working from this April. Please participate!
Thanks for all the problems and Good Luck!
satashun is my direct senior in the same faculty, and I’m so sad to hear this may be the last contest ;-;
I’m looking forward to solving his interesting problems and hope many contestants!
Unrelated to this contest, but does anyone know how to see my submissions page on AtCoder?
https://kenkoooo.com/atcoder/#/table/
I quit
How to solve C?
My $$$O(nm)$$$ solution I failed to finish in time:
Consider $$$ans_i$$$ to be the answer for $$$n = i$$$. We seek $$$ans_n$$$.
Let us say that we add the ending element $$$x$$$ to a sequence. Then, we have three cases:
So, to get $$$ans_i$$$, for every $$$x$$$, we need to add 1 for all combinations where points 1 or 3 apply. The number of such combinations is a sum $$$S_x = m^{i-1} - \sum_{k = 1}^{i-1} (m-x)^{i-1-k} \cdot m^{k-1}$$$. The latter part of this equation counts the instance where we have only elements $$$>x$$$ between $$$k$$$ and $$$i$$$.
So, $$$ans_i = \sum_{x = 1} ^{m}ans_{i-1} + S_x$$$. By using the previous value for $$$S_x$$$ and updating it every iteration, we can solve it in $$$O(nm)$$$.
Submission
thank you very much, this solution is much clearer than the editorial.
The ARC is harder than I thought:<
I tried to solve A, but I got two wrong attempt, until I found out the only thing I need to do is to enumeration.
I like B best, only simple algorithms are needed, but require some thinking.
It took me nearly an hour to solve C, I think it's quite challange, isn't it?
Hope everyone enjoy the contest like I do!
Got stuck on A's 13th Test Case (1 WA/15). How does enumeration work, though? I didn't even attempt it because of the 2^15+ apparently possible permutations.
only 15 primes smaller than 50, and every primes can be chosen once or not chosen, so there are
2^15=32,768
kind of Y.
It is enough for the time limit.
Here's my code
Thanks.
In the heat of the contest, I overestimated the value of 2^15 (totally embarrassing) and ended up with a solution in which I first took up all the unique prime factors and then filtered out all the unnecessary ones with the help of GCD.
My solution would fail the following test case:
3
21 28 35
The output of my program would be 3*2*5 = 30 instead of 7.
My Submission
I just did read the editorial of C. It seems I did not get how the operation works.
I thought that the operation allways needs exactly that much steps as there are distinct elements in X. But in editorial they construct some graph...and things.
Can you explain what the operation does, and why we need that graph thing?
Counter-example: 1 2 1 2 1 2 1 2 (needs 5 operations).
Ok, got it. I should have tried some examples for my own, then it becomes more clear.
I am curious about the graph thing too, it is needless, all you should do is to subtract something from n*m^n.
why does my logic for C fail ? I iterate on positions i,j such that a[i] == a[j] and no element in between is equal to a[i], then I calculate whether both are done in one pass or not by checking that whether they have an element less than a[i] b/w them. The answer for first encountered m is added initially. My submission https://atcoder.jp/contests/arc114/submissions/20939508
Was N*M*log solution supposed to TLE in problem C?
I've also got my O(N*M*logN) solution TLE and the Editorial says O(M*N) [since we can incrementally calculate the powers]. I pre-calculated powers in memory in order to get O(M*N) solution with Haskell, but it TLE'ed again for me, so I Wolfram|Alpha-ed the sum through N to get O(MlogN).
Where can I get the test cases, I am confused about few. Thanks
Wait for a couple of weeks before it arrives.
https://atcoder.jp/posts/21
Can A be solved in a quicker way? The time complexity of my solution is $$$n\times 2^{\pi(\max{a_i})}\times \pi(\max{a_i})$$$, where $$$\pi(x)$$$ denotes the number of primes not greater than x.
I had the same complexity and it got passed under 200ms https://atcoder.jp/contests/arc114/submissions/20940288
Screencast with commentary
Where can we discuss https://atcoder.jp/contests/ahc001?
Is problem E FFT?
Hi, Can you please tell me why does my logic for problem B fail? The only difference between my solution and editorial is that I count strongly connected components with the number of vertices greater than 2 or have a loop as the number of cycles, instead of counting connected components.
I find my bug and that was seriously stupid! poooof!
5 WAs & 30 minutes on A.
For problem A the answer is the minimum taken over the prime factors of an arbitrary input value of the product of that prime and the solution (recursive) for the subset of the input values not divisible by it (assuming that for the empty input the answer is 1).
A solution in Python.
I am doing almost similar thing. Take GCD of the given numbers. If GCD != 1 then we have got our answer. Else find minimum factor of each number & store in set (so that numbers remain unique). Then finally print multiplication of the stored numbers in the set.
But its giving WA can you help? My Submission
What you are doing is to simply multiply all distinct primefactors of all numbers.
Consider numbers 3 4 15, gcd of them is 1. So you end up multiplying 2*3*5, which is wrong because 2*3 covers all numbers.
For the case when GCD of all the numbers is greater than 1 you might think that the answer would be it's smallest prime factor, which is definitely better than GCD itself. But even this is not correct! For 14, 21 GCD is 7, but the answer is 6.
Another $$$O(nm)$$$ traditional DP solution of Problem C:
Let $$$F[m][n]$$$ denotes the sum of $$$f(A)$$$ over all $$$m^n$$$ arrays $$${A_1, A_2, \ldots, A_n}$$$ where $$$1 \leq A_i \leq m$$$.
Consider the first occurence position of $$$1$$$.
Assume $$$F[m][n]$$$ denotes the sum of $$$f(A)$$$ over all $$$m^n$$$ arrays $$${A_1, A_2, \ldots, A_n}$$$ where $$$1 \leq A_i \leq m$$$.
If $$$1$$$ is not in the array $$$A$$$, we can simply decrease all $$$A_i$$$ by $$$1$$$, resulting $$$1 \leq A_i - 1 \leq m - 1$$$, i.e. $$$F[m - 1][n]$$$.
Else, enumerate $$$i = 1 \ldots n$$$ as the first occurence position of $$$1$$$, i.e. $$$2 \leq A_{1 \ldots (i - 1)} \leq m$$$, $$$A_i = 1$$$ and $$$1 \leq A_{(i + 1) \ldots n} \leq m$$$. Consider the contribution from $$$A_{1 \ldots i - 1}$$$ and $$$A_{i + 1, n}$$$, we have
$$$F[m][n] = F[m - 1][n] + \sum_{i = 1}^n (m - 1)^{n - 1} + (m - 1)^{i - 1}F[m][n - i] + m^{n - i}F[m - 1][i - 1]$$$
Here:
Calculate it directly costs $$$O(n^2m)$$$. However, it can be easily simplified using prefix sums into $$$O(nm)$$$.
Let
$$$S[m][n] = (m - 1)S[m][n - 1] + F[m][n - 1]$$$
$$$T[m][n] = mT[m][n - 1] + F[m - 1][n - 1]$$$
Then
$$$F[m][n] = F[m - 1][n] + n(m - 1)^{n - 1} + S[m][n] + T[m][n]$$$
Therefore it is $$$O(nm)$$$.
In addtion, this DP algorithm is similar to that in problem "Swimming Pool" in NOI2017 (National Olympiad Informatics in China) Link: LibreOJ, though the latter is more difficult.
(Seriously I cannot understand how
<spoiler>
works...Could anyone tell me how to use it?)Edited: Okay it seems to work although I did not really change anything...Whatever
The solution is amazing! Thanks for your efforts:)
Thank you for the lovely solution. I was looking for a similar dp but was not able to see the trick of the one only adding if it is the last one. I however stumbled across this solution. I am not sure how to prove all the steps but it went something like this:
It is always optimal to choose a range $$$[l,r]$$$ such that for all $$$k$$$ $$$ l \le k \le r$$$ $$$ A_k \ge min(A_{l...r})$$$.
let $$$X = min(A_{l...r})$$$. Thus considering the immediate neighbours there are three cases to consider
$$$1 < l < N$$$ and $$$1 < r < N$$$ in this case for the elements in the middle we have $$$(m-X + 1)^{(r - l + 1)} - (m- X)^{(r-l+1)}$$$ i.e. all possibilities letting the elements be between $$$m - X$$$ and $$$m$$$ — the case when all elements are between $$$m - X + 1$$$ and $$$m$$$ For each of the two neighbours we have $$$X-1$$$ options since they must be strictly smaller than the X. For all other elements $$$m ^{N - (r - l + 1) - 2}$$$. Putting it all together we get
either $$$l = 0$$$ or $$$r = n$$$ but not both the only difference in this case is that we only have one neighbour. The resulting formula is
when $$$l = 0$$$ and $$$r = N$$$ in this case we have no neighbour
Thus we calculate $$$dp[length][type]$$$ in $$$O(mn)$$$ using the above formulas. We then iterate over all $$$i$$$ and $$$j$$$ st $$$1 \le i \le j \le n$$$ and add the corresponding dp to ans resulting in something like this
Thanks for your another solution!
However, I cannot understand what does the claim mean...Isn't it always true for any array $$$A$$$ that $$$A_i \geq \min_{x \in A}{x}$$$?
Btw have you checked the official editorial? It seems to be similar to your solution and maybe you can get some inspiration from it.
Indeed so the first move should involve all elements... I should add that $$$min(A_l...A_r)$$$ has not yet been solved... They possibly could be equivalent. Unfortunately I am still yet to understand the underlying graph that is utilised in the solution...
Could anyone clarify the logic behind problem D? I could hardly understand the official solution to D from the beginning (i.e. what does "incident edges" mean in the context and how can we rephrase the task into that).
Consider red and blue edges as 0s and 1s, and on each vertex write xor of edges connecting to it.
wow this explanation hits the target. Really appreciate!
Could somebody explain problem E a little more? I can’t clearly understand the tutorial...
$$$E[turns] = E[horizontal cuts + vertical cuts] = E[horizontal cuts] + E[vertical cuts]$$$. . $$$E[horizontal cuts]$$$ = $$$\sum_{i}P(i).1$$$ where $$$P(i)$$$ is probability that $$$i'th$$$ row is cut in some turn. To calculate this sum iterate over each row and find probability that this row is deleted. Let's consider the two given black cells have rows $$$r$$$ and $$$y$$$ where $$$r < y$$$. Make a square having two black cells as opposite ends. Whenever we cut any lines in this square game ends immediately. Let's call total lines in this square as $$$T$$$. Consider each line above $$$r$$$, to find $$$P(r)$$$ notice that we have to cut this line first from a set of rows which should have every row from this row to $$$y$$$ and all columns in the square we drawn above which is equal to $$$S=y-i+T$$$. $$$P(i<r) = 1/S$$$. Now you can similarly consider other two cases where row resides in square and row lies below square. Also do the same for vertical lines.
Thanks for your reply. But I still have some troubles about the calculation of P(r) which equals $$$\frac{1}{S}$$$ but not consider the order between the elements.
For example, now we consider the situation that we should make 2 at the first position, we can simply calculate $$$P=\frac{1}{2}$$$, but actually all the orders are: 1; 2; 2 1(1 and 1 2 we can consider them the same), now $$$P=\frac{2}{3}$$$.
Let's first to solve this problem — Consider a set $$$S$$$ union of an element $$$e$$$ and a set $$$S'$$$. Let $$$a$$$ be an element of $$$S'$$$. What's the probability that $$$a$$$ is taken out of $$$S$$$ before any other element from $$$S'$$$? Following calculation can be done to find that p-bility. First take $$$e$$$ and than $$$a$$$ or take $$$a$$$ on first turn. p-bility is $$$(1/|S|)*(1/|S'|) + (1/|S|) = (|S'| + 1)/(|S|*|S'|) = 1/|S'|$$$ since $$$|S| = |S'| + 1$$$. Now let $$$S = P\bigcup$$$ $$$Q$$$ and $$$P\bigcap$$$ $$$Q = NULL$$$. What's the p-bility that element $$$a$$$ form set $$$P$$$ is taken before any other element from $$$P$$$. We can notice that order of elements from $$$Q$$$ does not matter therefore we can consider the set $$$Q$$$ as single element $$$e$$$ and this is same as above problem.
Here is my submission — https://atcoder.jp/contests/arc114/submissions/20961705
Thanks! I've got it.
In the editorial of problem C it is asked:
I am curious whether someone has a better time limit solution, Thanks!
I'm pretty sure it's solvable in $$$O(M \log N)$$$. We're basically counting $$$\sum (N-d-1) M^{N-d-2} (m-1)^2 ((M-m+1)^d-(M-m)^d)$$$ or simpler, which can be reduced to sums in the form $$$\sum (m/M)^d (N-d-1)$$$ and that can be converted to closed form using generating functions for fixed $$$m$$$. It's a lot of careful algebra.
In problem D (Moving pieces on a line), can anyone provide some intuition/case why the following greedy solution is incorrect?
Mark an edge with 1 if we need to make a change to it (i.e. let a token traverse that edge). Otherwise, mark it with 0 (no token needs to traverse the edge). Initially, each edge in segments $$$[1, t_0 - 1]$$$, $$$[t_1, t_2 - 1]$$$ etc are marked with 0. Edges in segments $$$[t_0, t_1 - 1]$$$, $$$[t_2, t_3 - 1]$$$ etc are marked with 1.
Sort tokens by their position (in non-decreasing order). Iterate over each token in that order, and see if there's any edge to the left marked with 1. If there is at least one, move the token to the vertex left to the leftmost edge marked with 1. Make sure to flip/xor every edge that was traversed on that path. After this, "that leftmost edge" that was marked with 1 will now be marked with 0. Some other edges to the right of it might flip to 1 though. For each token that had to be moved, mark it as moved. Some might not be moved if there's no edge marked with 1 to the left of it.
Repeat this process, but now sort them in non-increasing order: Iterate over each token in this order, but now see if there's any edge to the right marked with 1. If so, give the rightmost such edge, and move your token to the vertex just after it, and flip/xor every edge along the way.
At the end you check if every edge is marked with 0. If they are, there's a solution, otherwise there isn't. The cost of your solution is defined by how you decided to greedily move the tokens (as described above).
Could anyone offer their perspective on problem D, especially the part when they put $$$a_i$$$ and $$$b_i$$$ in the multiset and then get the elements which occur an odd number of times. How it is that if that set is $$$t$$$ then the objective is achieved?
Thanks in advance.
Supposing we know $$$a$$$ (we do, these are the initial positions of the tokens) and $$$b$$$ (we don't, these are the final positions of the tokens): if the XOR (symmetric difference) of these two sets is $$$T$$$, then at least we know the answer exists, and $$$b$$$ is one such possibility.
The intuition here is the following:
Now, from $$$a$$$ and $$$T$$$ we can recover $$$b$$$. Because:
$$$a \oplus b = T$$$ (from the previous paragraph)
$$$a \oplus T = b$$$.
It should be the case that $$$|a| \geq |b|$$$. Otherwise, we need more final positions than # of initial tokens we had.
Note that when we recover $$$b$$$ from $$$a \oplus T$$$, it could be that $$$|b| \leq |a|$$$.
Finally, we do the following DP. $$$dp[i][j]$$$: The minimum cost of matching the first $$$i$$$ positions in (sorted) $$$a$$$ with the first $$$j$$$ positions in (sorted) $$$b$$$. For each transition, we might decide to pair $$$(i, j)$$$ or pair $$$(i, i + 1)$$$ (since there are not enough $$$b$$$s). The answer is when everything has been paired ($$$dp[|a|][|b|]$$$).