Be careful, the input numbers are float, though sample and all tests here have only integer numbers. It appears first at <= 6th test.

wa4 have test n=1 and some m
if u use dp and u write in your massive some int, when u write, u delete int and create new ints. But if u have n=1, u now answer for every for n=1 and when u use dp its write 0, it enters zero instead of the answer you wrote down, although there should be one in some cells

Just curious did anyone managed to pass the time limit
using binary search + rolling hash or the test data are
specially designed to be solved in time only by an efficient suffix tree/array implementation?

please answer to me.

#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.