Of course not

Thanks for your reminder! Would it coincide with other contests if online-mirror contest starts one day in advance? If suitable, we can shift it to an earlier date.

UPD: Starting time is advanced from Sunday to Saturday. Wish you all have known.

Indeed, You can see it sooner or later. BTW, Asia Xuzhou Regional Contest is extremely difficult, compared to this one. :)

As it is temporarily inaccessible, please be back just 6 hours before the starting time.

L: if m > n, the answer is 0, and if m = n, it's just number of ways to make a single cycle.

if m < n, then the graph is just k = n - m paths (some may be trivial though). Let's say we fix that there are d non-trivial components (have at least 2 vertices).

Then there are ways to choose the endpoints of the non-trivial components, and for each choice, we want to find number of ways to pair them up, which is .

From the remaining vertices, there are ways to choose the vertices in the trivial components.

And finally, the remaining vertices can be freely permuted and then distributed à la balls and bins, in ways -- during the contest, I did this part with Exponential Generating functions; it requires more theory, but very little creativity, so it's easier for me.

We also had to add an edge case for m = 0 (the answer is 1).

(edited to fix grammar)

I: There are at most O(n) segments to group. So let's sort them and make a two-pointer. What we need to do is to check whether there is a valid division. Segment tree works here, since the information of two segments can be merged easily.

I: Sort the valid 2 * N - 1 intervals by their weight. Let's enumerate the minimum and find the corresponding maximum. Consider a simpler problem: Given some intervals (L_i, R_i], find whether we can cover the interval (0, N] without overlapping. It's equivalent to finding whether we can reach N from 0 by the edges . Because the length of a interval is at most 2, we can maintain a segment tree, where the segment [L, R] stores the connectivity between [L, L + 1] * [R - 1, R]. It's easy to merge the information. Using a 2-pointer and maintaining the connectivity dynamically, we can solve the problem in .

First, count how many palindromes begin with s_i and let the number be f_i.

Then, find the maximum length d (d ≥ 0) such that s_i - k = t_k for each k = 1, 2, ..., d and let the length be g_i.

The answer should be .

The first part can be solved using manacher algorithm as you know, and the second part is equivalent to calculate for every suffix of the reversed string rev(s) the longest common prefix (LCP) with t, which can be solved using Z algorithm.

Maybe it's an overkill to use suffix array or suffix automaton solving this problem, isn't it?

Why does the randomized solution work for K?

I did ternary search on all 3 coordinates. Do a ternary search on x first, now for getting optimal answer for this x, do ternary search on y keeping x fixed, repeat this for z, keeping x and y fixed.

delete the k-continuous 0/1 in the 2 string and compare them

The first thing to explain is that the following one is not the standard solution. We just tested all the problems but didn't understand solution from the problem author. Never mind.

Let the answer matrix be F (the expected steps moving from u to v), the normalized adjacency matrix be E (the probability of one step moving from u to v), the identity matrix of size n be I and the all-one matrix of size n be J, there exists a diagonal matrix G such that F = EF + J - G. If G has been determined, what remains is to solve the equation (I - E)F = J - G.

Since the rank of (I - E) is (n - 1), we cannot directly solve the equation. But we know some additional conditions, such as F_i, i is always 0. What can we do with this condition? We may construct infinite solutions of the above equation by setting the values F_1, 1, F_2, 2, ..., F_n, n freely and then determining other values in the matrix. It can tell us each solution is in the form of F_i, j = FF_i, j + x_j where x₁, x₂, ..., x_n are free variables and FF is any solution, so we can simply apply Gaussian elimination to reduce the first (n - 1) rows and get a specific solution FF. Then, fix the values by the condition F_i, i = 0.

Did I miss something? Emmm... The calculation of G. Actually, I don't know how to explain it easily, but where P_i is the stationary probability (in stationary distribution of a Markov chain) that a random-walking object appears at i. You may calculate the vector P by the equations PE = P and .

The above solution is in time complexity O(n³). However, as you've seen, there exists a solution which applies Gaussian elimination to each (n - 1)-subsets of vertices by divide and conquer. The onsite judges thought participants who have learned this solution could soon come up with the optimized solution, so the time limit is a bit strict. facepalm.jpg

By the way, I tested the divide-and-conquer solution (without setting an epsilon) and it passed all the test cases with 1513ms, while the first one passed with 202ms. Maybe you just need some optimization on CodeForces?

The matrices are similar for all terminals. They differ by only two rows. Thus you use Sherman–Morrison formula to maintain the inverse matrix.

My solution also gets TLE during the contest.

Have you ever tried to solve them independently? I'm not sure about that. But if you solved them by yourself, you might obtain some great experience, won't you?

I have a complicated idea and it runs in time complexity , which may be worse than many others.

First, if there is one type of digit (at most one) that appears at least m / 2 times in the price tag of length m, the only best way is to eliminate this type of digits with other types as many as possible, and thus the cost will be calculated easily since it looks like 00... 0, 11... 1 or 22... 2.

But if no such type of digit exists, we can eliminate almost all the digits. That is, if the length of the price tag is even, we can eliminate all digits, or we have to keep one digit otherwise.

Which digit should be reserved? That digit should meet the condition that, if we remove this digit and split the price tag into two parts, each part must be able to be eliminated completely.

To find such digit, we may define c_i, j as 1 if the i-th lowest digit of the first price tag is j or  - 1 otherwise. For the lowest m digits, we need to find a position k such that and for j = 0, 1, 2. A brute-force solution runs in O(n²), so we need optimizations.

Let s_i, j be . We first pick up all possible k such that s_{k - 1, j} ≤ 0, and then we determine if it is possible to find a digit x at position k such that k ≤ m and s_m, j ≤ s_k, j. Since it is a typical partial order problem in four dimensions, it can be solved by divide and conquer (offline) in time complexity . That is, we regard each position i at (i, s_i, 0, s_i, 1, s_i, 2) and sort them in order of the first coordinate non-increasing, and then, during the process of divide and conquer, we sort them recursively in order of the second coordinate non-increasing, maintain the minimum x in the first divided part with the third and fourth coordinates by persistent segment tree and answer for each position in the second divided part.

However, we only have to check three types of x, so we can use a segment tree (no need to be persistent) to maintain the maximum fourth coordinate in a range of the third coordinate such that this position is obtained from picked positions with digit x. The time complexity is .

Let's assume that you chose any vertex v as first pink node and found an optimal brown node u. It can be seen that moving away from u would make one of its subtrees larger, which won't improve the solution. So we will only move closer to u.

Let's start from the centroid of the tree and call it Pink1. then find a optimal second node and call it Brown. Move Pink1 to the centroid of the subtree closer to Brown and run again. At each step we discard all the current Pink1 subtrees (except the subtree that is closer to Brown) from the potential optimal Pink1. So the number is halved each time, resulting in the complexity .

We (testers) thought it is a notorious coincidence with Balkan OI 2017 Day 2 A. Cats. If you need a solution, just check it out.

The first part of your solution is correct where you binary search on the cost associated with increasing one partition. So, now the problem reduces to solve the recurrence you mentioned optimally. As the above recurrence satisfies quadrangle inequality, you can solve it in O(n) using 1D-1D Dp optimisation. Hence the complexity would be O(n logA) where A is upper bound of cost.

You can see the time limit and memory limit of each problem in Dashboard. When you submit code in a specific problem, you can see the limit in Submit Code as well.