maroonrk's blog

By maroonrk, history, 4 years ago, In English

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!

  • Vote: I like it
  • +250
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Like we Chinese, the time is really good for us. Hope to get a nice rated change!

»
4 years ago, # |
  Vote: I like it +168 Vote: I do not like it

This may be my last (full) contest as I'm supposed to start working from this April. Please participate!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Thanks for all the problems and Good Luck!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +80 Vote: I do not like it

    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!

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Unrelated to this contest, but does anyone know how to see my submissions page on AtCoder?

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I quit

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C?

  • »
    »
    4 years ago, # ^ |
    Rev. 5   Vote: I like it +17 Vote: I do not like it

    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:

    1. We have never seen this element before. Then we need to add 1.
    2. 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
    3. 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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you very much, this solution is much clearer than the editorial.

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ok, got it. I should have tried some examples for my own, then it becomes more clear.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am curious about the graph thing too, it is needless, all you should do is to subtract something from n*m^n.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Was N*M*log solution supposed to TLE in problem C?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I get the test cases, I am confused about few. Thanks

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem E FFT?

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I find my bug and that was seriously stupid! poooof!

»
4 years ago, # |
  Vote: I like it +55 Vote: I do not like it

 5 WAs & 30 minutes on A.

»
4 years ago, # |
Rev. 7   Vote: I like it +8 Vote: I do not like it

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()))))
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 5   Vote: I like it +3 Vote: I do not like it

        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.

»
4 years ago, # |
Rev. 4   Vote: I like it +26 Vote: I do not like it

Another $$$O(nm)$$$ traditional DP solution of Problem C:

Hint 1
Hint 2
Solution

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    (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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The solution is amazing! Thanks for your efforts:)

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +16 Vote: I do not like it

    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:

    Claim

    let $$$X = min(A_{l...r})$$$. Thus considering the immediate neighbours there are three cases to consider

    Case 1
    Case 2
    Case 3

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like 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...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider red and blue edges as 0s and 1s, and on each vertex write xor of edges connecting to it.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow this explanation hits the target. Really appreciate!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody explain problem E a little more? I can’t clearly understand the tutorial...

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like 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!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem D (Moving pieces on a line), can anyone provide some intuition/case why the following greedy solution is incorrect?

  1. 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.

  2. 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.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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