It could be simpler. Its just check x = 0,1,2,3,4,... 10 and find the coeficients (like you did) and then eval the function over [0, Mod — 1]. AC = http://mirror.codeforces.com/contest/1155/submission/53163325

Thanks!!

Why the answer of problem E for the second sample is 7 and not 6?

If the shops are in : 3, 4, 5.

The minimum distance of node i to any shop is:

Junction 1: Shop 4 — Minimum distance is 6

Junction 2: Shop 3 — Minimum distance is 6

Junction 3: It is a shop — Minimum distance is 0

Junction 4: It is a shop — Minimum distance is 0

Junction 5: It is a shop — Minimum distance is 0

Junction 6: Shop 4 — Minimum distance is 6

Junction 7: Shop 5 — Minimum distance is 2

Junction 8: Shop 3 — Minimum distance is 1

Junction 9: Shop 4 — Minimum distance is 6

Junction 10: Shop 4 — Minimum distance 5

In this way, the answer is 6, isn't it? What is wrong in this solution?

Can anyone explain how to solve knapsack in O(S sqrt(S))?

hahaha No! Neymar >>>>> Messi. (Joke!) :)

Pele > Maradona

KAN

That was not the case.

I tried to hack Mr.Donaldo three times using the following testcase: 5 2 aaaaa

and then received this verdict.

I got Unexpected verdict on my hack in the solution on problem A and receive this result. What does it mean?

When you miss the case n=1 and you don't believe on correctness of your pattern

I think it will be on China !

My solution of E is a kind of greedy and Dp solution. In this problem we have a knapsack problem. The knapsack has a size much bigger than the size of its components. So we can make a greedy approach until the size of knapsack is X, then make a knapsack DP on the rest of components on a knapsack of size X. I fix X = 300 (3*100 ) arbitrarily. A doubt: How we can find the minimum X that we guarantee a optimal solution in this case? :p My solution:http://mirror.codeforces.com/contest/808/submission/27144481

Edit: It is Wrong! Sorry!

oh my god! I am feeling so Stupid! euheuheuh I have no idea about div1 A topcoder! Can anyone explain the DIV1 A solution?

yes! it is !

Let me define it:

f(0,0) = P;

f(0,1) = B;

f(1,0) = f(0,0) + f(0,1);

f(1,0) = f(0,1) + f(0,0);

f(i,0) = f(i-1,0) +f(i-1,1);

f(i,1) = f(i-1,1)+ f(i-1,0);

...

Let DP[u][j][x]= (the set of vertices that the vertex u, on the j-th, x-th state of this function can reach);

Basically, for each edge u->v,w , you must add: Dp[u][0][w][v]=1; then, for each i until (60) for each vertex u for each i, w of the funcion f , you must calculate the Dp[u][i][w];

Remember that we have calculated the Dp[u][i-1][w]! Then , for each vertex v , that you can reach on the state(u,i-1,w) , we have to add the set of vertex that the state(v,i-1,!w).

to implement union of sets efficiently you could use a bitset!

the complexity: O(n^3*log(10^18)).

Your code here...
bitset<501> alcance[61][501][2];
int n,m;
// 0 = P , 1=B
// i-esima string , estando no vertice j, com a string bonita ou nao
// quem esse estado alcanca :) 
int main()
{
    sc2(n,m);
    for(int i=0;i<m;i++){
        int u,v,w;
        sc3(u,v,w);
        alcance[0][u][w][v]=1;
    }
    for(int i=1;i<=60;i++)
        for(int u=1;u<=n;u++)
            for(int v=1;v<=n;v++)
                for(int w=0;w<=1;w++)
                    // se v e alcancado por u com w;
                    if(alcance[i-1][u][w][v])
                        alcance[i][u][w]|=alcance[i-1][v][!w];
                        
                    
                
            
        
    
    bitset<501> estado;
    estado.reset();
    estado[1]=1;
    ll resp=0;
    bitset<501> prox;
    int bit=0;
    for(int i=60;i>=0;i--){
        prox.reset();
        for(int u=1;u<=n;u++) if(estado[u]){
            prox|=alcance[i][u][bit];
        }
        if(prox.count()) {
            bit=!bit;
            resp+=(1ll<<i);
            estado=prox;
        }
    } 
    if(resp>1e18){
        pri(-1);
    }
    else{
        printf("%lld\n",resp);
    }
    return 0;
}

