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!.
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.
Omg, based on setters I think this will be one of the best OpenCups ever.
Ejudge doesn't work :(
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.
yes...
Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
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.
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.
Wow! This generalization of SMAWK in the evacuation problem is just awesome!
What does this mysterious abbreviation stand for?
I think he's referring to this.
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
Where are the problems? Why do all open cup have editorials but not problems?
Why the downvotes?
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.
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.
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.
Is there a link I could go to to see the problems?
There's a pdf file but I'm not sure if we're allowed to post 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?
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).
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.
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$$$.
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.
Would you mind sharing your code? I can't get this to run in time.
Sure, 77420579
In problem D we used the following
Lemma: let $$$n > 3$$$, $$$0\leq x\leq m$$$. Then the set
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$$$).
Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
In problem E how to optimize the solution using bitset?
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))$$$.
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?
Sorry，I can’t understand why we don’t consider transition when k>4 and k-j>1. Can anyone explain it?
Problem D
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.
got it，thx！
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, with0always at the end.