maroonrk's blog

XX Open Cup GP of Tokyo
By maroonrk, history, 4 years ago, In English

Hello!

Opencup GP of Tokyo will be held tomorrow, with the same problems as tomorrow's MW-prefinal contest.

The writers are yosupo, sigma425, and me. I will post the editorial after the contest.

We are looking forward to your participation!

UPD The contest is over. Thank you for your participation!.

editorial

UPD2 I managed to load the contest onto the Gym. I'm sorry that the statement doesn't look pretty since it was originally written in markdown format. This is my first attempt to make a Gym contest, so there might be a mistake. If you find some problem, please let me know.

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

Comments Comments (34)
| Write comment?
»
4 years ago, # |
  Vote: I like it +80 Vote: I do not like it

Omg, based on setters I think this will be one of the best OpenCups ever.

→ Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Ejudge doesn't work :(

→ Reply
»
4 years ago, # |
  Vote: I like it +133 Vote: I do not like it

Wow the problems and solutions of this contest is so fucking beautiful that I can't even.....

Thank you very much for a really nice contest. You made my day, or even month.

→ Reply
»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +79 Vote: I do not like it

In problem E, the tutorial mentions for some part that its proof requires Lucas Theorem.

But there's a simpler proof for it. For any non-palindromic sequence, you can get its reverse and it'll be a different valid sequence, and since that is a bijection, the total number of non-palindromic sequences will be even. So you only need to consider palindromes.

To build a palindrome sequence of length $$$N$$$ and sum $$$S$$$, you have two cases:

1- $$$N$$$ is even, then you divide $$$N$$$ and $$$S$$$ by two and recurse.

2- $$$N$$$ is odd, so you need to choose one element, subtract $$$1$$$ from $$$N$$$, subtract this element from $$$S$$$, and go to $$$1$$$.

This procedure will lead to the same observations mentioned in the tutorial.

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

    Also one can look at unordered partitions. Partition must contain some item "the highest bit of $$$N$$$" times in order to have an odd number of orderings.

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

Wow! This generalization of SMAWK in the evacuation problem is just awesome!

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

    What does this mysterious abbreviation stand for?

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

    Yeah! And it also can be solved with the convex hull trick. Just transpose the matrix, and that's all.

    A bit more details: in editorial there is a function $$$fleft(l, x)$$$. We can treat it as a series of functions — $$$h_x(l) = fleft(l, x)$$$. In each query, we need to get the maximum in position $$$l$$$ among the values of functions $$$h_x$$$ for $$$1 \leq x \leq r$$$. So we can add functions one by one, and process queries meanwhile.

    And because of quadrangle inequality, each new function would be in a hull on some suffix. So the overall complexity is $$$\mathcal{O}((n + q) \log{n})$$$.

    code: 77420574

    → Reply
»
4 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Where are the problems? Why do all open cup have editorials but not problems?

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

    Why the downvotes?

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

      If you weren't hiding behind a fake account you'd probably see less downvotes.

      Anyway, I do think you have a point; it's not ideal that we have a contest that is of generally very high quality but the problems are not made available to general community.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

Lel, when Median Replace was on AtCoder I already did it by building DFA. Here is my code: https://atcoder.jp/contests/agc022/submissions/2288101 But I did it by hardcoding 4 reduction rules for that particular replacing function (median). I didn't even know that different solutions exist. When I read that "editorial of problem from AGC will not help" and saw that its editorial is in fact quite different from mine solution (at least on the first sight) it made me strongly believe that DFA approach is actually intended solution of J (moreover, it would be hard to imagine that anything works if DFA doesn't). Too bad I read this problem quite late and we had no time to actually come up with some reasonable way of building that automaton.

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

    Yes, agree, editorial was helpful for us too.

    Funny thing, with alphabet of size 3, language won't be regular anymore, if you consider rule 012->1.

    → Reply
