| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
AtCoder Grand Contest 026 will be held on Saturday (time). The writer is sugim48 and yosupo. This contest counts for GP30 scores.
Contest duration: TBD (about 2 hours)
The point values will be announced later.
Let's discuss problems after the contest.
The round starts in 2 hours.
Duration: 150 minutes
Point values: 200 — 600 — 600 — 1100 — 1600 — 2000
Is there a near-linear solution of E? Considering the solution is just substring construction: pick the last (number of 'b'-s minus number of 'a'-s) 'b'-s in some prefix, then while there's a 'b' before the last 'a' picked with 'b' so far, pick that 'b' too", then DP over substrings constructed this way, it feels like there could be a faster solution than O(N2) DP. For example, if we could decide which prefix to start with in O(1), that gives a linear solution instantly. And the prefix to start with is the one with maximum (number of 'b'-s minus number of 'a'-s), so the only ambiguity appears when there are more of them.
Also, my solution of B is funny: deal with obvious cases until there are no more obvious cases, guess that the answer's always "yes" or always "no" at that point, check the samples for which answer it should be.
Yes, we describe O(N) solution in the editorial.
Are there English editorials for B and C?
C: Meet in the middle. Generate all pairs of strings in the first half and in the reversed second half of the string for all 2N colourings in each case. For a valid colouring, it has to be the same pair — let's say that we have a pair (s1r, s1c) in the first half and (s2r, s2c) in the reversed second half; then |s1r| + |s2r| = |s1r| + |s1c| = N gives |s2r| = |s1c| and if
(
means reversed string), then equal lengths mean s1r = s2c and equivalently s2r = s1c. Sort the pairs in each half and just compute the number of common pairs (of pairs). O(2NN2).
B: it just works
B: If A < B we lose immediately. If D < B, then each day the number of cans decreases, so we will lose some day for sure. Let's assume A, D ≥ B. If C ≥ B - 1, each night there are either more than C cans left, which is enough for Snuke to buy on the next day, or not more than C cans left, in which case we add D cans and Snuke can buy B cans on the next day. If C < B - 1, then the process looks like this: we take A modulo B, if it's greater than C, we lose, otherwise we add D and take the new value modulo B, check if it's greater than C again, and so on. In other words, we need to check if
. To do that, replace D with 
. Then 
is the biggest value of 
which is less than B.
Can you please explain the last part a bit, where we need to find maximum((A + kD) mod B)?
Thank you
That's just some basic properties of arithmetic progressions modulo n. Progression
has 
different values and they have the form 
, where 
. Also, these values are "monotone" in the sense that they start with 
, increase until 
is greater than B, then they "overflow" and continue increasing, until we reach 
again. The maximum is achieved right before this "overflow" happens. So we need to find maximal k such that 
. We can solve this linear inequality and get that 
. We need maximal integer k that satisfies this inequality, so 
.
I thought the same thing in contest timing but was stuck at the step where we have to find the maximum value of (A + k*D)%B ....
I guess what I lacked was knowledge.. , was unaware of these "basic properties" as you call them..
Can you give me some source where I can look some basic properties related to number theory like this one? Or some source where this is given?!
In Russia this stuff is taught at schools, that's why I called it basic. I guess you could try googling "extended euclidian algorithm" or "linear diophantine equations in 2 variables".
* in ~1% of schools
In case anyone else was confused with case 1 :
C>=B-1; A,D>=B
You can view it this way, the only way the shopping could terminate is if we are left with a number which is greater than C, but smaller than B,we are stuck then. Mathematically, if there exists x, such that B>x>C, then the shopping could end .
If we apply the condition C>=B-1, we see that there is no number which could cause the shopping to terminate. Hence then the shopping is perpetual for this case.
Thank you aid for the amazing proof.
In problem D, the histogram can be abstracted as a tree of O(N) rectangles; this tree can be constructed easily in quadratic time and in a slightly more complicated way in
.
Formulating the DP on the tree is quite clear: each subtree has a horizontal base, which can have alternating colours; if it does, then each row (of this rectangle) is alternating, otherwise each column is alternating. Alternating rows mean all the subtrees have alternating bases as well, alternating columns mean the subtrees can be coloured in any way. Therefore, we should compute two numbers for each rectangle/vertex/subtree: the number of colourings (of the subtree) and the number of these colourings where the base is alternating. The DP can be computed in
; see my code for the exact DP formula.
How do you partition the histogram into rectangles?
If you have some part of the histogram (left border, right border, base — bottom border), take the minimum of heights of columns between the left and right border; this will be the top border of the rectangle in the current node. Its subtrees are constructed recursively, for each maximum range (left border in son, right border in son) that contains only columns higher than the top border of the current rectangle.
It's quite natural — take away the largest rectangle containing the whole bottom row, you're left with some connected components, recurse into them.
The main advantage of this is that subtrees obviously don't affect each other and all interactions are only between a parent's and a son's horizontal edges.
Aight that makes sense, thanks.
P.S. Your code really is amazing :)
Can anyone explain about the solution of D-histogram coloring? I'm trying to solve this problem with two dp arrays as mentioned in the English editorial. I think this solution looks like a straightforward dp solution, but I'm having a difficulty in deriving the exact dp formula.
Thanks in advance.
I read comments, but I'm looking for the dp solution without explicitly constructing trees. I think dp[i][j]=(number of ways to color all the grid in a histogram at column 1 to i, and j-th highest height to the highest row satisfying the given conditions) might solve this problem, but as I cannot derive the exact formula, I ask this question.
If there's anything that I misunderstood, please let me know.
Thank you for reading my comment.
Here’s my code for that approach: https://beta.atcoder.jp/contests/agc026/submissions/2849310