Which OpenCup login do you use?

Same problem again, 15 minutes till contest!

F: realize that vertices in L(L(G)) correspond to pairs of adjacent edges in G, and edges in L(L(G)) connect pairs that have a common edge in G.

For each edge e in G, consider pairs including e. Can you find how many connected components these pairs would be forming at the moment if we ran Kruskal's algorithm on L(L(G))? If you can, then you know the contribution of e to the result.

B: greedy. Very roughly speaking, you want team A to beat team B on penalty and, alternately, team B to beat team A on the number of problems (or vice versa). How would you achieve that?

How to solve I. I could realise that we need to find scc's in graph where i->j if j is preferred over i. And take problems from sink onwards. How to construct them fast. Or is the idea totally different?

Is the multipoint evaluation and divide and conquer on the tree required in the expected solution? I didn't find any more clever way to solve it.

Let f(i, x) be the length of LIS of a₁, a₂, ..., a_i that contains only integers up to x. Similarly, let g(i, x) be the length of LIS of a_i + 1, a_i + 2, ..., a_n that contains only integers larger than x.

For each i, you want to find the maximum of f(i, x) + g(i + k, x). You can maintain a segment tree of these sums for all x, then moving i forward by 1 can be done with O(1) modifications.

Там интерактор против тебя играет.

Если хорошо разобраться в устройстве интерактивных задач, то можно знать, что интерактор может брать данные для теста одним из двух способов: 1. Считать из входного файла 2. Сгененировать первоначально, а затем модифицировать в зависимости от запросов участника.

Фраза "не выбран заранее интерактором" сбила меня полностью: ну, раз не выбирается интерактором, значит считывается из файла.

Just some typical tricks. Let A(x) be the GF of numbers. .

The answer should be

The last four terms can be calculated by brute forces. The time complexity is O(n³).

The first term can be calculated by "meet in middle". This part is .

Consider 10 lines that pass through two points. Roughly speaking, for each halfline, we are only interested in the direction of the halfline relative to these lines. Thus, essentially, there are only 20 choices for each halfline, and we can brute force all 20⁵ combinations.

The only problematic situation is when we choose the same direction for multiple halflines. In this case, if we assign the same directions for k halflines, the probability that these halflines are disjoint is 1 / k!, so divide the probability by k!.

You can participate in the Open Cup round.

I don't know if there exists an easier/faster solution. A number is secondary, if and only if it has no subsequence equal to any number in 2,3,5,7,11,19,41,61,89,409,449,499,881,991,6469,6949,9001,9049,9649,9949,60649,666649,946669,60000049,66000049,66600049. Just match these numbers directly(in your digit DP). We will get a huge number of states, but only about 150000 are reachable, so we use a DFS to find them.

Oh maybe I've got it.

Consider a simple dp: $$$dp(i,l)$$$ means the number of tuples $$$(i,i+l-1,...)$$$. To calculate it, we need to know if $$$[i,i+l-1],[i+l,i+2l-1]$$$ have no more than 1 different position. If so, we call $$$i$$$ is good for $$$l$$$.

We assert that good positions form $$$O(\frac{n}{l})$$$ ranges. To find them, we use a method like what we do in BOI2004 Repeats(SPOJ687). We want to calculate LCP of 2 substrings allowing Hamming distance of 1, so use a suffix array to calculate LCP, ignore the first difference, and calculate LCP again. Then just do something similar to convolution.

After finding these ranges, you can use segment tree or std::set to calculate the answer. The complexity is $$$O(n\log^2 n)$$$.