What is the issue with the zip file for C? My program crashed on the judge input, and I only found out after the timer ran out that it was because the zip file had an "Unexpected end of data". Until now, I assumed that I didn't pay enough attention when downloading the file, but your comment makes me wonder.

Problem E can also be solved without PIE, but by a simple DP in which the state is the current position of the path and how many blocks we have fixed left/above of this position (seperate values for blocks above, left and above+left) See my solution for details.

The editorial for problem H says: 'We will explain the precision issues later', but that part seems to be missing. Can somebody please add that part? In my attempts to solve the problem, I struggled with precious issues for quite some time, and I added several hacks until I finally got AC (114778549).

For problem D, I don't understand the proof in the editorial that $$$t_{i,j} \gt =T_j$$$ for $$$i \lt j \lt =N$$$ when it takes 1, 2 or 3 minutes to solve a problem. Can somebody enlighten me?

By the way, I did find counterexamples when it could also take 4 minutes to solve a problem, for example:

1 2 2 2
1 1 4 4
3 2 1 3
3 2 1 1

3 4 4 3 2
4 2 4 3 2
4 4 1 2 2
4 4 2 2 3
3 3 3 3 1

I have a (somewhat handwaivy) proof. First note that you always make a jump of $$$(i+1)/2$$$ and then optionally jump an additional $$$n/2$$$. This means that in two steps, you always jump some fixed amount, then optionally an additional $$$n/4$$$ (halved from the optional part of the first jump) and then optionally an additional $$$n/2$$$ (from this jump). Repeating this pattern, after $$$x$$$ steps, you can be in any of $$$2^x$$$ evenly spaced positions.

The complexity analysis of the solution in the editorial for problem I is wrong. The problem with the proof is that the claim 'each nonzero mark can appear at most once at any given time' is false; multiple siblings of ancestors of node X can gain an 'old mark' when we query X.

In fact, the solution for one $$$A_i$$$ is not $$$\mathcal{O}(Q\log(N))$$$, but actually $$$\Omega(QN)$$$, as the generator below demonstrates. For the generated testcase, the segment tree beats solution 'harvests' about $$$\frac{1}{12}QN$$$ nodes when $$$A_i$$$ is $$$3$$$ (assuming $$$Q$$$ is allowed to be $$$\frac{8}{3}N$$$). The codes in the editorial take around 30 and around 50 seconds respectively on this case on my local machine, so would probably give TLE on the codeforces platform.

#include <vector>  
using namespace std;

int N, Q, A;
vector<int> par;
vector<int> dep;
vector<bool> isleaf;

void buildtree(int& nxt, int p) {
	if (nxt == N) return;
	int at = nxt++;
	par[at] = p;
	dep[at] = par[at] == -1 ? 0 : 1 + dep[par[at]];
	isleaf[at] = true;
	if (par[at] != -1) isleaf[par[at]] = false;
	if (dep[at] == 10) return;
	for (int i = 0; i < 3; ++i) buildtree(nxt, at);
}

int main() {
	N = 50000;
	Q = 50000;
	A = 3;
	par = vector<int>(N);
	dep = vector<int>(N);
	isleaf = vector<bool>(N);
	int nxt = 0;
	buildtree(nxt, -1);
	vector<int> leafs; for (int i = 0; i < N; ++i) if (isleaf[i]) leafs.push_back(i);

	int root = 0, at = 0, wait = leafs.back(); leafs.pop_back();
	vector<int> visit;
	while ((int)visit.size() < Q) {
		int cnt = at == 0 ? A - 1 : A - 2;
		for (int i = 0; i < cnt; ++i)
			if (at < (int)leafs.size() && (int)visit.size() < Q)
				visit.push_back(leafs[at++]);
		if (at >= (int)leafs.size()) break;
		if ((int)visit.size() < Q) visit.push_back(root);
		for (int i = 0; i < A - 2; ++i) if ((int)visit.size() < Q) visit.push_back(wait);
		if ((int)visit.size() < Q) visit.push_back(root);
	}

	printf("%d %d\n", N, (int)visit.size());
	for (int i = 0; i < N; ++i) { if (i != 0) printf(" "); printf("%d", A); } puts("");
	for (int i = 1; i < N; ++i) { if (i != 1) printf(" "); printf("%d", par[i] + 1); } puts("");
	for (int i = 0; i < (int)visit.size(); ++i) printf("%d\n", visit[i] + 1);
	return 0;
}

As an aside, personally I find segment tree beats solutions quite tricky to prove, but I also find it quite difficult to create testcases that causes them to become slow. So I don't blame the authors; I am just a little disappointed that what first looked like a cool application of segment tree beats turns out to be wrong.

Thanks for your help. The pieces start coming together for me now. Some last questions / remarks.

• It looks like it is important how exactly division (which is used inside gcd) is done: $$$round(b^{-1}a)$$$ works, but $$$round(ab^{-1})$$$ doesn't. How can we decide which one we need? Has it something to do with $$$q$$$ being a left factor of $$$g$$$?

• You say 'for simplicity we will further work with vectors $$$a_i$$$ multiplied by $$$2$$$', but can't this cause $$$g$$$ to be non-primitive, resulting in the divisor of $$$g$$$ with norm $$$\lVert q \rVert$$$ being non-unique?

• We don't need to worry about $$$k \gt 1$$$, because then the gcd of input coordinates would be greater than $$$1$$$.

• It doesn't matter to us that $$$q$$$ is only unique up to units, since that only changes the order and signs of $$$r$$$.

• In your comment regarding the transformation being $$$q \cdot v \cdot \bar q$$$, I think $$$180^\circ$$$ rotation is only multiplying rows with $$$-1$$$, not swapping them. I think swapping is a $$$90^\circ$$$ (or $$$270^\circ$$$) rotation, which also multiplies one of the rows.

• I think using $$$s'=\frac{s+x}{2},~ x'=\frac{x-s}{2},~ y'=\frac{y+z}{2},~ z'=\frac{z-y}{2}$$$ is even cleaner. If my calculations are correct, this only multiplies the second row with $$$-1$$$ and then swaps the second and third rows, which I think is just a $$$90^\circ$$$ rotation around the x axis.

• $$$90^\circ$$$ rotation around an axis may also be represented as quaternion with unit norm (but with irrational coefficients), so I think your observation is still valid.

I think I follow most of the editorial for problem I, except for several statements in the last paragraph:

