### maroonrk's blog

By maroonrk, history, 23 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! Comments (57)
| Write comment?
 » 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?
•  » »
 » I quit
 » How to solve C?
•  » » 23 months ago, # ^ | ← Rev. 5 →   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
•  » » » thank you very much, this solution is much clearer than the editorial.
 » The ARC is harder than I thought:
•  » » 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 are2^15=32,768kind of Y.It is enough for the time limit.Here's my code
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   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?
•  » » » 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).
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   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.
 » 23 months ago, # | ← Rev. 2 →   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
 »
 » 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.
 » 23 months ago, # | ← Rev. 7 →   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))) if a else 1 n, s = sys.stdin print(f(list(map(int, s.split())))) 
•  » » 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.
•  » » » » 23 months ago, # ^ | ← Rev. 5 →   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.
 » 23 months ago, # | ← Rev. 4 →   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.
•  » » 23 months ago, # ^ | ← Rev. 3 →   (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
•  » » » The solution is amazing! Thanks for your efforts:)
•  » » 23 months ago, # ^ | ← Rev. 3 →   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
•  » » » 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.
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   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...
•  » » 23 months ago, # ^ | ← Rev. 4 →   $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 •  » » » 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}$. •  » » » » 22 months ago, # ^ | ← Rev. 2 → 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 •  » » » » » Thanks! I've got it.  » 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! •  » » 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.  » 22 months ago, # | ← Rev. 3 → 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: 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|]\$).