One can solve the problem using greedy algorithm: if we can skip x minutes at current moment without skipping any good moment — we do that, otherwise — watch another minute of the film.
In this task you must find for every string in the text the pair containing that string, and from two strings of that pair output the shortest one.
It can be easily proved that, if two points from statement are placed on different sides of some line, this line will be crossed anyway. So, all we need to do is to cross all these lines, so the answer is the number of these lines.
To check if two points lies on different sides of a line one can simply use its coordinates to place in line equation and check if these two values have different signs.
Solution complexity — O(n).
Let's numerate all the songs and seconds starting from 0.
Problem will be solved using DP approach. State will be described by two integers (i, j): dp[i][j] is probability of that we named exactly i songs, and the last named song was named exactly before j'th second (after j - 1 seconds). dp = 1 obviously.
To make a move from state (i, j) to state (i + 1, j + k) (1 ≤ k < ti), we must name the song exactly after k seconds its playing — probability of that is (1 - pi)k - 1·pi.
To fixed state (i + 1, j) sum of that moves can be represented as . Simple calculation of this value for each state gives O(nT2) complexity, so one must notice, that this values can be calculated using two pointers for fixed i (in common case it represent a segment with ti length) for every j in time O(T). This way calculating this type of moves takes O(nT) time.
There is also a move to (i + 1, j + ti) and a move from (i, j) to (i, (j + k) = T), when we couldn't name current song in time T. This types of moves is calculated with O(nT) too.
Solution complexity — O(nT).
We will divide only by prime numbers.
First, let's build a graph, where each of n numbers have own vertex group:
Find all prime factors of current number. Every factor will have its own vertex in a group, furthermore, if some factor p has power of ai in current number, it will have exactly ai vertexes in group.
The number of vertexes in such graph is .
Now we will make edges in our graph: edge between two vertexes exists if and only if there is a good pair (given in statement) of vertexes group numbers and the prime values of a vertexes are the same. That means that we can divide that group numbers by that prime.
The number of edges is .
Good pairs are given the way that our graph is bipartite. After finding maximum matching in this graph we represent the way of doing operations as described in the statement.
As soon as solution is using Kuhn's algorithm, its complexity is . One could notice that some of the edges are useless and reduce it to .
The solution of a problem — 60 (LCM of a numbers from 2 to 6) segment trees.
In v'th segment tree we will hold for every segment [l, r] the next value: minimum time needed to get from l to r if we start in a moment of time equal to v modulo 60. Using these trees' values it is easy to quickly answer the questions, carefully changing the trees' values.
The problem is solved using DP approach dp[i][mask] — the number of ways to paint first i blocks of a ladder the way that the last layer of vertical edges is painted as described in mask mask. This could be easily recalculated using matrix M[mask1][mask2] — the number of ways to paint horizontal edges between two neighbour vertical layers painted as represented by masks mask1 and mask2.
For fixed i we have wi layers, so this matrix must be multiplied by itself wi times, which can be quickly done by binary-pow algorithm. After that this matrix is simply used in dynamic described above.
Solution complexity — .