Under given constraints $$$g$$$ is primitive (not divisible by any integer constant larger than $$$1$$$). It may be proven thus that if $$$g$$$ is primitive and $$$\lVert g\rVert =ab$$$ then $$$g$$$ may be uniquely (up to units) represented as $$$g=qp$$$ where $$$\lVert q\rVert =a$$$ and $$$\lVert p\rVert=b$$$. Due to this if we fix $$$\lVert q\rVert $$$ we may find actual $$$q$$$ as $$$gcd(g,\lVert q\rVert)$$$ because $$$q\bar q=\lVert q\rVert $$$.

Why is $$$g$$$ primitive (has it to do with the gcd of input being 1? if so how?). For the 'it may be proven'-statement, how can it be proven and how is it used? Maybe we need to do it repeatedly (needing $$$q$$$ and $$$p$$$ to be primitive as well) to create a unique factorization of $$$\lVert g\rVert$$$ (and therefore also of $$$g$$$ up to units)? Why does $$$q$$$ has to divide $$$g$$$? And lastly why has $$$gcd(g,\lVert q\rVert)$$$ to be equal to $$$q$$$?

Also, I don't see where the assumption mentioned by Benq comes up.

I think conceptually my solution is even simpler. The basic idea is to find a good lowerbound. Two obvious lower bounds are the maximum subarray sum (when we consider zeros and question marks as $$$-1$$$) and the absolute value of the minimum subarray sum (when we consider zeros as $$$-1$$$ and question marks as $$$+1$$$). It turns out that the highest of these lower bounds is nearly always attainable, except in the case when there are two places with different parity that provide the same lower bound (it is easy to see that this lower bound is not attainable in this case); in that case our answer will be exactly one higher.

So the final solution is just to run Kadane's algorithm twice, keep track of the lower bounds for each parity, and return the answer as described above (with a single if).

During the contest, my proof of the claim above was a bit shaky, so I also wrote a quick stress test to verify it, but the 'real code' is pretty short (only the solve method).

Instead of hashing you can also compare the actual and the expected value of $$$\sum(x[i]-a)^2+(y[i]-b)^2$$$ and then make sure that there are no points outside the outer circle. For this last check, you can remember $$$ymn$$$ and $$$ymx$$$ for each value of $$$x$$$ and iterate over $$$x$$$ to check it. Because this is the last check and there won't be many times when we pass all other checks, so the extra running time of this check wont hurt.

K: I haven't implented it yet, but I think the following should work. First for x and y independently, calculate the points in the (t,x) and (t,y) plane that contains all paintings. This can be done with half-plane-intersection. Then from this we will get piecewise linear functions for the amount of overlap of all paintings in the x-dimension and in the y-dimension. We can combine these functions to calculate a piecewise quadratic function for the area of the overlap of all paintings. On each piece, calculate the maximum of that piece, split the pieces there and in the query points, and then the answers to the queries become simple range maxima.

G: Important observation: because books heights are random, the length of the longest increasing sequence starting from some book will be small (something in the order of $$$log(n)$$$) with high probability. We will process the queries offline in decreasing order of $$$l[i]$$$ and keep the number of fragments for each value of $$$r[i]$$$ in a segment tree. When we decrease the current value of $$$l$$$, new books become available and we have to update the segment tree. Because of the observation, this updating can be done fast.

E: I haven't implemented it yet, but I think the following should work. First, for each segment determine the time it first breaks. To do this, classify the drones as heavy or light (a drone is heavy if it has more than something like $$$sqrt(k)$$$ changes in height). Then for edges connecting two light nodes or two heavy nodes we can merge-sort-like compute the breaking time, for edges connecting a light node to a heavy node we can iterate over changing times of the light node and use range queries on the changing times of the heavy node to compute the breaking time. From this it is relatively easy to calculate the answers for the queries using DSU and either parallel binary search or some small-to-large merging.

B: Find a point $$$root$$$ so that the worm the starting position lies entirely in some subtree of it and the final position has no node in this subtree. Now it is easy to see that at some point the worm has to move to some path that starts at $$$root$$$ and ends somewhere in the subtree, then directly moves to a point that starts at $$$root$$$ and ends somewhere in another subtree, and finally moves to its destination. The first and last parts can be done greedily. You choose one end, go as deep as possible from there, then go as deep as possible from the other end, etc. until the other end can move directly to the $$$root$$$. You can try both options of which end goes deeper first and keep the best one.

I was almost there (62731786), but couldn't quite figure out in time how to make the initial situation 'handy' (fixed after contest: 62742219). Fortunately the fifteenth place was (barely) enough for me to reach nutella :).

For even more 'pleasure', solve it in basically the same way, but with a LinkCutTree instead of HLD (which I just did).

I just watched your video about POI23 day 2. I found it quite enjoyable, and other similar videos as well, so thanks for making them. However, I do want to mention something about the last problem. You may have figured this out by yourselve in the meantime, but I think for Club members (KLU), the way you describe to choose the 'yellow edges' in your youtube video is wrong. Below I will use the same terminology (and colors) as you use in your video and I will talk about cubes and squares, but this generalizes to higher dimensions as well.

For example, for input '3 0 4 1 5 2 6 3 7', suppose you split the cube into the two squares (0123) and (4567) , and you choose the yellow edges 0-3 and 1-2 in the first square. Now before knowing the final cycle in the first square, there is no way to choose yellow edges in the second square that guarantees that there won't be multiple cycles when we merge the two subsolutions. More specifically:

• If you choose 4-5 and 6-7, the two subcycles can be 0-2-1-3-0 and 4-5-7-6-4, which will result into two cycles after merging (0-2-6-4-0 and 1-3-7-5-1)
• If you choose 4-6 and 5-7, the two subcycles can be 0-1-2-3-0 and 4-5-7-6-4, which will result into two cycles after merging (0-1-4-5-0 and 2-3-7-6-2)
• If you choose 4-7 and 5-6, the two subcycles can be 0-1-2-3-0 and 4-5-6-7-4, which will result into two cycles after merging (0-1-5-4-0 and 2-3-7-6-2)

The way to fix this is to first solve the subproblem in the first square, and then to choose the yellow edges of the second square such that they correspond to the 'blue' edges of the first square. Now we can prove that the merged result will always be a single cycle.

Informal proof: if we start from a vertex of the first square and start by first taking a blue edge, the only thing that can possibly go wrong is that from a vertex in the second square we prematurely (when there are other unvisited vertexes remaining) go to the vertex connected with a green crossing edge to first vertex. But the vertexes visited in the second square are consecutive vertexes of the cycle in the second square (when we take a blue edge from the first square, we have added a corresponding yellow edge to the second square, which must be in the cycle, and when we take a blue edge from the second square, it is by definition in the cycle). Since the cycle for the second square visits all its vertexes, this cannot happen.

