#include<iostream>
#include<cmath>
#include<cstring>
long long int n;
int main(){
    const int k = 256;
    std::string g = "GOOD";
    std::string b = "BAD";
    std::string str;
    std::cin>>str;
    std::cin>>n;
    if( n == 0){
        std::cout<<"0"<<"\n";
        return 0;
    }
    int arr2[4];
    int bit = 1;
    int arr[4];
    long long int l = 0;
    memset(arr,0,sizeof(arr));
    memset(arr2,0,sizeof(arr2));
    for(int i = 3;i >=0 ; i--){
        long long int j = pow(k,i);
        for(int C = 1;C<=255;C++){
            long long int h = C*j;
            if( n >= h){
                l = n % h;
                if(l==0 && i!=0){
                    arr[i] = 1;
                    bit = 1;
                    n = n-bit*h;
                    break;
                }
                else if( i == 0 && n <255){
                    arr[i] = n;
                    break;
                }
                else {
                    arr[i] = n/h;
                    bit = n/h;
                    n = n-bit*h;
                    break;
                }

            }
            else break;
        }
    }

    if(str == g){
        long long sum = 0;
        for(int i = 0,m = 3; i<=3,m>=0;i++,m--){
            sum+=pow(k,m)*arr[i];
        }
        std::cout<<sum<<"\n";
    }
    else if( str == b){
        long long int sum = 0;
        for(int i = 0,m = 3; i<=3,m >= 0;i++,m--)
            sum+=pow(k,m)*arr[i];
        std::cout<<sum<<"\n";
        }
    else;
    return 0;
}

if u have wa 44 just remove one in the cyclic factorization, if there is one.
<=sqrt() + 1   -- bad
<=sqrt()       -- good

Can anybody help?

This was overall a great problems set!

Can anyone give a hint on the solution for "J. Turning Turtles"?
What special property (beside that it's a tree) must one use?
What is the complexity of the intended solution?

Thanks in advance!

1. Use integer calculation for judging if the answer is -1 or 0.
2. Use integer calculation until the last step for the area (an integer-division).
3. Use 'long long' instead of 'long' or 'int'.

Also, here are some cases which might help.

0 0 -1000 0
0 0 1000 1
1000001000.000000

-1000 0 0 1000
0 -1000 1000 -999
2002004004.004004

0 400 1000 1000
-1000 -1000 355 -187
-1

0 400 1000 1000
-1000 -1000 350 -190
0

0 400 1000 1000
-1000 -1000 353 -188
16931680400.000000

-1000 -1000 1000 1000
-1000 -1000 1000 999
31984004000.000000

-1000 -1000 1000 1000
-472 -851 379 1
5800420000.000000

Since input numbers are integers, pseudovector product absolute value will be at least 1 if they aren't parallel, so you can compare it to 0.5 to have bigger margin for double precision error.

When n>10 is a prime, i am writing n=k*3+l*2, where l=1,2 or 3 depending whether n mod 3  = 1 2 or 0. Then I get lcm=3^k*2^l, which is the maximal with respect to all possible divisions of n. However, my program gives WA6. Am I correct?

Thanks!

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.