How to solve B, E, F, G, H, I, J?

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 186 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/24/2021 17:26:15 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

F: The idea comes from Petrozavodsk Summer 2016. Day 7: Ural FU Dandelion Contest. F. Suffix Array for Thue-Morse.

Build the compacted suffix automaton of $$$fib_n$$$ and you can find some nice structures.

`ab`

and`ba`

alternatively.An example for $$$fib_6$$$

The

`[[x]]`

means the accepting states, and the`[x]`

means a fibonacci word.It can be seen that we can only use $$$O(n)$$$ states to represent $$$fib_n$$$. And the suffix array can be obtained by walking the compacted suffix automaton. Since the maximum index is $$$10^{18}$$$, we can only keep the last $$$O(\log 10^{18})$$$ nodes.

Is the second extra b edge going from 3 to 7?

Is there a general method for solving this problem on various morphic words? For instance, what about tribonacci: $$$a \to ab, b \to ac, c \to a$$$?

E: It can be seen that $$$dp_x$$$ equals to some $$$a_i+b_{i+1}+\dots+b_{x}$$$. Let the prefix sum of $$$b$$$ be $$$s$$$,

Use segment tree to maintain the value of $$$a_i-s_i$$$.

Meh, nine <=medium problems that can be done in <=2.5h and one boring killer.

I agree but to be fair top-5 teams seems too strong now. Problems are either <=medium or almost unsolvable. It sounds stupid but... if it can be solved, USA1 will do it in 20 minutes :)

I'm thinking about preparing contest for Ptz and OpenCup and I'm very scared that you guys (and USA1 and Past Glory and japan02) will solve everything (maybe but 1 problem) in 3 hours and I don't really know what to do about it. I mean, if I can solve it, you'll solve it faster and better.

A tiny idea: try to stay away from Opencup for more than 3 years and you might probably find difficulty increasing.

Just kidding. Next time I will try to provide harder tasks for you. XD

Another idea for me could be to get rid of carrying teammates xD

My solution for $$$H$$$ is supposed to be $$$nlogn$$$ but I have been getting TLE with it. Here's my code if someone could help me find out why I'm TLEing: https://ideone.com/AirWlG and I will explain my idea below.

Let's look at the $$$sum$$$ case first. Let $$$totalSum(m)$$$ be the sum of all hamming distances for $$$S^m$$$.

Since $$$S^m = S^{m - 1} + [m] + S^{m - 1}$$$, it's easy to see that $$$totalSum(m)$$$ can be defined recursively as $$$2 * totalSum(m - 1) + subSum(m)$$$. Where $$$subSum(m)$$$ is the sum of the hamming distances of the subarrays that contain $$$m$$$ in $$$S^m$$$ (I will explain the base case later).

Let's solve $$$subSum(m)$$$. Let $$$d$$$ be the smallest $$$d$$$ $$$s.t.$$$ $$$\lvert{S^d}\rvert >= n - 1$$$. The middle part of any $$$S^m$$$ $$$s.t.$$$ $$$ m > d$$$ will look something like this:

$$$[..., v_1, v_2, ..., v_{n - 1}, m, v_1, v_2, ... v_{n - 1}, ...]$$$