I also found proving complexities of the (non-bitset) solutions to F non-trivial.

I did find a case (see below) which shows ksun48's solution is definitely not $$$\mathcal{O}(n^2)$$$, allthough it does use similar ideas as the intended solution. On atcoder custom test, the case generated by the code below runs in 5983ms and uses an obsessive amount of memory (2210988KB).

int nstem=MAXN/2,nleaf=MAXN-nstem;
int n=nstem+nleaf; assert(n<=MAXN);
int m=nleaf+nstem-1; assert(m<=MAXM);
printf("%d %d\n",n,m);
for(int i=0;i<nstem-1;++i) { int a=i,b=i+1; printf("%d %d\n",a+1,b+1); }
for(int i=0;i<nleaf;++i) { int a=nstem-1,b=nstem+i; printf("%d %d\n",a+1,b+1); }
for(int i=0;i<nleaf;++i) { int a=0,b=nstem+i; printf("%d %d\n",a+1,b+1); }
for(int i=0;i<nstem-1;++i) { int a=i,b=i+1; printf("%d %d\n",a+1,b+1); }

As for the intended solution, I am not entirely sure about it's complexity, but I think I'm close, allthough it still feels a bit 'hand-waivy'. Anyway, I implemented a version of it based on google translate of the japanese editorial and based on the writers implementation. The only tricky part is the 'addedge'-function. My current hypotheses is that when this method is called recursively, it will always result in creating a new edge (never returning in line 53), which obsoletes the edge from which it is created. And it seems that obsoleted edges will never result in recursive calls. Therefore, each of the $$$m$$$ input edges (together with their shortened versions) can only be shortened at most $$$n$$$ times in total in lines 51 and 52. And each iteration of lines 61 to 68 will be paid for by changing an entry in the 'exists' array from -1 to some value (either directly, or in the recursive call), which can happen at most $$$n^2$$$ times in total. Therefore, the complexity seems to be $$$\mathcal{O}(n^2+nm)$$$.

And as a final remark, I also saw an interesting accepted hashing + heavy-light-decomposition + segment tree implementation which looks like $$$\mathcal{O}(n^2log^2(n))$$$.

Problem L: To partition a subtree, assume that its parent, its leftmost leaf and its rightmost leaf are already assigned to the same set. Now assign the 'left path' and the 'right path' to a new set, together with the lefmost and rightmost leafs of subtrees hanging of these paths. Now we can partition those subtrees recursively, since the assumption is satisfied for them.

Below is a picture to make it more clear. The red nodes are already assigned to some set (the same set for all three). The green nodes are assigned to a new set. The purple subtrees are assigned recursively.

Try the following test case:

6 1 1
3 1 2 5 6 4

J: For every value, calculate the distance to its destination and sum these distances. In a single swap, this sum can not decrease for a 'free' swap and can decrease by at most two otherwise. So $$$sum/2$$$ is a lowerbound for the answer.

Furthermore, it is easy to see it is always possible that you can always choose two values to swap so that the either sum decreases by two, or the swap is free and the sum stays the same (choose a value that is in the wrong place, see what direction it needs to go, if the value in that direction needs to go in our direction or is in its final place, we found a valid swap, otherwise it needs to go in some other direction and continue searching from that value). We cannot keep making free swaps indefinitely, so eventually we will make a swap that decreases our sum by two, which proves that the lower bound can be attained.

The hard problem has a really nice solution. First note that we never need to cross an edge between two adjacent cells more than two times. Now there are only six different options for how we walk the stairs between two adjacent floors, as illustrated in the first picture below. For how we walk on a certain floor, we have essentially the same options, as illustrated in the second picture below.

Stairs options:

Floor options:

We can use these observations to solve the problem with dynamic programming, iterating over the floors from top to bottom. First we have to determine which transitions (combinations of stairs option for floor x-1 and x, stairs option for floor x and x+1, and floor option for floor x) are possible, which is a bit of casework (see my solution for details). Then we determine for each floor option its cost. And then what remains is a pretty simple dp.

The final solution is linear and it would work for much bigger limits then those that were given in the actual problem. And the complete code is quite short.

const int NONE=0;
const int RIGHT=1;
const int CROSS=2;
const int LEFT=3;
const int BOTH=4;
const int DOUBLECROSS=5;
const int NSTATE=6;
const int STATECOST[]={0,2,2,2,4,4};

vector<int> transitions[NSTATE][NSTATE];

class TurnOffLightsDiv1 { 
public: 
	int getMinimumTime(vector<string> g) { 
		int h=SZ(g),w=SZ(g[0]);
		REP(i,NSTATE) REP(j,NSTATE) {
			REP(k,NSTATE) {
				if(i==NONE&&(j!=NONE||k!=NONE)) continue;
				int wantcross=(i==CROSS?1:i==DOUBLECROSS?2:0);
				int havecross=(j==CROSS?1:j==DOUBLECROSS?2:0)+(k==CROSS?1:k==DOUBLECROSS?2:0);
				if(havecross%2!=wantcross%2||wantcross>havecross) continue;
				bool haveleft=(j==LEFT||j==BOTH)||(k==LEFT||k==BOTH);
				bool haveright=(j==RIGHT||j==BOTH)||(k==RIGHT||k==BOTH);
				if(havecross==0&&(haveleft&&i==RIGHT||haveright&&i==LEFT)) continue;
				transitions[i][j].PB(k);
			}
		}
		vector<vector<int>> floorcost(h,vector<int>(NSTATE,INT_MAX));
		REP(x,h) {
			int py=-1;
			floorcost[x][CROSS]=w-3;
			floorcost[x][DOUBLECROSS]=2*(w-3);
			REP(y,w) if(g[x][y]=='#') {
				floorcost[x][LEFT]=2*(y-1);
				if(floorcost[x][RIGHT]==INT_MAX) floorcost[x][RIGHT]=2*(w-y-2);
				if(py!=-1) floorcost[x][BOTH]=min(floorcost[x][BOTH],2*(py-1)+2*(w-y-2));
				py=y;
			}
			if(py==-1) floorcost[x][NONE]=floorcost[x][LEFT]=floorcost[x][RIGHT]=0;
			floorcost[x][BOTH]=min(floorcost[x][BOTH],min(floorcost[x][LEFT],floorcost[x][RIGHT]));
		}
		vector<vector<int>> dp(h+1,vector<int>(NSTATE,INT_MAX)); dp[h][NONE]=0;
		for(int x=h-1;x>=0;--x) {
			REP(i,NSTATE) REP(j,NSTATE) if(dp[x+1][j]!=INT_MAX) {
				REPSZ(idx,transitions[i][j]) {
					int k=transitions[i][j][idx];
					if(floorcost[x][k]==INT_MAX) continue;
					int cur=floorcost[x][k]+STATECOST[j]+STATECOST[k]+dp[x+1][j];
					dp[x][i]=min(dp[x][i],cur);
				}
			}
		}
		int switchcost=0; REP(x,h) REP(y,w) if(g[x][y]=='#') ++switchcost;
		return dp[0][LEFT]+switchcost;
	}     
};

