### rng_58's blog

By rng_58, history, 2 years ago, , AtCoder Grand Contest 026 will be held on Saturday (time). The writer is sugim48 and yosupo. This contest counts for GP30 scores.

Contest Announcement

Contest duration: TBD (about 2 hours)

The point values will be announced later.

Let's discuss problems after the contest. agc, Comments (20)
 » The round starts in 2 hours.Duration: 150 minutesPoint values: 200 — 600 — 600 — 1100 — 1600 — 2000
 » 2 years ago, # | ← Rev. 3 →   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(N 2) 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 2 N colourings in each case. For a valid colouring, it has to be the same pair — let's say that we have a pair (s 1r, s 1c) in the first half and (s 2r, s 2c) in the reversed second half; then |s 1r| + |s 2r| = |s 1r| + |s 1c| = N gives |s 2r| = |s 1c| and if ( means reversed string), then equal lengths mean s 1r = s 2c and equivalently s 2r = s 1c. Sort the pairs in each half and just compute the number of common pairs (of pairs). O(2 N N 2).
•  » » 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
•  » » » 2 years ago, # ^ | ← Rev. 6 →   In case anyone else was confused with case 1 : C>=B-1; A,D>=BYou 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.