Head-on solution have complexity O(2^40)=O(10^12). It's very slow. How do it faster?

Why is the correct answer in the example "uhhdud" and not "uhdudh"?

in terms of lexicographic order, this combination is closer to the original data.

Let a[1], ... , a[n] be the sequence written by the friend and pref[i] be the xor of the prefix a[1...i]. Then a question (l, r, t) (which means the parity of the number of ones on the segment from l to r is t) can be represented as (pref[r] xor pref[l - 1] = t). Let's build a graph with two vertices for each prefix (thus, there will be 2 * (n + 1) vertices). Using compression, we actually need only at most 2 * m vertices (where m is the number of questions). Let the vertices corresponding to the prefix i be f0(i) and f1(i). Now, let's add all edges f0(i) ~ f1(i). For a question (pref[r] xor pref[l - 1] = t) if t = 1, we add two edges f0(l - 1) ~ f0(r) and f1(l - 1) ~ f1(r), else if t = 0, we add edges f0(l - 1) ~ f1(r) and f1(l - 1) ~ f0(r). To check whether a sequence of questions from 1 to x is achievable we just need to check whether our current graph is bipartite. This can be done by simply doing dfs after each question.

Though O(N*log(N)) and O(N) both gave me 0.068 timing, it's a good testdata to write such code, would matter if N could be up to 10^6. Also this solution with O(1) stepping may additionally report number of ways to achieve minimal result.

The structure is doubly-linked list of available amounts (always strictly ascending), each of which is non-empty doubly-linked list of characters with that amount. This structure allows to query for max and to change amount of single character +-1 at O(1).

Could anyone who solved it share the idea?

My solution was: iterate over all vertices i. Fix each i start bfs, so you get a tree (rooted in i). Find it's diameter (from the farthest node v from root i start another BFS and find the farthest node u from v. The distance from u to v would be the diameter).

Across all the diameters find the minimum, that would be the answer.

This solution got WA 8. After random_shuffle() on adjacency lists I've got WA 17.

Now repeat this solution 100 times and you get AC.

So my question is, what is the solution?

att

hi,

im trying to solve this problem and would like to get tips in the right direction of solving this problem.

would a grapha matching solution work? or perhaps a minimum cost flow solution? or anything else?

thanks in advance.

I spent a lot of time on this problem.
For those who want to fit the time limit I recommend reading A. Brandstƒadt, D. Kratsch "On partitions of permutations into increasing and decreasing subsequences".
Also M.D. Atkinson "Permutations which are the union of an increasing and a decreasing subsequence" is very interesting to read but not so helpful for this particular problem.

-1000 0 0 1 1
My solution do not deal with testcases like this, yet still was accepted. Am I missing something? For those who wonder, my program gives 9079565065540428013 on this testcase lol

Simple solution, but try to optimize it!
If you want better explanation (myironmistake@gmail.com)

Example - my submission 9959592 (problem 1990 - Podracing). It's not about input or sorting (checked everything), but GCC gives 0.5 sec where VC++ gives 0.171 sec (it was 0.9 sec on the verge of time limit when everything was double). FPU is just a guess because I faced situations before in real projects when GCC used FPU and VC++ used SSE or something else and was way faster, there was some command-line switch like -fdisable-fpu or -fdisable-387 or something like that for gcc (can't remember now), probably it will help.

The original version of the statement was unclear, and not all the limitations were described in the input data format.

Both English and Russian version of the statement were updated.

My algorithm is linear, except the quicksort procedure.
It gets TLE at Test #24.

What happened?
I have checked the program multiple times.

Thanks.

When you count invM*rj*M mod M*pj you can get number > int64. But you can use this: a*b mod a*c=a*(b mod c). In our situation M*(invM*rj mod p[j]).

Can somebody tell me how they passed test nr. 2 (or give me some good test cases)?

I have a solution in O(N*M*log(N*M)) using suffix array and I can't find the bug.

Thanks

Edited by author 16.09.2010 22:39

Hi everybody!

I solved this problem, but my algo is O(n log n) and it works 0.14 seconds.

Idea of my algorithm is to find two vectors witch sum is not greater than L and change them on their sum. It it possible to prove that such two vectors exists if there are more than two vectors in set. Do this procedure while we can find such two vectors.

But many people solved it much better... I want to know this solution.

Can anyone explain sample test? I have smth like this:
Case n = 4, k = 1:
0000
0000
0000
1111
Case n = 4, k = 2:
0000
0000
0001
0111
Case n = 4, k = 3:
0000
0000
0001
1011
Case n = 4, k = 4:
0000
0000
0001
1101
Case n = 4, k = 15:
0000
0000
0011
1100

Who know how to solve it. I think all the varians will be
4^(9 + 7 + 5 + 3 + 1) = 4^25 when n = 10. So i cannot count from 1st to kth variant