What I have so far:

It seems we are basically looking for string p and s such that ((A^R contains s and B contains ps) or (A^R contains ps and B contains s)) and p is palindromic (possibly empty). To prevent double counting A^R should not contain xs or B should not contain xs, where x is the last character of p.

There are still some details to work out, but it feels like it should be possible to count these strings by creating a suffix tree containing A^R and B to iterate over common substrings s, and by creating a palindromic tree to count the number of different p for each of them (by starting at the longest palindromes ending before the suffix leaves of the current node in the suffix tree and then calculating the number of ancestors of these nodes in the palindromic tree).

Is this also the approach you had in mind or am I overcomplicating things?

It is very similar. To put into similar words: If my prefix is smaller, the interval will still be at least K if you use me, and since I'm later, the interval will become shorter.

My AC code gives

YES
3
3 5 7
3 4 5
1 4 7

A: Use heavy-light decomposition. Now every update introduces at most one new point where the color changes in each of the O(log(n)) paths. Therefore we can afford to keep track of all segments with the same color.

E: Keep removing nodes of degree 2 until only a single edge remains.

If you want to go from one state to another state, you know how many edges should flip and using the matrix exponentiation you get to know the probability of exactly this many edges flipping. To get the probability of this specific set of edges flipping, divide by , since each set of edges of the same size has the same probability of being flipped.

I stared for ages at why my codes for E and F gave wrong answer. I just found out that there is a query limit, which was not mentioned in the 'one-by-one' problem statement, but was only mentioned in the pdf which you can get by clicking on 'download statements'.

To be honest, I found it kind of strange that there was no query limit, so I read the statement (many times) letter for letter, but did not think to look in the pdf. Well, now I now better for next time.

You can normalize each state. Then for n=5 there only remain 34 states, 13 of which are unconnected. If you know the probability distribution of states at time l, you can use matrix exponentiation to get the answer, since 14³·q·log(r - l) fits within the time limit (one extra state for 'having been in any connected state').

Unfortunately 34³·q·log(l) seems too slow to use matrix exponentiation directly for getting this probability distribution. Instead, using matrix exponentiation again, calculate the probability of exactly k edges flipping in l steps (only 11 states so it again fits within the time limit). Now iterate over the (unnormalized) state at l and using previous result it is relatively straightforward to compute the probability that this will be the state at l.

Combining these two steps got me AC in 373ms.

I'm not sure if I understand your strategy for 'the first thing' of case three correctly. Do you propose that Bob from that point on switches between two cells indefinitely? In that case it seems wrong to me.

My proof for the third case: Bob chooses a path towards Alice. He starts switching between the first two cells of that path until Alice revisits her starting square. Then Bob starts switching between the next two cells from the path until Alice revisits her starting square for the second time. This process continues until one of the two squares Bob is switching between is equal to Alice's starting cell, in which case it is impossible for Alice to return to her starting cell and she must eventually run out of moves, so Bob wins.

H:

Lets keep a set of directed paths where the following condition holds for each node of the path except the last: the node directly after this node in the permutation (if any) can only be an earlier node or the next node of the path. Initially each node is its own path. Now we search for the head of any path which has exactly one outgoing edge to another path. If this happens to be tail of the other path we can concatenate both paths and repeat. Otherwise we have special case 1 which we handle separately (see remarks at the end).

If after the process above finishes we have more than one path, there is no solution (we can never leave the path in which we start). Otherwise we have found one solution (just follow the path), but there may be more. When there is no edge from the head to the tail (which turns the path into a cycle) we have special case 2 which we also handle separately (see remarks at the end). Otherwise we can start in any node of the path, provided there is no 'back edge' (other than the cycle-closing edge) that 'covers' us, which is easy to check with a prefix-sum-like datastructure.

There are two special cases left that need to be handled. For special case 1 we know that the last nodes of the permutation must be either the path that points to the middle of another path or the nodes of the other path before the node that is being pointed at. We can just try both cases with minor modifications of the algorithm above (only extend paths outside the final vertex set, append the final vertexes at the head of the path afterwards, and there will never be more than one solution). For special case 2 an other solution is only possible if there is at least one edge to the tail of the path. In this case the last nodes of the permutation must be the prefix of the path upto the last node that has such an edge and we can handle this in the same way as special case 1.

The above can be implemented in . I enjoyed solving this problem, too bad I couldn't make it work during the contest (mostly because I was overcomplicating it), but I have it accepted afterwards. I have omitted most of the proofs, but when drawing some cases on paper they should be rather obvious.

This site and this site contain a lot solutions, including to most problems you gave.

The first step I took is to think of the problem in terms of prefix sums. This is a very common approach in problems dealing with sums over subarrays, so the reason I thought of is is experience.

The second step I took is to notice that were only interested in the last position in the list that has a value of at most x. Therefore, we can remove items from the list when there is a later smaller prefix sum. This will make the list increasing in both index and value. This is also quite a common trick, but I think it should be possible to come up with this even if you haven't seen it before.

Now for a given end position we can binary search the list to find the best start position for it. If we want to make it linear, we somehow have to get rid of the binary search. Suppose the optimal start position for a given end position is in the middle of the list. If we could remove the elements before, this would make the algorithm linear. The problem with this is that those elements before could be the optimal starting positions for some later ending positions. The third step is to notice that allthough this indeed might cause the algorithm to miss some best local minimums, it will never cause the algorithm to miss a global minimum.

The way to make algorithm linear (drop elements before current optimum) is also quite a common trick, but one I think you should be able to come up with even if you haven't seen it before. The most difficult part of this problem for me was to see why this works (local minimums vs global minimums).

So in conclusion, to solve this problem in linear time I think you have to have some experience (to know the prefix sums technique), make some logical simplifications (here experience helps) and finally make the observation why this works (the creative, thinking part needing intuition and problem understanding).

Keep a dequeue of the 'best' prefix sums found so far. This will be increasing both in index as well as in value. When we go from left to right, we add new prefix sums to the back (making sure it stays increasing in value) and remove prefix sums from the front (if we can use it here, it will never be better to use it later).

The code will look something like this:

