Everything that you needed to do — solve some similar cases.
You need to check the following cases:
Home the first shop the second shop home
Home the first shop the second shop the first shop home
Home the second shop home the first shop home
Home the second shop the first shop the second shop home
First of all, you should read the statement carefully. Then, for every element 1 ... N create a list of integers from what we can get this number.
After that you have to check some cases, before that create a special mark for answer Ambiguity:
Let current element of the given array is bi
- If two or more elements exist from which it's possible to get bi, then use your special mark that answer is Ambiguity
- If no elements exist from which it's possible to get bi, then print Impossible
- If only one element exists from which it's possible to get bi just change bi to the value of this element
Finally, if you marked your special mark then print Ambiguity, else print Possible and correct answer.
Let's take a minute to see how the best answer should look like.
Let Hi be a sorted sequence of hi. Let E — set of indices of the last elements of each block. Then e E, first e sorted elements of sequence hi are equal to the first e elements of the sequence Hj.
So, it is not difficult to notice that the size of E is the answer for the problem.
Firstly, we need to calculate two arrays: prefmax and suffmin, where prefmaxi — maximum between a1, a2, ..., ai, and suffmini — minimum between ai, ai + 1, ..., an.
If you want to get the answer, just calculate the number of indices i that prefmaxi ≤ suffmini + 1.
First of all, let's solve this problem for n ≤ m, and then just swap n and m and print the answer. Important! Not to print squares twice!
We can use this formula for fixed n & m (n ≤ m) for calculating the value of x.
Using the sum squares and the sum of the first k numbers we can easily solve this problem.
Getting 6x = 6n2 * m - 3(n2 + n3 - nm - n2) + 2n3 - 3n3 + n = 3 * m * n2 + 3 * m * n - n3 + n
As we solved this task for n ≤ m the 3n2 * m = ≈ n3, it means that n is not greater than .
The solution for this problem is dynamic programming.
Let froot, mask is the number of ways to build a tree with root in vertex root using vertices from the mask mask and all restrictions were met. For convenience we shall number the vertices from zero.
The answer is f0, 2n - 1.
Trivial states are the states where a mask has only one single bit. In such cases froot, mask = 1.
Let's solve this task recursively with memorization. To make the transition, we need to choose some kind of mask newMask, which is necessarily is the submask of mask mask. Then we should try to find new root newRoot in mask newMask. Also, in order not to count the same tree repeatedly impose conditions on the mask newMask. Namely, we shall take only such masks newMask, in which the senior bit (not in charge of the root) coincides with a senior bit (not in charge of the root) of the mask mask. After that, you need to check the fulfillment of all conditions to the edges and to the lca. If everything is OK, update . Where means xor.
What about checking lca, it's possible to do it in time O(N2) — previously memorized lca for each pair or in the worst case in time O(Q) just iterating through all pairs of vertices, for which some vertex v is lca.
Time: O(3N·N3) or O(3N·N·Q)