»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Is there a link I could go to to see the problems?

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Is it true that in L it's possible to pick only $$$O(n)$$$ instead of $$$O(n\cdot \log(n))$$$ pairs as the candidates for answers? If yes, is it possible to find them quickly?

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

    The answer of first question is yes. But I don't know the way to enumerate pairs in O(n log n) time(in my remember, O(n log^2 n) is possible).

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

    Yes, here's an explicit way to get $$$O(n)$$$ candidate points. Best means "having greatest weight", and above and below refer to the $$$y$$$-axis.

    • For each red point, take the best blue point above it.
    • For each blue point, take the best red point below it.
    • For any maximal red point $$$r_i$$$ (i.e. a point such that $$$r_i$$$ is better than everything below it), consider the next red point $$$r_{i'}$$$ with greater weight (find the minimum $$$r_{i'}^y$$$ such that $$$r_{i'}^w > r_i^w$$$). Then, take $$$r_i$$$ with the best blue point above $$$r_{i'}$$$.

    We'll pick an arbitrary (but consistent) way of breaking tied weights. These pairs are easy to find in $$$O(N)$$$ time after sorting by $$$y$$$.

    The proof is pretty simple. We'll use the same observation from the editorial: for any $$$y$$$, any optimal pair that crosses $$$y$$$ must use the best red below $$$y$$$ or best blue above $$$y$$$.

    • For any non-maximal red point $$$r_i$$$, consider $$$y = r_i^y + \varepsilon$$$. Then, $$$r_i$$$ is not the best red point below $$$y$$$, so we must take the best blue point above $$$r_i$$$.
    • For any maximal $$$r_i$$$, consider the next $$$r_{i'}$$$ with greater weight. Then, consider any other blue point $$$b_j$$$. If $$$b_j^y < r_{i'}^y$$$, then $$$r_i$$$ is the best red point below $$$b_j$$$. Otherwise, if $$$b_j^y > r_{i'}^y$$$, consider $$$y = r_{i'}^y + \varepsilon$$$. Then, $$$r_i$$$ is not the best red point below $$$y$$$, so $$$b_j$$$ must be the best blue point above $$$r_{i'}$$$.
    → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It is also possible to solve L without using magic of symmetric queries. Just treat them as two separate queries, solve both and get maximum.

It can be done with sqrt-decomposition in $$$\mathcal{O}((q + n) \sqrt{n})$$$ time. Sqrt-decomposition is over the y-coordinates. In each block we store only red points, sorted by x. Also for each prefix we store maximum value on prefix, and best pair with an element from prefix (where a blue point is from the same sqrt-block). And also we store the best blue point from the sqrt-blocks above.

With that, we do a scan line from right to left. Processing blue points and R's of queries.

When adding a blue point, we should update the best blue points for all the sqrt-blocks below. And update prefix maximums for pairs in the current block.

When processing an R value, we should iterate over all sqrt-blocks. And in each one we take the best pair on prefix and the best red element on prefix + best blue point from the sqrt-blocks above.

With some care and preprocessing it all could be done in $$$\mathcal{O}((q + n) \sqrt{n})$$$ time. That is enough to get AC.

→ Reply
»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

In problem D we used the following

Lemma: let $$$n > 3$$$, $$$0\leq x\leq m$$$. Then the set

$$$\displaystyle\left\{\sum_{i=1}^na_i\,\mid\,0\leq a_i\leq m,\,\,\bigoplus_{i=1}^n=x\right\}$$$

of all possible sums of bounded by $$$m$$$ $$$n$$$-sequences with xor $$$x$$$ is a segment of numbers of fixed parity (possibly empty).

Does anyone know how to prove it? It doesn't hold if $$$n = 3$$$, for example, when $$$x = 1$$$ and $$$m = 12$$$ (we can obtain $$$25$$$ and $$$29$$$, but not $$$27$$$).

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

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

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

In problem E how to optimize the solution using bitset?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Assuming the dp without bitset is

    I think what seems hard to do with bitsets is to make sure the last bit of (mask + a[j]) is right and do the transition with (mask + a[j]) / 2. But the heavy part is iterating through K elements for every mask, we use bitsets just to improve that.

    You can double the size of bitsets and ignore the restriction on the last bit and the /2 transition. Just fix it after the heavy part. Overall complexity should be $$$O(\log(N) * (K * \frac{V}{32} + V))$$$.

    my code
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there some not computer-checking proof in J that there is such DFA? For example, is it true for 4 parts instead of 3?

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

Sorry，I can’t understand why we don’t consider transition when k>4 and k-j>1. Can anyone explain it?

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

    Problem D

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

      Let's say there is a sequence $$$b$$$ that uses this transition. Then, We can somehow make changes like $$$b_i:=b_i-4,b_{i+1}:=b_{i+1}+2$$$ to get new $$$b$$$ that doesn't use the transition (it can be proved by caseworks), so we don't need to consider it.

      BTW I found that the last part of the dp says dp[i][j]->dp[i+1][k] but it should be dp[i][j]->dp[i-1][k]. Sorry if it was confusing.

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem I has a mysterious alternative solution.

The problem statement requires indexing from $$$1$$$, but the following narration is indexed from $$$0$$$.

To be brief, we simply need to print $$$\log_2(n)$$$ cyclic shift of 0 1 2 ... n-1, whose first elements are $$$1,2,4,8,...$$$ respectively.

At last, we print a cyclic shift whose first element is $$$2^{\lceil \log_2 n\rceil}-n+1$$$.

If $$$n$$$ is odd, cyclic shifts should only consist of elements 1~n-1, with 0 always at the end.

→ Reply