long long sum = 0;
deque<pair<int,long long>> q;
int ret = INT_MAX;
for(int i = 0; i < n; ++i ) {
	while( !q.empty() && q.back().second >= sum )
		q.pop_back();
	q.push_back(make_pair(i,sum));
	sum += A[i];
	while( !q.empty() && q.front().second <= sum - k) {
		ret = min(ret, i + 1 - q.front().first);
		q.pop_front();
	}
}
return ret == INT_MAX ? -1 : ret;

I have a similar feeling. Solved the easy and the medium for a decent number of points, was working on the 'Solution 1'-approach for the hard (in quadratic time), but couldn't quite finish it, got a challenge and still only placed 57th.

In retrospect I maybe should have looked at the standings about 20 minutes before the end and after seeing the large number of submissions for the hard problem reconsidered my aproach; maybe that I would've thought of the 'Solution 3'-approach then. But it is hard to change plans when you feel like you're on the right path.

So for me it also feels wrong to (almost) only let the 'do you see (guess) the Solution 3-approach' decide the advancers, but I might be biased :). Anyway, I'll retry in 3B.

That seems somewhat simpler than what I was doing. I only calculated the local prefix maxima (not the global ones) and then the result of a single node in the final calculation was the triplet (minimum cost to get to the next interval, maximum position we can get with that cost, maximum position we can get with a cost of one more)

In my solution there is no master. Every node searches for the correct value of D in its own list of maximums (and only one node finds it and that node prints the answer). So the number of messages send for every node is 2*number_of_nodes*number_of_iterations and the k-ary search is necessary.

Maybe you could pass the queries of all searches in a chain instead, but it might be to slow and seems trickier to code to me. Also maybe there is a way around having to search on each node, but I don't see it yet (searching on the entire range of towels fails since it is not monotonic, it is only monotonic for the prefix maximums, but the master does not now the prefix maximums of others, or which node holds the globally k-th prefix maximum)

I admire the diligance, but I have one question. Maybe I am missing something, but how does this solution handle the case of a very long string of A's with some noise in the middle? In that case a lot of the hashes will be the same, allthough the string is not very periodic (a long prefix and a long suffix are, but not the entire string). And aborting the equality check early seems a bad idea since somewhere in the noise there will probability be a match for the first couple of bits.

In my solution (which passed the large in 8340ms) I did the following:

Evenly divide the stacks among the nodes (the worst case seems to be 101 stacks in which case the first node might get about 20 million towels). Then for each node determine the order in which the towels for this node are given out (using a priority queue) and determine the prefix maximums (these are the candidates for D).

Now given a value of D, a node can determine the number of towels it gives out in phase 1 by binary searching these prefix maximums. With the outer binary search (each test involves sending a query to each other node and waiting for the answer) each node can paralelly determine if it has the 'correct' value of D and if so (which will be the case for exactly one node), how many towels are taken before it, from which the final answer can easily be computed.

The final trick in my solution for reducing the message count is to use a k-ary search (I used 250) instead of a binary search.

It seems I am missing something simple in B, probably because I overcomplicate the problem :).

I've reduced the problem to counting the number of of topological orderings in a graph of a special form (which look somewhat like a Young tableaux, but 'right-aligned' instead of the usual 'left-aligned').

What am I missing?

I solved it with DP, where the state is (number of saucers removed from queue, machine that is empty, time after which the other machine will become empty) and the value is the minimum time to get to that state. The important observation that allows this solution to fit in the limits is that the third parameter can be bounded by MAXH*MAXS, because if the free machine can process one saucer before the other machine will become empty it is always optimal to do so.

Concentrate on one player at a time, suppose the cards he ends up with are a₁, ..., a_k, with a₁ being the best. Let b_i be number of cards the previous player (the player who passes cards to the current player) has which are better than a_i. Now process the cards of the current player from best to worst.

Card i either initially belonged to some starting hand out of which the previous player just drafted a better card (b_i options) or it was the first card drafted from the starting hand of the current player (1 option). Exactly i - 1 of these options have already been taken away (by previously processed (better) cards of the current player), so b_i + 1 - (i - 1) options remain, resulting in a total of ways to choose where the cards for the current player came from.

The only thing left is to make sure that the current player started with at least one card, so we need to subtract the number of ways in which we never choose the second type of option, which is . The final answer is the product of the number of ways for each player. All this can be implemented in .

Well, I just looked at the results of the last ten SRMs or so and in term of accepted solutions relative to the total number of participants, this was definitely one of the hardest (if not the hardest) in those rounds. It might have been easy for you to come up with a correct solution, but it is also pretty easy to come up with a wrong solution (for example always flipping the component with the largest degree or something like that). Also, even if you get the right idea, it might take you some time to convince yourself that it is actually the right idea.

So I disagree with you and in hindsight I still think that for a lot of competitors (remember that you are one of the top competitors) the competition would have been more fun if this was the medium problem and there was an easier 250 instead. The samples were ok I think (two thirds of the solutions passing seems reasonable to me), allthough we could have added a non-trivial large (20*20) testcase.

This time there was no discussion with the testers about the point values the problems should have, presumably because of the short time between the last comments relating to the content and the actual round. If there would have been I would have suggested something like 350-650-1000. I guess that the reason the hard was only given 800 is because it was originally proposed as a medium (not a good reason imho, but a reason anyway), but for the other problems I don't know.

This is the way I solved the PawnGame problem (I was a tester for this round). Let l[i] be the number of squares left of the black pawn, r[i] be the number of squares right of the white pawn and m[i] be the number of squares in between the pawns. It only ever makes sense for black to jump when l[i]<r[i], for white when l[i]>r[i] and for no-one when l[i]=r[i] (if someone is forced to do so otherwise he might as well give up). This also means we are never in a rush to jump (the other player will never take away that option). So the game will start with both players making moves toward each other until no such moves are possible anymore. When such a state is reached, it is trivial to determine the winner. The trick to this problem is determining in what rows the players should move in the first stage.

I came to the solution by noticing that in the end the only thing that matters is in how many rows it will makes sense to jump for black (B) and in how many rows it makes sense to jump for white (W). Then the number of moves available for black will C-B and for white C-W, where C is some constant (not accounting for rows where l[i]=r[i], but those rows will decrease C for both players by the same amount). In other words, the goal of both players in the first part of the game is to get as many pawns as possible to 'the other half of the row'.

When m[i]%2=0 a move by one of the players can always be countered by the other player, so for those rows it is already clear which of the pawns (if any) will get to the other side. A similar reasoning holds for when abs(l[i]-r[i])>=2. So the only interesting rows left are those in which m[i]%2=1 and either l[i]=r[i] or abs(l[i]-r[i])=1. In the first case always one of the pawns will reach the other half, so 'winning' this row relatively gains 2 points, while in the second case either the pawn that is ahead will reach to other half or the row will end in a draw (l[i]=r[i]) so 'winning' this row only gains 1 point.

