Thank You, I will check this.

It's expected value not variance.

Why my code for E is so slow? http://mirror.codeforces.com/contest/895/submission/32688252

How to solve D? I have only 2^20*50*20 solution.

What is the name of your team?

Graph of masks and bfs from each mask from input. Graph contains the edge if two masks are different only on one bit. The answer is a vertex with the biggest distance.

So I did but got tle on test31.

Oh yes thx.

I had WA on pretest7 7 times.

I have if(a != b) graph[a].pb(b)

What is wrong with my solution for E? I'm finding all cycles and trees. Answer is 2^(number of cycles)*product of sizes of trees. https://pastebin.com/FShyKDWw

Yes, but with priority_queue is easier.

I've made simple dp on tree in E but fail. I assume that because of long long overflow. Is that good solution?

I think that number of states is less than number of compositions of log(1e9) because when we divide by p^k than we subtract k from max{k1,...,ks}. Am I right?

I think it is. For numbers bigger then 2 is easy but I can't show that for 2 number of states is small.

What with states for 2?

When we have 3 leftmost points there must be a line which is going through 2 of those points.

thx

sort what?

How to solve div2 d?

Now I see. You maintain the ends of diameters. When You find new longer diameter you just update sets. It's fast because you can change set for vertex x only when it was a new end of bigger diameter.

Maybe you should read about jump pointers.

Let mex of the array after (a xor x) be M than after M xor x you get a number which cannot be in the oryginal array.

The same solution but you don't need trie. Normal sorted array is enough. You just make lower_bound for every bit.

Is O(nsqrt(maxval)) good enough in c?

I see only that we can change ai+bk-i to 1,00000001^ai*1,00000001^bk-i and now it more similar to multiplication of polynomials.

You can use one substring several times cabwabgab

c-> ca > cab > cabw > cabwab > cabwabg > cabwabgab

What with this test?

gabbbbbbbbbcwabbbbbbbbbc

DP[i][a][b] — minimal number of steps for sufix i...n if in clipboard we have substring a..b

Maybe you should write about your idea.

Now I see They are not changing into a star. They are changing into centroid with stars.

I think that there are graphs which cannot be changed into start. Degree of centroid in tree is unchangeable so if centroid don't have degree equal n-1 than we would never get a star.

bad solution

The last one.

I think that rejudge is still unfair. I usually start with problem D. I was sure that my solution is correct so I tried to find a bug and ultimately lost 2,5h.

I'm not sure if this round should be rated.

I spent 2,5 h.

Oh the same.

I've made the same and have 16 ans on pretest6.

I've gotten 16 ans in D. I choose y random numbers and start. After that I choose the biggest number less or equal x. Then I go 1999-y-1 times to next number. What is wrong with this solution?

I have AC.

Maybe I didn't understand the problem but in your solution vertex 1 don't have any edges.

I think so. When we have odd number of 1 then sum of degree is odd and this is wrong. When we have number of 1 even then we can match vertices with 1 but we are looking only on dfs tree. When you find partner for some 1 then you can change edges on path between those vertices 0->1 and 1->0.

what with 1?

Only when there isn't -1 and number of 1 is odd we can't find subset.

I think that it's possible to solve B with HLD but you can use normal max-seg-tree.

Where is editorial?

It can't work because you cannot count dp with only those informations. You don't know what is best pair. Maybe optimal solution is take one number power of two and next one power of 5.

OK, I had a bug.

How to solve D?

I did DP[i][k][s] — a maximal number of 2 in prefix [1..i] when we take k numbers and product of those numbers has s factors equal 5.

1 <= i,k <= n , 0 <= s <= 5000

It was too slow.

I was asking for each bit. Then answer for some bit must be y or x xor y and then I have numbers which have only one y. For first number I just make binary search on numbers with this bit.

Yes I have O(knlogn).

Normal max-segmenttree was enough.

thx

Why the answer is 5^(n-b)? 5^n — number of all possibilities. 5^b — number of all vectors in vector space. Why when one vector has k representations then every other must have k?

I think that vertex which is common to all paths between a,b,c is one of the lca(a,b), lca(b,c), lca(a,c).

When you find this common vetex x you can print the max length of xa,xb,xc.

28845144