Nope. Many parts of the problems are written by ourselves and are not real :)

Star India appears to have leaked the episode online through its own website.

Well, problem B killed everyone anyway ;)

Very faster? Seriously?

RIP. ENGLISH

Bend the knee :-P

Placing Daenerys Targaryen's army(#428 B) was very painful , finally receiving WA . I hate her weird choice O:)

When you're just doing the contest*

BooHoo

Dracarys

Valar morghulis.

Rowing.

I miss Tywin ;_*

Dude don't post this shitty big pictures

no i didnt watch it too but i heard its one of the best series :)

I haven't watched it but read the whole plot of this season and now I am giving away free spoilers to people who watch it :v

The long input file result hasn't been calculated yet

And the Andals, and First Men. Protector of the realm...

UPD: Tourist won it in system testing.

king in the north remains, long long live the king!!

There is only one true king !

Ahh the dreaded comment ! :D

haHaa

Verrrrrrrrrrrrrrrrry funny :/

HAHAHAHAHAHAHHAHA :|

It's really good. Codeforces is the only practice website I'm active on and there are lots of problems for you to solve for different skill levels. I recommend going to the problem set tab and clicking on solved to see the most solved problems and starting with those. You can see the types of questions they usually have by looking at previous contests, like this one.

Unfortunately, it isn't possible to publish the persian statements, we are sorry to persian users.

haha...nice one

no one has! XD

蛤？

what the test case 7 ?

Saying this because you couldn't solve a tricky problem won't change anything

Solutions for problem B of even reds failed in pretest 7.

yeah i failed 5 c because i wasn't calculating the probability of choosing the path i was just printing sum(root->leafs) / number of leafs

A bit more productive version: "But I will find you and I will solve you"

Use formatting

Yes, I made a similar hack:

3 10 2 2 2 2 2 2 2 2 2 3

And system sayd me the answer is NO. Should be YES.

Really? It's terrible.

The answer "NO" is correct.

We use 8 "2 - placed" seats for groups of 2.

4 groups of 2 soldiers and 1 group of 4 soldiers remain.

This group with 4 soldiers will use one 4 - placed seat.
Now there are 3 "4 - placed" seats and 4 pairs of solders.
You cannot place them without breaking the rule.

Now it looks like even Um_nik will fail (submission 29384447)

i think i had a very simple sol before:

int sm = 0, odd = 0;
for(int i = 1; i <= k; i++){	
	int t; cin >> t;
	sm += t;
	if(t & 1)
		odd++;
}
if(8 * n >= sm + odd){
	cout << "YES";
}else
	cout << "NO";

is it correct??

I hacked 4 users with this test, but I didn't understand why?

Yes right?

I think many will fail B after the full judging

Ehh, I fail this one too...

What I did was finding the maximal component where each vertex has degree equal to or more than i (1<=i<n) but I get WA on test 5

Find the maximum clique in the graph. Suppose it has t nodes, the result is .

I think this should fail:
1 3
2 2 4

We might have the same idea. Run under timelimit, hope that it converge. :)

I was thinking in lagrange multipliers, what do you mean by clique? is a pentagon ABCDE with a triangle ACE a counterexample?

Yes. Consider solution that distributes x_i liquid to vertex v_i. Suppose there is no edge between v_i and v_j. If we fix t = x_i + x_j and change x_i, then answer is linear function of x_i (because only summand that is could be not linear of x_i is a_ij·x_i·(t - x_i) = a_ij·x_i·x_j, which is zero). So in one of optimal solutions either x_i = 0, either x_j = 0. Now fix any optimal solution with maximum numbers of zeroes. In this solution any vertices with non-zero numbers are connected. So, answer should be a clique.

I proved it with following way:

Lemma. There is an optimal way to give numbers to each vertex as this way: only some vertex v and it's neighbors can have positive values, and every other vertex has 0 value.

Proof: Suppose that you have some optimal way to give values to vertices. For each vertex, calculate sum of values written in neighbor vertices. Find a vertex which has maximum value, and let this vertex v. Suppose we have vertex w != v, which is not a neighbor of v, and has positive value written. Then, we can just add value of w to v, and make value of w 0. This will make better result for problem. It means that all vertices except v and it's neighbors should have 0 value to have optimal solution.

If we use above lemma, we can show that answer only depends on maximum clique by induction.

Theorem: the answer for some graph that maximum clique is K is equal to answer for perfect graph with K vertices.

Proof: 1) K = 1 -> Easy to show. 2) If above theorem holds for some K, it should hold for K+1 also.

By lemma, we can take some vertex v and it's neighbors, and erase all other vertices from the graph. In this modified graph, suppose we can get rid of vertex v and think it later. (It's correct. We can find which value to write in vertex v, only depending on answer on graph without v) Then left graph should have just K-clique. So this graph is equal to perfect graph with K vertices by induction. By adding vertex v again, it becomes perfect graph with K+1 vertices.

:p

How would you organize it so that it's yes? I can't think of a way.

You are wrong. We have 6 2-placed zones and 3 4-placed, 6 two-using groups sending to 6 2-placed, so we have only 3 4-placed zones and 2 2 2 3, we can't put groups on them, cause different groups can't seat with each other (sorry for my poor endlish :D)

It's yes, ofc

My solution passed pretests and it gives YES

UPD: 29391756 passed systests =)

yes the answer should be YES

iterate over the GCD from 1 to 1000000 and find the answer exactly for that gcd and add it to the final answer.

Inclusion/Exclusion + DP.

My code: http://ideone.com/BG4EtW

you need to calculate sum( probability of reaching the leaf * depth[leaf]), instead of sum( of paths to leafs) / number of paths

I fixed it by calculating for each destination the probability to reach there * their length. For each node the probability to reach its children would be the probability to reach itself divided by the number of children (with node 1 being probability of 1). The expected length is then the sum over all of the destinations.

Expectation(node){
   E = 0.0;
   d = 1.0/number_of_children
   for each v in node.children:
      E+= (d)*(1+Expectation(v));
   return E
}

Getting to different ends in the tree have different probabilities.

Consider the input

5
1 2
1 3
3 4
3 5

Getting to 2 have probability = 0.5 whereas getting to 4 and 5 have probability = 0.25 each

*misunderstand

I did that and some inclusion exclusion but have WA4, in any case that sum is k*2^k-1

Yes, then apply Pinex not to count twice some sets {6} in the example 2,3,6.

yeah. kCa = kC(k-a), so you can rewrite it as (k/2)*kC0 + (k/2)*kC1 + ... (k/2)*kCk = (k/2)*(kC0 + kC1 + kC2 + .. kCk) = k*(2^(k-1))

I used Mobius inversion Formula (I knew it was totient) and Inclusion Exclusion for g=1.

BTW The summation is equivalent to k * 2 ^ (k-1)

I derived it in this way -> Binomial expansion is,

Derivating on both sides with respect to x,

Substituting x = 1 on both sides,

Can you please tell me how to get this formula?

For begin I'm too did as you did. Then I solved so: when you went to vertex in DFS you should know probability visits to this vertex, children's probability such: (parent_probability)/(count_children). If vertex is leaf then ans += depth*probability_vertex.

Sum of depths of leaves divided by the number of leafs is wrong. You have to take into account the probability of reaching every leaf (you have assumed the probability of each branch from the root node to be equal, which is not the case, as there is a branching factor at every node, not just the root). The line "In each such city, the horse goes with equal probabilities and it stops when there are no such cities" mentions this.

Is this in problem C?

So {1, 2} and {7, 8} are not neighbours as well... :/

even I thought that.

As it is just a div2 B it has to be under estimated :P

2 2 1