An-other solution : 
It is easy to see that for optimal solution we can choose a subset of leaves of the tree. 
Traverse from the leaf nodes (size == 1 and number != 1) upto the node 1. This will give you how many (if any) bad roads a leaf node can cover. To avoid timeout, mark the visited nodes and traverse only upto a marked node. But this may give wrong answer in cases like this : 
4
1 2 2
2 3 1
2 4 2
To avoid this traverse the leaf nodes in decreasing order of the number of bad roads it covers.
Edit : 18728599

distance from 2 to 8 is 32 while a[8] is just 24

I am curious..how would you find a similar problem as that on SPOJ, on any other online judge?

What do you do... 50 push-ups for every Accepted ?

In case x % φ[M] is equal to 0, A^0 % M will become one, which may not be same as A^φ{M} % M

e.g. (2 ^ 0) % 10 = 1, (2 ^ 4) % 10 = 6, phi[10] = 4;

Even if you would have given the value of n around 10-15 instead of 1 with big a[i]'s, your hack might be successful.

Obvious answer — fast servers ( > 1e9 cycles per sec). There have been many posts/comments regarding this.

Return on line 14.

Very unlike last year.

Please don't use your best weapon.. give dogs at least a chance.

Dogs are the added difficulty participants need to overcome this year.

I accidentally deleted my input0 for 1st problem, so when I downloaded it again, it triggered input1 for the problem, so two incorrect solutions. Can anyone expain this? Anyway I finished with 1004 missing the cut by 20 seconds :(

There is no option for English alphabet captcha in account recovery :(

Did this happen as a result of Errichto's Blog?

I think there is an O(n) solution.
First you can find all the opening parenthesis for closing ones using stack in O(n).
Use array d[n+1] for keeping the count initialized with 0. 
Then for every opening closing pair with opening at i and closing at j set 
d[j] = 1 + d[i-1]. This can be done for all indices from 1 to n in O(n). 
Finally for answer accumulate all d[i]'s.

For example s =    ( ) ( ( ) ) ( ) ( ( ) ( ) ). 
            d = {0,0,1,0,0,1,2,0,3,0,0,1,0,2,4};

So, the answer will be 14.

No. What you are describing is of-course of the order O(n^2*(log(n)), But the essence of finding the pattern to be added to the result (by result i don't mean any particular r[i] but the whole result array), is that you can update array r for any a[x] in log(n) time.

Each number in the input array will add to some indexes of r[] in a certain way. You can see that from given example in the question or generate input of your own to see. There is nothing more to the problem than that. After that you can use any interval query/process data structure.

I solved this problem using fenwick tree. If r[n] is the result, you can figure out for each number in input array which indexes of r it affects. Each number in input array will form a pattern which can be easily processed and queried by fenwick tree.

Another is to correct someone's grammar, (lost — lose)

I saw your submission history, you have hardly solved any Div2C, let alone Div2D & Div2E. Nothing gets you out of your comfort zone like solving difficult problems. Use a2oj or directly solve C,D,Es from problemset. See other's solutions, read editorial, ask questions if you cannot. Have fun :).

My first dfs-order problem was this one. It has a really great editorial explaining how sub-tree can be converted into subarray using dfs, for update and query using segment/fenwick tree. You can easily understand and solve your problem after reading the editorial.

why would you use coordinate compression when 1 <= ai <= 10^6 ? 15606407

I think hashing might be a better option. Calculate forward and reverse hashes of each, then for each string, you can count how many hashes of reversed string are there.

This problem is quite similar to DQUERY whose O(nlogn) solution is explained by goo.gl_SsAhv here. Also, I just found out that this solution by nhap96 uses same technique (there might be a little difference). Editorial is bit difficult to understand.

I wish to be a fake Legendary Grandmaster.

see this blog You can also go to PROBLEMSET ans click on any tag to get all the problems related to that tag.

Codeforces is very fast. It can process more than ~1e9 operation per second.

This post was made for handle and color changes last year and i think it was 2-3 days after beginning of new year(2015).

remove all the nodes from the tree that are not marked and not between two marked nodes.

I was hoping to participate in my first Div 1 contest tomorrow :(

The contest could be scheduled at 17:00 MSK (19:30 IST) so that it would end exactly when cook-off begins.

you can tap the little blue triangle at the top of the submissions to search for something, in this case you can search accepted to see all accepted solutions. But there is a problem as it shows results for only that page i.e. you have to go to every page and search for the result. Something should be done for searching results from all submissions.

If s is global the s.size() == final.size() will follow only once. make s an argument of the function and also you should check the function for every position of the matrix. code. ( why is n 8 instead of 5?)

Ok, That makes sense.

I guess if they had 400 t-shirts they would give 1 each to both division's 200 toppers. But they only have 200 t-shirts.

I think sieve runs faster than this code.

sieve — 4.05 s

your code — 6.21 s

I think i can relate to it.

Not reading whole problem, or reading it incorrectly is a major issue for me. I don't know what happens during a contest, so i got three WA in problem A.

2C becomes really simple if you add equilateral triangles on two opposite sides of the hexagon.

Can anyone explain Haghani's solution of problem DIV 2E/1C ? Its so simple and elegant but i don't get how it works.

how do i fix this?

When tourist said his team did not feel any pressure for the world finals i thought OK.. But then querty787788 went ahead and registered for this contest as if he has nothing to do tomorrow. Let's see if he actually participates.