So the complete strategy for the first part is: If there is a row with m[i]%2=1 and l[i]=r[i], move in one of those rows. Otherwise if there is a rows with m[i]%2=1 and abs(l[i]-r[i])=1 move in one of those rows. Otherwise move in any row.

Before reading this thread I did not know the problem also appeared in Winning Ways for Your Mathematical Plays, maybe I should read that book :). Note however that the strategy above corresponds with the table from the book in the spoiler below (when m[i]%2=0 all moves can be countered and when m[i]%2==1 the first option 'costs' only a star, the second option costs 'half a move' and the final option costs a full move).

I think the problem is really interesting and has a beautiful non-intuitive solution. It is a shame that I didn't notice the test cases were so weak and that this (understandably) takes a lot of attention away from the beauty of the problem.

As a tester for this round I feel I have to say something. First let me start with apologizing for all the issues this round had. When you are a tester for a round you always try to do your best to do whatever you can to let the round go smoothly and to make the round fun for everyone. I clearly failed this time and for that I feel bad.

Looking back at the round, there were a few things I should have done better. First, I knew that the easy was harder than usual. Because of that I did push for more samples with explanations, but what I now think I should have done is to make more noise and to try to make it the medium problem instead and ask for another easy problem. The point you make about the round also having to be fun for blue coders convinced me here. The round would be fine that way, I didn't really like the problem we ended up using as the medium anyway and the round would probably be more fun for a lot of people.

Second, I should have done at least a quick look at the test cases. The system used for testing problems does not make it easy to do that, but some effort in this area should have prevented the extremely weak test cases of the hard problem.

Third, I should have seen the overflow issue in the medium problem.

Fourth, I was way off in my estimation of the difficulty of the medium problem; I expected it to be solved by something like 10-15 people. In my testing one of the first things I tried was when can you cut a 2*x piece 'for free' (without the other player getting anything in return), when a 3*x piece, when a 4*x piece, etc. which quickly leads to the correct pattern and then the code is really short. I agree it requires somewhat of a leap of faith, but playing with it some more on paper (or possibly stress-testing) should be convincing enough to code it I would have thought. Originally the medium and hard problems were swapped, but both I and the other tester found the PawnGame problem too hard for a medium and the BrownieGame problem doable (allthough not great) for the medium slot. It turns out we were right about the PawnGame problem (allthough two solutions passed, they only did so because of the weak test cases), but wrong for the BrownieGame problem. The thing I will take away from this is to be extremely cautious about allowing a problem that was posed for some slot to be used for a lower slot.

Fifth, I should also try to google to see if the solutions to some problems are easy to find that way. Maybe I would have found Conway's book that way. Btw, I just tried it for the 250 and found this.

The sixth and final thing is that I will ask to be able to start testing sooner. This time I was given access to the problems on monday evening and this was a bit too short for proper testing for me; if it is in a weekend I usually have some extra time but during weekdays combined with a full time job was less then ideal.

Once again I apologize for the issues in this round and I will try to do better next time.

No, you binary search over the maximum cost for which you use 'all options'. To check if m is possible, check if (here counts the number of i for which i·2^x ≤ m). After the binary search you can use whatever you have left for options which cost exactly one more.

First note you need to maximize subject to (here x_i is the number of ones in f(a, i)). Now increasing a x_i by one 'costs' i·2^x_i. Binary search over the maximum cost that you use.

I solved it today (link) (during the contest it took me way too long to solve F and then spend the rest of the time on H) and expected there to be lots of cases, but was actually surprised that there were only two.

Either there is a cut in at least one of the dimensions or there is no cut in any of the dimensions. The first case can be handled quite easily with inclusion-exclusion. The second case is somewhat more tricky.

Define a cuboid to be in a pillar if it can be 'pushed down' together with all cuboids 'below' it. If a cuboid is not in a pillar (we need at least one of those, otherwise we would have a cut) then it must be blocked somewhere, either horizontally or vertically or both. Without loss of generality assume it is blocked vertically. This blockage causes the entire vertical slab to be blocked. If this entire vertical slab could be 'pushed down' together we would have a cut, so it must be blocked somewhere horizontally. Continuing in this way we see that all cuboids that are not in pillars form vertical and horizontal slabs that are connected. This also means that all those cuboids are aligned in layers. At least one of the pillars must be shifted relatively to the layers (otherwise we would have a cut) and this shifted pillar causes the rows and columns in different layers to be aligned.

This all means that we need to fill C/c layers so that a given number of the A/a rows (at least one, not all of them) and a given number of the B/b columns (at least one, not all of them) are shifted in at least one of the layers. Each layer is a 2D-version of the problem, were we can either shift some rows, shift some columns or shift nothing at all. This can be calculated with a relatively simple DP and afterwards we can shift the remaining pillars and obtain the answer for the second case.

In my submission (343647) I only build two big suffix trees explicitly.

In the centroid decomposition I find for each query one node in each of these 'big trees'. After the centroid decomposition I preprocess one of the suffix trees, finding for each of the queries the last node in the suffix tree that is an ancestor of the node from the centroid decomposition and is a suffix of the special word for the query (which is probably what you call 'the position in the small tree', see wlast, oldwlast and qstidx in my code).

Also at the same time I construct for each suffix of a special word the range in the inorder traversal for that special word that corresponds to the subtree (which is similar to an euler tour of the 'small trees', see bwlid and bwrid in my code).

I'm not sure which part you don't understand. Maybe my code clarifies things:

• centroid decomposition [AC in 360ms]
• merge-small-to-large [AC in 180ms]

I had the same idea (centroid decomposition) but had to stop halfway during the contest, so I wasn't able to finish it. I don't think the approach is 'nasty' and actually quite like it.

The basic idea is to think of all paths starting in a node. We should count the number of paths where d[u]>=mindist[u] ONLY for the last node on the path (where d[u] is the distance to our starting node and mindist[u] is the minimum distance to a leaf).

With the centroid decomposition in a single step we consider only the paths going through the centroid. Now a path from u to v (not in the same subtree) should be counted for u iff 1) dep[u]+dep[v]>=mindist[v], 2) for all nodes on the path from u to the root dep[u]-dep[x]<mindist[x] and 3) for all nodes on the path from v to the root dep[u]+dep[x]<mindist[x]. The middle can be rewritten as dep[u]<dep[x]+mindist[x] for any proper ancestor of u and the first and last as mindist[v]-dep[v]<=dep[u]<min(mindist[x]-dep[x] where x is a proper ancestor of v). With one dfs we can precompute the ranges of depths for which a certain v can be counted and with another dfs update the answer for that subtree (first removing the subtree from the depths to be counted and re-adding it afterwards).

