oops, sorry I can't read.

Yes, this is an efficient method in , and I prefer it to the following O(n) method: rev[i] = -(MOD / i) * rev[MOD % i] (where MOD  = 10⁹ + 7), and then ifact[i] = ifact[i - 1] * rev[i].

Anyway, is very close to O(n) and much smaller than .

There is a contest in csacademy, and hackerrank. I believe that there are a lot of other contests in other websites.

Nooo, don't. I like the pictures

Well sadly, I also can't understand what you are saying, too..

Whatever, Let me rephrase what I meant. Author claims :

• The problem with only plus operation is easily solvable with fast algos.

• After 4k-th iteration, The problem with only minus operation actually become an instance of "The problem with only plus operation", with input as odd / even array element. So we can perform 4[n/4] operation very fast.

I agree on first paragraph, and pattern shows second is true, but I'm not sure why.

UPD : Ok now I got it. I didn't read the part that we always reduce it to + / even n case. Now we can prove it. I'm sorry, and thank you for the help!

Ha, speaking of urinals: http://www.spoj.com/problems/URI/

And if I'm not mistaken, this is actually exactly the same as Div1E. (I'm problemsetter for the SPOJ problem). Too bad I did not participate in the round :D

Initially you have the size of 1. When you get a subtree of size S you'll make a S * size transition and then you'll make size += S. On the first step, you'll pair the current vertex with all the vertices from the subtree. From the second step onwards, you'll pair the current vertex AND the already counted vertices with the vertices of the next subtree (the number of such pair is S * size). This means that you'll never count any pair twice and the complexity will be exactly the number of such pairs, or O(n^2)

To be pricise,you can calculate the complexity is this way: just a sketch:

 int now=1;
	  	for (k=0;k<v[i].size();k++)
	  	{
	  	  int t=v[i][k];
	  	  for (j=now;j>=0;j--)
		  for (int l=s[t];l>=1;l--)
		    {
		    	f[1][i][j+l]=min(f[1][i][j+l],f[1][i][j]+f[1][t][l]);
				f[0][i][j+l]=min(f[0][i][j+l],f[0][i][j]+min(f[0][t][l],f[1][t][l]));
			}
		  now+=s[t];
		}

s[1]*1+s[2]*(1+s[1])+s[3]*(1+s[1]+s[2])+...=sigma(s[i]*s[j])=[(sigma(s[i]))^2-sigma(s[i]^2)]/2

adding each iteration together,you will find all terms except n^2 will cancel each other So in total,complexity=O(n^2)

Reread editorial for B. Phrases that are closest to formal proof are 'Observe the following picture' and 'Am I the only one whose mind is on the verge of exploding?'. We observe and notice, we don't prove.

Maybe you are right about D. Maybe I just tried to find more examples of strange things in this round and went too far.

We will see card (x, y, z) as cube with coordinates (x, y, z). All our cards form a cuboid with sides p, q and r. Let's count the number of such cards (x, y, z) that there exists a card in our set such that (x, y, z) cannot beat it. For given card (X, Y, Z) from our set all such cards forms union of three cuboids: (y ≤ Y, z ≤ Z), (z ≤ Z, x ≤ X) and (x ≤ X, y ≤ Y). So our task is to find the volume of the union of this figures for all cards from our set.

First cuboid has 'free' x coordinate, second -- 'free' y coordinate and third -- 'free' z coordinate. Let's regroup this 3n cuboids in three groups by free coordinate. How the union of all cuboids in one group looks like? Let's look at group with free z coordinate, for example. z coordinate remains free, and union of rectangles froms ladder-like structure. For every x₀ coordinate there is y(x₀) such that cube with coordinates (x₀, y, z) is in our figure iff y ≤ y(x₀), and y(x₀) is non-increasing function. There also exists non-increasing function x(y₀) with similar meaning. We can build all the functions y(x), x(y), z(x), x(z), z(y) and y(z) in linear time with suffix maximums. That's arrays AB, BA etc. in my code.

Now we want to find the volume of the union of this ladders with one free coordinate. Let's use inclusion-exclusion principle. Now we want to calculate volumes of ladders, pairwise intersections of ladders and intersection of all ladders together.

Volume of one ladder is easy to calculate: it is area of planar ladder multiplied by the legnth of free coordinate. The area of ladder is just sum of y(x) for all x.

Volume of intersection of two ladders is not harder. Let's assume that these two ladders have y and z free coordinates. Let's iterate over x. Then first ladder gives us the range of z and the second gives range of y. Each cross-section with fixed x is a rectangle with sides z(x) and y(x). Sum of z(x)·y(x) over all x is the volume.

And the volume of intersection of all three ladders is the hardest part. Again, let's iterate over x. That gives us rectangle z(x) × y(x), but there is also a ladder y - z. We should intersect the ladder with the rectangle to get the cross-section for given x. There is two cases: rectangle inside the ladder and reactangle has part outside the ladder. In the latter rectangle z(y(x)) × y(x) lies inside the ladder and we should add sum of y(z) for all z(y(x)) < z ≤ z(x) to its area. To get this sum in O(1) we can use prefix sums.

Please refer to my code for further explanations. There are three clear parts each doing what is written here.

Let's suppose each vertex v has its own 1_v and for some set of vertices V. Now calculate the number of iterations of inner cycle in my algo like this: whenever you want to add sz_v·sz_u, replace each sz with corresponding sum of 1 and then open brackets. It is easy to see that 1_v·1_u appears exactly once for all different v, u, so the sum is exactly n(n - 1) / 2.