### maroonrk's blog

By maroonrk, history, 6 months ago,

We will hold AtCoder Regular Contest 114.

The point values will be 300-400-600-600-700-900.

We are looking forward to your participation!

• +250

 » 6 months ago, # |   0 Like we Chinese, the time is really good for us. Hope to get a nice rated change!
•  » » 6 months ago, # ^ |   -19 hope so, this is my first time join ATCoder, Chinese two!
•  » » 6 months ago, # ^ |   +3 Time is also good for central asia
•  » » 6 months ago, # ^ |   -10 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
•  » » » 6 months ago, # ^ |   0 Link to the editorial : https://atcoder.jp/contests/abc194/editorial/863
 » 6 months ago, # |   +168 This may be my last (full) contest as I'm supposed to start working from this April. Please participate!
•  » » 6 months ago, # ^ |   0 YES BOSS ! IM IN
•  » » 6 months ago, # ^ |   +20 Thanks for all the problems and Good Luck!
•  » » 6 months ago, # ^ |   +80 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!
 » 6 months ago, # |   +5 Unrelated to this contest, but does anyone know how to see my submissions page on AtCoder?
•  » » 6 months ago, # ^ |   +6
 » 6 months ago, # |   0 YUPPP ,I am IN :)
 » 6 months ago, # |   +28 I quit
 » 6 months ago, # |   +3 How to solve C?
•  » » 6 months ago, # ^ | ← Rev. 5 →   +17 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: We have never seen this element before. Then we need to add 1. We have seen this element before, say at index $k$. All the elements from $k$ to $i$ are $> x$. Then we need not add anything, because we could paint it with a range We have seen this element before, say at index $k$. There is an element between $k$ and $i$ such that it is $< x$. Then, we need to add 1, because we cannot paint a range 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
•  » » » 6 months ago, # ^ |   0 thank you very much, this solution is much clearer than the editorial.
 » 6 months ago, # |   +26 The ARC is harder than I thought:
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 only 15 primes smaller than 50, and every primes can be chosen once or not chosen, so there are2^15=32,768kind of Y.It is enough for the time limit.Here's my code
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » 6 months ago, # ^ |   +12 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?
•  » » » 6 months ago, # ^ |   +16 I thought that the operation allways needs exactly that much steps as there are distinct elements in X Counter-example: 1 2 1 2 1 2 1 2 (needs 5 operations).
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Ok, got it. I should have tried some examples for my own, then it becomes more clear.
•  » » » 6 months ago, # ^ |   0 I am curious about the graph thing too, it is needless, all you should do is to subtract something from n*m^n.
 » 6 months ago, # | ← Rev. 2 →   0 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
 » 6 months ago, # |   +16 Was N*M*log solution supposed to TLE in problem C?
•  » » 6 months ago, # ^ |   0 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).
 » 6 months ago, # |   0 Where can I get the test cases, I am confused about few. Thanks
•  » » 6 months ago, # ^ |   0 Wait for a couple of weeks before it arrives.https://atcoder.jp/posts/21
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 I had the same complexity and it got passed under 200ms https://atcoder.jp/contests/arc114/submissions/20940288
•  » » » 6 months ago, # ^ |   0 Yep, sir, my submission got passed too. But I'd like to know more about whether there's a better way to solve it.My submission(under 20ms) https://atcoder.jp/contests/arc114/submissions/20943485
 » 6 months ago, # |   +45
 » 6 months ago, # |   0 Where can we discuss https://atcoder.jp/contests/ahc001?
•  » » 6 months ago, # ^ |   0 I think you can discuss it here.
 » 6 months ago, # |   0 Is problem E FFT?
•  » » 6 months ago, # ^ |   0 you missed a wonderful chance to say, E, -is-this-fft- ? :P
 » 6 months ago, # |   -8 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.
•  » » 6 months ago, # ^ |   -8 I find my bug and that was seriously stupid! poooof!
 » 6 months ago, # |   +55 5 WAs & 30 minutes on A.
 » 6 months ago, # | ← Rev. 7 →   +8 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. import sys def pf(x): i = 2 while i * i <= x: if x % i == 0: yield i while x % i == 0: x //= i i += 1 if x > 1: yield x f = lambda a: min((p * f([x for x in a if x % p]) for p in pf(a[0]))) if a else 1 n, s = sys.stdin print(f(list(map(int, s.split())))) 
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ | ← Rev. 5 →   +3 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.
•  » » » » 6 months ago, # ^ | ← Rev. 5 →   0 Actually, for your case his answer would be correct, because he multiplies the numbers in the set of the smallest prime factors, which in this case will be {3, 2}.A counterexample is 3, 5, 6, for which the answer is 15, but his solution gives 30.
 » 6 months ago, # | ← Rev. 4 →   +26 Another $O(nm)$ traditional DP solution of Problem C: Hint 1Let $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$. Hint 2Consider the first occurence position of $1$. SolutionAssume $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: $(m - 1)^{n - 1}$: $A_i = 1$ will add $1$ to $f(A)$ iff $A_{(i + 1) \ldots n} \leq m - 1$. Otherwise, the right sequence already contains $1$ and calculate it into $f(A_{(i + 1) \ldots n})$ so we do not need to care it. $(m - 1)^{i - 1}F[m][n - 1]$: The left sequence has $(m - 1)^{i - 1}$ possibilities and we multiply it by the sum of all possible $f(A_{(i + 1) \ldots n})$. Similar for $m^{n - i}F[m - 1][i - 1]$. Calculate it directly costs $O(n^2m)$. However, it can be easily simplified using prefix sums into $O(nm)$. DetailsLet$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.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +21 (Seriously I cannot understand how  works...Could anyone tell me how to use it?)Edited: Okay it seems to work although I did not really change anything...Whatever