It seems a 'merge-small-to-large' kind of approach should also work, but (substantially) more difficult to code: Paths from one light subtree to another light subtree can be handled similarly as above. For paths from a light subtree to a heavy subtree we should do some preprocessing before going into the large subtree. For paths from a heavy subtree to a light subtree we should end the processing of a subtree with some information about the depth-ranges in it, so we can do some postprocessing after going into the large substree to handle these paths. In the end it should be possible to do all computations visiting the heavy subtree only once, so also resulting in an NlogN runtime.

I solved it in the practice room in the following way.

1. First use divide and conquer to determine an x-coordinate that is within the rectangle: choose the middle x-coordinate, solve recursively for rectangles lying left of this x-coordinate and for rectangles lying right of this x-coordinate. Now all we need to implement is a method for finding rectangles containing a fixed x-coordinate.
2. Fix the lower y-coordinate.
3. Imagine we also fixed the higher y-coordinate. Now for every color it is easy to see we have at most two options: take the closest point from the left of the fixed x-coordinate or take the closest point from the right of the fixed x-coordinate. The answer will then be (hy-ly)*(max_left_dist+max_right_dist), where max_left_dist is the maximum distance from a point chosen from the left and max_right_dist is defined similarly.
4. We can visualize this by plotting for each color (left_dist,right_dist)=(a,b) in the plane. Now we have to choose a point (aopt,bopt) so that for each color either a<=aopt or b<=bopt (or both) and we want to minimize aopt+bopt.
5. From this we can immediately see that we can safely remove points that are completely 'covered' by other points. Therefore for the remaining points as a increases, b decreases.
6. We can also see that the only options for the optimal (aopt,bopt) are all combinations of two remaining adjacent points (if (a1,b1) and (a2,b2) are adjacent, an option for a solution is (a1,b2)).
7. Now instead of fixing the higher y-coordinate, instead we will use a sweepline, maintaining the set of remaining points and the options for the optimal (aopt,bopt) as we go. This sweepline will go from top to bottom, since that way the left_dist and right_dist for each color will only get worse, so we don't have to worry about 'old' values for a color still being in the datastructure.
8. Maintaining these datastructures is a little tricky, you can look at my code to see how I did it (basically use a set with some binary searching for maintaining the points, a priority queue for maintaining the options, and some bookkeeping for determining when an option becomes invalid (the corresponding points are not next to eachother anymore)).
9. Putting it all together, we see that it works, and the complexity seems to be O(n^2*log(n)). (It takes 557ms on the worst test case in the system tests).

I can explain my solution (30552018). Not entirely sure if this is what you mean, but it is somewhat different from the solution in the editorial and (I think) an interesting alternative way to solve the problem.

First note that the stack in 'the stack way' (as mentioned in the editorial) can never get very large, at most about O(sqrt(tot)), assuming we keep the lcp-values on the stack distinct. Now for an interval in the segment tree, keep two stacks: one 'forward' and one 'backward'. Both of these stacks have at most O(sqrt(tot)) values. We can use the stacks and best value of two adjacent intervals to calculate the stacks and the best value for the combined interval. All this can be done in time linear in the stack sizes. Since we have O(lg(n)) levels in our segment tree, this gives an upper bound of O(sqrt(tot)*lg(n)) per query.

Your solution seems to be O(N*sqrt(N)). The code below gives test cases where your solution performs a little over 0.6*N*sqrt(N) calls to push_down. I think that is about the worst you can do, since only the push_down call on the heavy child seems suspect (I think) and because of the merging of light childs before it, it seems a vertex can receive at most O(sqrt(N)) such calls.

int n = 500000, d = 0;
while (3 * n - 3 * (d + 1 + (d + 1 + 2)*(d + 1 - 1) / 2) >= 2 * n) ++d;
vector<int> p(n);
p[0] = -1;
FORE(i, 1, d - 1) p[i] = i - 1;
int at = d;
REPE(i, d - 2) {
	int prv = i;
	REP(j, d - i) { assert(at < n); p[at] = prv; prv = at++; }
}
while (at < n) p[at++] = d - 1;
printf("%d\n", n);
REP(i, n) { if (i != 0) printf(" "); printf("%d", p[i] + 1); } puts("");

The following is not a formal proof, but one that seems good enough for me :) Suppose that we need to remember three cells, let's name them a, b and c. Then the path must first visit a for the first time, then b for the first time, then c for the first time, then a for the second time, then b for the second time and finally c for the second time (if the path was for example abcbac then we could take a 'shortcut' between the two a's, costing at most two instead of one, but saving the cost of b). If we need to start in one corner and end in the opposite corner, then (for topological reasons) this structure (abcabc) is not possible without the path crossing itself (try it on paper), so we never need to remember three cells.

Below are two examples. The first example shows that we do need to remember two cells and the second example shows that if the destination (or source) is not on the border, then we need to remember more cells. The second example can be extended to any number of cells that need to be remembered (if the grid can be large enough). In the examples S stands for source, D for destination and lowercase letters for initially blocked cells that need to be removed in the optimal path.

SS..####
SS..####
##..####
....####
...a....
..#.....
.....#..
....b...
####....
####..##
####..DD
####..DD

SS#####.......
SS#####.......
..###....###..
..###...cDD#..
..#....#.DD#..
..#...b...##..
.....#....##..
....a...####..
####....####..
####..######..
####..........
####..........

I can log in now. The contest is not available anymore and t-mac replied to my question what is going to happen that they are 'talking internally'.

Edit: the round just became available

If there are no edges in the graph then (at most, see below) one of the nodes can be in the clique. Otherwise let u be the vertex with the largest degree. We have two cases:

• If u is not in the clique then all adjacent vertices (at least one) must be in the clique and the clique size must be at least d(u) so each of the vertices must have at least d(u)-1 edges to other vertices in the clique. But since all nodes have degree at most d(u) and the adjacent nodes have an edge to u (which is not in the clique), the clique must consist exactly of the nodes adjacent to u. This means that the current graph must look like a clique of size d(u) and some isolated nodes.

• If u is in the clique then we known that nodes not adjacent to u are not in the clique and we can remove them and u from the graph and repeat.

So the algorithm looks as follows:

1. If there are no edges in the current graph goto 5

2. Select the node with the largest degree and remove all nodes not adjacent to it from the graph.