I hope it helps ! Sorry for my bad english!

In the div2E problem it's enough cin and cout to read the input properly. (http://mirror.codeforces.com/contest/779/submission/25044527)

binary search ... imagine that you have a query that answer if the current S has a subsequence T. This "function" is: true true true.... false false false.. You just have to find the last occur of true. You have to find the optimal prefix of the array permutation that answer TRUE on this query :) ! I hope it helps you ! Sorry for my bad english!

sorry , i linked other submission.. the accepted solution that i told is this new !

In C problem , i supposed that the cycle is small. But how should I prove that the length of this cycle is smaller than 100 ? :) my accepted code :

http://mirror.codeforces.com/contest/768/submission/24855247 edited

What is the expected approach for E?

Suppose that we have the rank of the first place of each group. R1 is the greatest rank of group 1 , R2 is the greatest rank of group 2 and so on. Now, we will suppose that R1<R2<R3<R4 and so on. Now, suppose that we have M contestants on each room. We can mantain a DP , that the state is I (the player we are) and J (how players we can skip). The dp count HOW many manners we can arrange the players in each room such that the rank of the first contestant on room 1 is smaller than the rank of the first contestant on room 2 and so on.. On state DP[I][J] -> WE HAVE TO POSSIBILITIES FOR THE PLAYER I: HE IS THE FIRST OF HIS ROOM , and he is not the first of his room; WHEN j is 0 , the i-th contestant MAY be the first of his room. Then: DP[I][J]=DP[I+1][J+SIZE-1] ( THE player I is the first of his room) + DP[i][j+1] ( THE PLAYER I IS the first of his room) ; The base case is: dp[1][0] = > the first player may be the first of his room. DP[lastplayer][anything] = 1; HOW WE assume that R1<R2<R3<R4<Rgroup. we may multiply this answer by fatorial[group].

If j==0, j-1 will access a invalid memory

Dp[i][j]= How many ways do you arrange the contestants , skipping at most j contestants. This DP assumes that the the first contestant of group 1 has a smaller rank that the first contest of group 2 and so on... Then you have to multiply the answer by fat[group] to cover all possibilities: DP[i][j]=DP[i+1][j+size-1]+DP[i][j-1]; sorry for my bad english ;/

I solve D with the 2- pointers technique. Fix the m first "window" ( interval from 0 to m-1). It must be covered by any of this characters. Then, we get the most right and most lexicographically smaller character (on position x). When we get this, we repeat the same problem in the (x+1,r+m-1) window. To do this we keep a structure pont[i] that keep the most right position of character i and update this with 2 pointers. After do that we have to add to the solution all character which is lexicographically smaller than your "bigger character". Sorry for my bad english ;/ My solution: 21297160

awesome tutorial, thanks amd!

Good Job kogyblack! Good Explanation :)

Sorry! You are right! if it has a cycle, we should NOT add 1 to the answer :)

Every connected component of the graph, could be solved independently. Each connected component has at most 1 vertex with ending degree 0 after all (solving optimally) . If the connected component is a simple path or a tree root on a vertex v, we may notice that this component has 1 vertex with ending degree 0. If the connected component is cyclic, starting on any node we can organize the Edges in order to take no edges with ending degree 0. Imagine we have one conected component witch has a cycle and a path or a cycle and a tree or both :) , for example this: 1-2, 2-3, 3-1, 1-5, 5-6; Notice we can turn it into the problema of the cyclic connected componen. For this, we can also pick the vertex with in-out degree=1 and connect it. For example: 1-2 , 2-3 , 3-1, 1-5 5->6; 1-2,2-3,3-1, 1->5, 5->6; In this phase we have the same cycle! Therefore, we can run a dfs for each connect component and verify if it has any cycle. If it has add the answer by 1, if it has not, add the answer by 0.

I use too and I got TLE ;/