•  » » » 6 months ago, # ^ |   +5 The solution is amazing! Thanks for your efforts:)
•  » » 6 months ago, # ^ | ← Rev. 3 →   +16 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: ClaimIt 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 Case 1$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 $\sum_{X = 1} ^ {m}\left((m - X + 1)^{r-l+1}-(m - X)^{r - l + 1}\right)\cdot (X-1)^2 \cdot m^{N - (r - l + 1) - 2}$ Case 2either $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 $\sum_{X = 1} ^ {m}\left((m - X + 1)^{r-l+1}-(m - X)^{r - l + 1}\right)\cdot (X-1)^1 \cdot m^{N - (r - l + 1) - 1}$ Case 3when $l = 0$ and $r = N$ in this case we have no neighbour $\sum_{X = 1} ^ {m}\left((m - X + 1)^{r-l+1}-(m - X)^{r - l + 1}\right)$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
•  » » » 6 months ago, # ^ |   +8 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.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +8 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...
 » 6 months ago, # |   0 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).
•  » » 6 months ago, # ^ |   0 Consider red and blue edges as 0s and 1s, and on each vertex write xor of edges connecting to it.
•  » » » 6 months ago, # ^ |   0 wow this explanation hits the target. Really appreciate!
 » 6 months ago, # | ← Rev. 2 →   0 In Problem B: why the output of below tc is 12 3Explanation: 1 --> 2 --> 3 (there is no cycle output should be 0) I am missing something?
•  » » 6 months ago, # ^ |   0 $f_{i} <= N$What I have done this, my inputs are wrong.
 » 6 months ago, # |   0 Could somebody explain problem E a little more? I can’t clearly understand the tutorial...
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 $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 •  » » » 6 months ago, # ^ | 0 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}$. •  » » » » 6 months ago, # ^ | ← Rev. 2 → 0 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\bigcupQ$and$P\bigcapQ = 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 •  » » » » » 6 months ago, # ^ | 0 Thanks! I've got it.  » 6 months ago, # | 0 In the editorial of problem C it is asked: Bonus: for how much value of$N$and$M$can you solve the problem? I am curious whether someone has a better time limit solution, Thanks! •  » » 6 months ago, # ^ | 0 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.  » 6 months ago, # | 0 Can anyone tell my what's wrong with my approach on the first question . let spf[x] = is the smallest prime factor of x now I multiplied all the unique elements among { spf[x1] , spf[x2] , spf[x3] , ..... , spf[xn] } .  » 6 months ago, # | ← Rev. 3 → 0 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).  » 6 months ago, # | 0 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. •  » » 6 months ago, # ^ | 0 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: When we move a token from position$a$to position$b$, moving the token directly from$a$to$b$($a \rightarrow b$) is equivalent (albeit with different cost) to$a \rightarrow INF \rightarrow b$(since the path$a \rightarrow b$is traversed once, the path$b \longleftrightarrow INF$is traversed twice, so the edge colors in this latter part are un-affected) Writing the move above ($a \rightarrow b$) in terms of applying "XOR" to a range, this is doing XOR$1$in the range$[a, b)$, which is the same as doing both XOR$1$in range$[a, INF)$and XOR$1$in range$[b, INF)$(given the rationale described previously that these two are "equivalent"). Jumping ahead a bit, let's look at$T$. If for each position$t \in T$we XOR 1 the range$[t, INF]$, and given that$|T|$is even, you can notice that we will get the alternating 0 — 1 — 0 ... — 0 sequence of edge segments. (think about why this only works for even$|T|$). Each of the XOR 1$[t, INF]$(for all$t \in T$) operations above can be done an odd number of times. You will still get the alternating 0 — 1 — 0 ... — 0 sequence of edge segments. Remember how in our second bullet point we showed that doing the move$a \rightarrow b$(XOR$1$in the range$[a, b)$) is equivalent to$a \rightarrow INF \rightarrow b$(XOR$1$in range$[a, INF)$and XOR$1$in range$[b, INF)$)? That means that our desired set of XOR ranges (XOR 1$[t, INF]$(for all$t \in T$)) can correspond back to some$a$and$b$. We know$a$, so we need to find$b$. 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|]\$).