Take the LCA of all blue nodes (bLca) and the LCA of all red nodes (rLca). Now iterate over every blue node b and if rLca is on the path from b -> bLca, then you can say for sure that you can't disconnect the blue and red nodes (since b has to cross over rLca and every red node also has to cross over rLca).

Do the same logic for every red node (check if bLca is on the path from r -> rLca) and if that occurs for any blue or red node, the answer is no, otherwise yes.

Here's what I did:

Find the lca of the red set (say, u) and the lca of the blue set (say, v). Note that all red nodes are in the subtree of u, and all blue nodes are in subtree of v.

If u = v, obviously it's not possible.

If u is ancestor of v, then check whether v is ancestor of any red node. If yes there's a problem, if not it is possible.

Similar case for v being ancestor of u.

If none of the above (so lca(u, v) != u or v) then it's possible.

How did you solve G?

You move in a spiral path!

In each move initially you keep painting new b squares. So initial uncoloured= a*a-b*b.

Also finally you will be left with a a%b*a%b square in middle while in spiral.

so in first type of move... (a*a-b*b-(a%b*a%b)) cells are covered with b per move.

Then you can cover the middle of the spiral in a%b moves,

My code...
void solve(){
	lli a,b;
	cin>>a>>b;
	lli left=(a%b);
	a=a*a-b*b-left*left;
	cout<<(a+b-1)/b+left<<endl;
}	

Move in a spiral inwards, instead of zig-zagging down.

A small case where zig-zagging fails is 5 2 — you get 12 while the actual answer is 11.

To (kinda) see why spiralling works, look at it this way — in each move, try to maximize the number of new squares you colour. For a while this will be b with both methods, of course, but when you spiral it reduces from b only when you reach the absolute center, whereas when zig-zagging you hit this for the entire last row.

Not exactly a proof, just some intuition of why it might work.

Problem G is actually not difficultest.

We can think about binary tree that each question divides into two sets (left child = "yes" person, right child = "no" person).
Let $$$d_1, d_2, d_3, ..., d_n$$$, the depth of binary tree with $$$n$$$ leaves. Here, we should minimize $$$a_1 d_1 + a_2 d_2 + ... + a_n d_n$$$. If the minimum value is $$$Z$$$, then the answer will be $$$\frac{Z}{a_1 + a_2 + ... + a_n}$$$.

Assuming $$$a_1 \geq a_2 \geq ... \geq a_n$$$, the optimal answer will hold $$$d_1 \leq d_2 \leq ... \leq d_n$$$. Then, we can say that node of person $$$l, l+1, ..., r$$$ will divide into $$$l, l+1, ..., k-1$$$ and $$$k, k+1, ..., r$$$.

This observation will turn to simple DP problem, where recording $$$dp(l, r, d)$$$ the minimum sumproduct of node $$$l, l+1,..., r$$$ and current depth is $$$d$$$. The time complexity will be $$$O(n^4)$$$ and it passed.
Also, if we think little more, we can erase $$$d$$$ from dimension in DP and the time complexity will be $$$O(n^3)$$$. (Sorry, this $$$O(n^3)$$$ solution was false...)

P.S. Similar to Optimal Binary Search Tree Problem, this problem can be solved by $$$O(n^3)$$$ with Monge DP speed-up.

No. Better ask your questions here. Someone will answer.

I am pretty confident that I solved problem E with different way to other people.

Let's think about directed weighted graph $$$G$$$ with $$$m+1$$$ vertices, where vertices numbered $$$0, 1, 2, ..., m$$$. We will add edges as follows:

• We will add edge from $$$a_i-1$$$ to $$$b_i$$$ with cost $$$1$$$.
• We will add edge from $$$j$$$ to $$$j-1$$$ with cost $$$0$$$. ($$$j = 1, 2, 3, ..., m$$$)

I think this is the simplest solution:

It's pretty clear that the greedy strategy works. Say the lowest id function you need is id x. Consider all intervals that contain x. Of those, include the interval which ends latest.

To implement this efficiently, sort the intervals by their start time. Now process all intervals which contain the next program you need and choose the one that ends latest. You need just a few integers for state: the current interval you're considering, and the next program you need. This runs quickly, just a sort in O(nlogn) and a linear scan.

You have to guess one of 4 people in 2 questions in worst case. You must ask the first question about any two people. With any other strategy, there could be a situation when 2 questions are not enough.

In C, note that every number we mark is of the form $$$0+1+2+...+i = i(i+1)/2$$$, modulo p.

If you substitute i = 2p, this is 0 (modulo p), and then the pattern just repeats because 2p+1 is 1 mod p, 2p+2 is 2 mod p, ... so you won't mark anything new from there.

L is just geometry — since the circles are guaranteed to have exactly 2 points of intersection, the region of intersection is going to look something like a lens (bloated towards one side, maybe, depending on the radii). The point you want is the midpoint of the line joining the top and bottom of this 'lens', and the radius is the distance of this point from either circle (note that any point on this line will be equidistant from both circles)

You can iterate over all possible permutations of result (RGB, RBG, GRB and others).

For each permutations next greedy approach works:

• color 1 to the first deck;

• color 3 to the second deck;

• color 2 to the second deck, if there is only color 2; otherwise to the first deck.

After all cards were processed, you need check that the first deck is consistent (it should be exactly 1...12...2).

I thought K is top2 or top3 easy problem (along with I), but all participants started chasing yellow guys who solved problems in more or less alphabetical order. I think they just didn't read problems in the end till 2nd hour.

You can represent every Jedi with the sum of it's three parameter to use the dark force

Then you should represent it again with the sum of the two smallest parameter.

Then sort the second representation and for every one in the first array do a binary search on the second array for the number of elements that smaller than it by 2 (to be strictly greater in two parameters ), there only one check that if the sum of Jedi is greater than it's min 2 parameters by 2 then you must subtract one from the binary search result.

In H you can just ask for every bit and generate the number. firstly, ask for the first bit in all the elements and count the number of Integers from 0->n that have one in this bit and you can simply know the bit of the required number and the elements that have the same bit then count again number of ones in the next bit and also have the same previous bits like the required one by this way you can know every bit in half questions from the previous one .

In F you can sort the input twice (two different arrays) the first time by the attack the second is by hit point in increasing order and for every one in the first array you see from the second one the elements that have hit points less than or equal to it's attack point and keep track of the largest two attack points from the second array and you sure you can attack it and then you must check if it can attack you There only one case so you track two integers is that if you can attack yourself so if the largest attack point is like yours so you take the second Integer (both Integers can be the same).