3. If the current graph is a clique (keep track of total number of nodes and edges in current graph) goto 6

4. Remove the current node from the graph and goto 1

5. The options for the clique are (the removed largest degree nodes) together with (at most one node from the remaining nodes).

6. The options for the clique are (the removed largest degree nodes) together with (the remaining clique minus possibly one node).

I had exactly the same bug! In addition, I also had an overflow, but with those two fixes my solution passes in upsolving.

Would not have meant a win for me (Gennady was just too fast for that), but for me a second place also counts as 'amazing' :).

I agree. I guess it is just the hammer-nail-thing Petr mentioned in one of his recent blog posts.

Btw, my centroid decomposition solution from the contest was hacked (time limit exceeded), but afterwards I optimized my code somewhat and now it passes in 2.4 seconds (28668357).

Btw, since there are also a number of people competing onsite, I think they will be announcing the results in some kind of award ceremony, which might take a while.

I also asked a question (using the messages) about when the results will become available a while a go, but haven't received an answer yet. I am afraid that whoever is answering the messages is now also busy with the award ceremony.

I was wondering the same :).

I think my idea of B is right, but there could always be an implementation bug (especially since the sample cases were very small; I did not stress test my solution). What I did was for each subtree compute how much beacon time from the root you need and how much beacon time you have remaining if you need to traverse this entire subtree. And then do another dfs to determine final node you are going to end up in. The have/need for the parent structure is passed as a parameter to this function and have/need for the siblings can be calculated with prefixes and suffixes from the first calculation.

I got it to pass both the time and memory limit (barely), but looking at some other solutions, I am now quite sure it is not the intended solution :).

We can prove it by contradiction. Take any graph with the smallest number of nodes for which this algorithm does not give an optimal labeling. The largest label must always be assigned to a node with no outgoing edges, but it can't be the largest of those nodes (otherwise the algorithm would give the optimal labeling). Lets call the largest node with no outgoing edges x and the node that has the largest label in the optimal labeling y. Then after labeling y with the largest label, the remaining part of the graph is correctly labeled by the algorithm (otherwise we would have a smaller graph for which the algorithm gives an incorrect result). This will first label some nodes greater than x and then it will label x. But we get a better labeling by labeling x with the largest label, y with the next largest and then label the same nodes as before. This is because of the nodes labeled so far y is the smallest node (since y < x and all other labelled nodes are greater than x) and in the partial labeling we have labeled the same nodes using the same labels. So we have a contradiction, which means our assumption was wrong and therefore there is no graph that our algorithm labels incorrectly.

I only saw it in the last 5 minutes (which was just in time for me). The trick is to look at the problem backwards: determine which node gets the last label.

Sometimes you need more moves. For example '4 1 2 5 6 2 1 6 5' needs 6 moves. Analyze why and you will find how to get the minimum number of moves.

When you have only two weights, you can solve the problem greedily: first take the minimal number of necessary items so there is a multiple of the lcm remaining (in this case this means taking a single item of weight 1 when the wanted sum is odd) and after that greedily take the best groups of a single item of total weight equal to the lcm until you have the wanted sum (in this case this means either taking a single item of weigth 2 or two items of weight 1).

It is then relatively easy to prove that the dp solution gives the same results as the greedy solution above (for example by induction).

It works because in this case F(0) < F(1) < .... < F(B1) = F(B1+1) = ... = F(B2) > F(B2+1) ...> F(m/2). If there also are equal elements in other places, you are right and ternary search is not guaranteed to work.

Consider the case n=4, m=7 with items A=(1,3), B1=(2,4), B2=(2,4) and C=(3,6).

Then the (only) optimal solution for dp[4]=A+C, for dp[5]=A+B1+B2, dp[6]=A+Bx+C and dp[7]=B1+B2+C, but there is no way to create the solution for dp[7] by adding items to any of the three solutions before.

To achieve this complexity you need to keep your interval tree balanced, for example by using a splay tree. I looked at your submission (26724827) and it seems it will time out on a case such as:

50000 1
1 2 ... 50000
100000
2 1 1
2 2 2
...
2 50000 50000
2 1 1
2 2 2
...
2 50000 50000

I guess everyone has their own coding style he/she is comfortable with. Sometimes when I look at someones code I think 'is it really necessary to put that code on 10 lines when it also fits on 1' :).

That reminds me of a story from an TCO a while ago. I was coding and Jan Kuipers was watching my screen. When somebody asked him how I was doing, he replied 'he has a bug over there' (pointing about half a meter right of the screen).

I also viewed the process as a rooted tree with N+M leaves, N of them labelled with 0 and the others labelled with 1, where each non-leaf node having exactly K children and is labelled with the average labels of its childeren (just like the editorial).

Then I relax this condition a bit, so that there may be fewer than N+M leaves; I still require M of them to be labeled with 1, but between 1 and N of them to be labelled with 0. We can always reconstruct this into a valid tree (without changing the label of the root) by repeatedly expanding any leaf labelled with 0 (labelling all new leafs with 0) until there are N leafs labelled with 0.

Next I proved that we can transform any tree which has more than one branching node at some level into a tree which has at most one branching node at each level and the deepest level has at least one leaf labelled 1. The second part can easily be achieved by contracting nodes where all childs are labelled zero into one node labelled 0. The first part can be done by noticing that if there is more than one branching node at a level, there are at least 2*K-1 leaves in one of the levels below that level. In this case at least K of them have the same value. We can rearrange these nodes so they all have the same parent. We then contract the K nodes into 1 node with the same label. This does not change the label of the root. If the node was labelled 1 we have to expand one of the deepest nodes labelled 1, so that the number of nodes labelled 1 stays the same. We can repeat this proces until each level has at most one branching node.

Finally we can now uniquely define the shape of the tree only by its height. When we know the height we can calculate the number of leaves: it has to be at least M+1 and at most N+M. We then see that if we decide for each level how many leaf nodes at that level we label with 1 (making sure there are exactly M nodes labelled 1 in total) this defines the label of the root node and each way of assigning these values results in a different value for the root node. The number of ways for this can easily be calculated with a simple DP. We then take the sum over all valid heights and we are done.

My code (20 mins after constest)

The reason for the WA is that is possible that the root node and its children are deleted and that the second dfs then never visits the part of the tree that isn't deleted. Small challenge case: '7 5 2 2 2 2 2 1 1 1 2 2 3 3 4 4 5 4 6 5 7' (answer is 2, but first attempt returns 1).

Btw I liked the idea and the video. You solved the problem in a somewhat different manner than I did. For me personally the explanation+coding could have been a lot shorter, but then again, I realize that this may not be true for the target audience.