Key observation is that for any $$$m > d$$$, All $$$n$$$ subarrays we want to consider in the calculation of $$$subSum(m)$$$ will only differ in the element with value $$$m$$$. I will refer to these subarrays by their order from now on. (e.g. $$$[v_1, v_2, ..., m]$$$ is first subarray, $$$[v_1, v_2, ..., m, v_1]$$$ is the second, and $$$[m, v_1, v_2, ..., v_{n - 1}]$$$ is the $$$n^{th}$$$

Let's define $$$F[i]$$$ to be the hamming distance of the $$$i^{th}$$$ subarray $$$without$$$ the element $$$m$$$. Now $$$F$$$ is the same for all $$$m > d$$$.

Now $$$subSum(m)$$$ is $$$(\sum\limits_{i=1}^n F[i]) + n - freq[m]$$$. Where $$$freq[m]$$$ is the frequency of element $$$m$$$ in array $$$a$$$. (This is because element $$$m$$$ will be compared against event element in $$$a$$$).

We now need to compute 2 things:

(1) $$$F$$$

(2) $$$subSum(d)$$$ (To use this as a base case for our recursive definition above).

We will compute both of them in a similar manner.

Define $$$H(a, b, k)$$$ to be a function that returns a vector $$$ans$$$ of size $$$k$$$. $$$ans[i]$$$ is hamming distance between $$$a$$$ and the $$$i^{th}$$$ cyclical shift of $$$b$$$.

With some goofing around, you can see that you can use this function (or something similar) to get:

(1) $$$F$$$ = $$$H(a, [v_1, v_2, ..., v_{n - 1}], n)$$$.

(2) $$$subSum(d)$$$ = $$$H(a, S^d, length(S^d) - n + 1)$$$.

(I can explain them in another comment if someone wants to but I don't want to make this text any longer than it already is :c).

Key Observation to calculate $$$H$$$ is to see that the $$$b$$$ we send is a special array. It has at most $$$log_2(n)$$$ unique values, and the distance between two occurrences of any element of $$$x$$$ is $$$2^x$$$. You can combine these 2 observations to calculate $$$H$$$ in $$$log_2(n) * k$$$ (I believe its calculation is clear in the code but I could explain it in another comment too if someone wants).

The $$$minimum$$$ case is similar. Define $$$minHamming(m) = min(minHamming(m - 1), minSubHamming(m))$$$.

$$$minSubHamming(m)$$$ will either be $$$minF$$$ or $$$minF - 1$$$. Where $$$minF$$$ is the minimum value in $$$F$$$ calculated above. The case where it will be $$$minF - 1$$$ is when the element $$$m$$$ matches its counterpart in $$$a$$$. You can iterate over indices $$$i$$$ of element $$$m$$$ in $$$a$$$ and minimize with $$$F[n - i - 1]$$$ Since this is the only subarray that will make $$$m$$$ match in index $$$i$$$.

Was solution for D just implication of Sylvester's determinant theorem, like $$$det(M)=x^{n}(1+\sum_{1}^{n}\frac{a_ib_i}{x})$$$? Are there some special cases?

There were no special cases

(for future reference)

"Sylvester's determinant theorem" refers to this.

I think this theorem is overkill here. You can subtract first row multiplied by $$$a_i/a_1$$$ from all other rows, then you get matrix with zeroes everywhere except first row, first column and diagonal and this case is obvious.The only special case is when $$$a_1 = 0$$$, then you need to swap it with some nonzero $$$a_i$$$.

Several teams (including us) missed this case on H:

The answer is

`6 6`

(there is only one orientation allowed, and it has distance 6), but it's easy to print`1 6`

if you accidentally allow the shift i=2 when computing the min. It's a one or two line fix but unfortunately wasn't in the test data.How to solve I.. ?

Do a straight-forward DP, like, f[i][last 3][second last 3]. Observe that generally f[i][][] and f[i + 1][][] differs by at most one row. Hence, it can be compute f[i + 1][][] from f[i][][] with O(n) efforts.

Argh... Got it, thanks!

For J first you make an observation that if jailings intersect in interesting way then their sets of boundary cells intersect. You also note that number of boundary cells of jailing is at most linear in terms of cells with particular value corresponding to that jailing that lets you iterate through it.

First, for each cell you gather all values such that this cell lies on boundary of corresponding jailings. Then for each value you iterate through all its boundary cells and check it with all values gathered there. I guess it works in $$$O(area)$$$, but no idea why.

What about the test cases of the following format?

¯\_(ツ)_/¯

So it's $$$O((area)^{\frac32})$$$ there. Either there were no such cases or it works fast anyway since TL was quite generous.

I'm not sure about our proof, we had many handwave parts, but at least on this case in is linear if you distinguish between vertical and horizontal boundaries and compare only vertical with horizontal.

We made a few big insights:

Just observation 2 gives a $$$O(area * log)$$$ solution using a plane sweep, but combining observation 1 lets us directly walk the boundaries for an $$$O(area)$$$ solution (you need to process rectangles in tiebreaking order).

One other helpful conjecture is that the total number of intersecting pairs is at most $$$O(area)$$$; does anyone have a proof/counterexample?

To be honest I don't really understand your idea. What is the value added by 2nd observation compared to what has been said before and how do you use it to get any solution? In a case where edges of two jailing coincide they intersect in many more than 2 points. In cases when they intersect in a corner only that is only 1 point. So it's not entirely true it is 0 or 2 point. And what tiebreaking are you talking about?

(I edited my comment a bit)

The key to avoiding these edge cases is adding a tiebreaking order so that no two coordinates are exactly equal. First, sort all rectangles so that rectangle $$$i$$$ contains rectangle $$$j$$$ only if $$$i < j$$$, e.g. by area from biggest to smallest. Let $$$R_i = [xlo_i, xhi_i) \times [ylo_i, yhi_i)$$$. Then, instead consider the modified rectangle $$$R_i' = [xlo_i + i \varepsilon, xhi_i - i \varepsilon) \times [ylo_i + i \varepsilon, yhi_i - i\varepsilon)$$$. Because our ordering goes from big to small, you can check that this modification doesn't affect which rectangles contain which, so $$$f(R_i', R_j') = f(R_i, R_j)$$$. Then, all coordinates are distinct, and our observation that the borders of 2 modified rectangles intersect at exactly 0 or 2 points (in fact, exactly $$$2 f(R_i, R_j)$$$) holds.

Once you have these, you can treat each (modified) rectangle as two horizontal and two vertical line segments. For each rectangle, to compute $$$s$$$, you find the sum of the indices of all other segments which intersect with these (with multiplicity) and divide by 2. This is a simple plane sweep. The first observation means that you can just walk the length of the segments instead, though I think you have to do O(original length), not O(number of post-tiebreak coords) (maybe someone can prove that the latter is small?).

Thanks, nice

How solve G without tl issues?

What's your complexity?

$$$O((n+m)\log n\log 10^8)$$$ We got AC after contest, but it took too much time to optimize it.

It is actually possible to do it in $$$O(n log n)$$$. Let P be our query point. First you determine how long horizontal and vertical rays starting from P we can draw. They can be determined using sweeping. They give you some upper bound on the answer. If answer is smaller it is because there is another point within rectangle formed by these rays. Depending on whether this obstacle point lies above or below diagonal ray starting from P, it gives upper bound corresponding to its x or y coordinate. You can determine these using sweeping as well. Solution by mnbvmar

You can do everything in one sweep (right to left), just keeping a regular segment tree for vertical segments and a set for horizontal segments. To get the answer, go down the tree and query the set. Code.

What was the correct idea for B?

Binary search on answer, then go left to right and greedily assign each symbol to the currently shortest sequence that want it now. It is easy to show that it is always better to append 2 to empty sequence instead of [20] and it is always better to append 0 to [2] instead of [202].

I don't think that it is always correct, but for 2020 it is.

Thanks, with binary search this kind of greedy becomes reasonable and easy to understand!

Were there wrong ideas that passed ?

No, I just had some harder ideas, which seemed correct, but eventually appeared to be wrong.

How to solve problem A (Arrange And Count) from div1 ? We thought about DP ,but we didn't manage to solve it.

The operation is basically: reverse the sequence and rotate it. So after an even step you can get any cyclic shift of the original sequence and after an odd step you can get any cyclic shift of the reversed sequence. The only thing left is to count the number of distinct sequences among all these. Doable with suffix array.

You need to find how many different sequences there are from all continuous subsequences of length $$$n$$$ from $$$a + a$$$ and $$$reverse(a) + reverse(a)$$$, where $$$+$$$ stand for concatenation. You can do it either with hashes, or with suffix array.

The answer is the size of the set containing all the rotation of the string, and all the rotation of the reversed string.

Let $$$|P|$$$ be the shortest prefix such that $$$P \cdot k = S$$$ (here $$$P \cdot k$$$ is $$$P$$$ concatenated with itself $$$k$$$ times). The number of different rotation is equal to $$$|P|$$$. So the number of different rotations if you also take into account the reverse is $$$2 \cdot |P|$$$, but with the caveat that some strings might appear twice, once in the initial string and once in the reversed.

If some rotation from the initial string appears as a rotation in the set of rotations of the reversed string, then both sets are the same.

You only need to compute the length of $$$|P|$$$ and check whether $$$rev(S)$$$ appears as a substring in $$$SS$$$. $$$P$$$ can be computed in $$$O(n)$$$ using the prefix ($$$\pi$$$) function, and the latter can be checked also in $$$O(n)$$$ using KMP.

Thank you for detail explanations awoo , Ra16bit , marX !

How to solve problem C (Choose Two Subsequences) from div1 ? We thought about DP ,but we didn't manage to solve it. We got WA2. Um_nik , tourist , pashka, Ra16bit .

You can do $$$\mathcal{O}(|s|\cdot |t|)$$$ DP to solve the problem for each suffix of $$$s$$$ and each suffix of $$$t$$$.

Thank you Benq Benjamin for the solution .I got it . We wrote dp on prefixes . it was our mistake .