5 problems, 2 hours, see russian version.

Why do people keep asking this? Do you prepare yourself somehow based on the number of problems?

i don't agree with you :)

you mean "Is it rated?" but in another style xD

You can register for both divisions lol.
UPD: fixed

You are div1 in your soul xD

UPD: Roses are red, France is on West, you're again in div2 contest :(

yeah, I guess... "We wish you good luck and high rating!"

Yes!

zeliboba I think the time you mention here is not the same as the time on the codeforces page, can you edit/clarify?

Yes

No for sure.

It's not matter for you and me and all other coders that should participate in Div 2 :) but I think when difficulty of them are the same It means that u should just read all of them and chose a problem that u think u can solve it

Itachi was smart :|

have a nice night :)

Here you can find old years AIM Tech rounds:

http://codeforces.com/contest/709

http://codeforces.com/contest/624

http://codeforces.com/contest/572

They wrote div 1 C, D, E are pretty much same difficult, so for a div 2 coder the div 1 C problem will be harder than usual.

That moment when you want to get the A

about AIM Tech rounds

How do you know what's typical here? =)

ok now im your first friend

"Ctrl + R" also good)

Len hacked "Diversity"

Try clearing your cache, it worked for me.

click room --> double click on the score of a solution --> click hack button .

I was having the same problem.

I guess just a n>2000 random integers.

Windows rand() is up to 32768. 11 WA for me here.

We can try 1000 times take random index and after all, we can go from biggest number which less than x on list. There is big probability that we can find at least 1 number in range [index_of_answer-999,index_of_answer], so we can find it.

Not sure what your solution is, but I went from WA3 to pretests passed by noticing that just finding a minimum cut in the graph with cap_uv = g_uv?1: INF isn't enough since you might have a g_uv = 1 edge going from the T-side of the cut to the S-side of the cut. If you ignore this, you might get a flow that is valid, but not maximal. If that makes any sense.

EDIT: Specifically, my final solution was:

• First, cover the graph in paths from s to t covering each g = 1 edge. Doesn't matter how, if you have an edge (u, v), just find some path from s to u and from v to t through g = 1 edges. Add 1 to both the flow and the capacity of all edges on the path.
• Create a flow graph. For an edge (u, v) with g = 1, we add an edge with capacity 1 from u to v and with capacity INF from v to u. If g = 0 we add an edge with capacity INF from u to v. Find some minimum cut in this graph between s and t. Increase the capacity of all non-cut edges by 1.

Finally, add both flows together. The idea behind the flow graph is that we find to find some cut using a minimal number of edges, but we can only use edges with g = 1. Additionally, we can't have any edge going from the T-side of the cut to the S-side, since then the flow is not a max-flow, since you could push back flow through this edge (in reverse). Hence the reverse INF edge.

Exactly rand() didn't work, but random_shuffle did as I noticed from solutions which passed pretests...

I spent 32 minutes trying to figure out what the hell is going wrong. Ans it's not even the first nor the second time I've done it with the same exact problem...

rand()/double(RAND_MAX)*n passed. see 29761972

I dunno, i picked 1500 and it passed pretests, not sure about systest.

rand() generates numbers less than RAND_MAX which apparently is 32767 on codeforces. (on my machine it's 2147483647)

No, such a thing doesn't exist (assuming antagonistic test case) -- The main idea is that if you query for 1000 times, you may get results from the smallest 2000 numbers, and if x is among the largest 5000 numbers, this gives you no information about the larger part of the linked list at all.

So even deterministic solutions that pass systests are probably just "unpredictable" enough to pass off as random.

The order of transformation matters since you are deleting edges (and parent/children relationships in the subtree flip really often).

If my logic doesn't fail me, the way to solve this question is:

For each subtree of the centroid(s), transform such that a node is adjacent to all other nodes in the subtree and is connected to the root. This gives distance 2 between all other nodes and the centroid. This also can be done in 2n operations.

can you explain me what " squared distances " mean. i cant understand that and of course i didnt get the examples that made me very confused in the contest :(

You can do smth like this:

unsigned long long curPos;

curPos = rand();
curPos <<= 15;
curPos ^= rand();
curPos %= n;
curPos += 1;

Oh the same.

#if RAND_MAX <= 32768
#define rand() ((rand()<<15)+rand())
#endif

I was hacked even though I used srand(time(0)), I'm not sure if this is fair :(

I think srand(unsigned((long long)new char)) is better.

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

I checked using custom test, (long long)(pow(2, i)) = 2^i for all 1 <= i <= 50. But I hacked some solution that didn't round it to integer.

Those using pow() may fail when the value becomes large (over 2^53), but even for the largest test cases they still remain smaller than 2^50 meaning pow() could reasonably work.

srand(time(0)) re-seeds the generator with the current time. Assuming your solution is passing in < 1 second, it means that it will always re-seed with the same time, so your myrandom will just generate the same number over and over.

Are you sure that value doesn't generate the same thing over and over again? time (0) gives the time in seconds afaik, so I think that reinitializing each time with what seems to be the same seed should give the same number. I think that if you used srand (time (0)) in the main, just once, it've worked just fine (though I'm not sure).

You used std::rand(), which generates numbers only up to 32767. It wasn't a nice move from the authors, they could easily make the constraint N <= 30000.

Case s = 1, t = 3, e₁ = (1, 2), e₂ = (2, 1), e₃ = (2, 3), g₁ = g₂ = g₃ = 1 is a counter example.

e₁ cannot have max flow.

I believe that the key is to note that any edge contained in a (flow) cycle cannot be saturated in a maxflow. (Intuitively, if we have capacity to waste on making flow go circles, you cannot be the bottleneck). Finding edges contained in a cycle is easy, especially since m<=1000.

So we forcefully remove such edges from our bottleneck consideration by setting them to capacity 1000.

Now we find the mincut of the resulting graph (with all other edges weight 1). For any one such mincut, we set those capacities to be 1 and all other capacities to be 1000 for the output.

Did I miss other details?

Check out this test

5

3 1 2 5 4

Answer is

2

3 1 2 3

2 4 5

Consider current postion of an element and postion of the same element in sorted array as two nodes and make a graph with edges curpos->sortedpos. Now, you have to find all connected components of the graph. Here's my solution Solution