Sorry for my poor English. If you find a mistake, write me a private message, I'll fix it. Some problems have not been translated yet, now you can try to read the Russian version of editorial with Google Translate.

408A - Line to Cashier

In this problem you were to find waiting the time for every queue by summing up the purchases of all the people, and return the minimum.

408B - Garland

In this problem it is necessary to find the garland with the maximal length, which can be composed of elements that we have.
First, if you need some color, but you don't have it, then the answer is -1
Otherwise, answer is always exists.
Let's sum the answers for all the colors separately.
Suppose we have a pieces of a garland of some color, and we need b pieces. Then we have to add min(a, b) to the answer: if a >  = b we will use b 1 meter pieces, in the other case if a < b we will use all a pieces.

407A - Triangle

In this problem you have to locate the right triangle with cathetuses a, b on a plane with its vertices in integer points.
If the required layout exists, then cathetus a always can be represented as a vector with integer coordinates A{x;y}, and a² = x² + y². Iterate over all possible x (1 ≤ x ≤ a - 1), check, that y = sqrt(a² - x²) is integer.
Vector, ortogonal to vector {x;y}, is { - y;x}. Take vector B{ - y / g;x / g}, where g = gcd(x, y). The triangle can be located on the plane if and only if b % |B| = 0, where |B| — length of vector B. The candidate for the answer — triangle (0;0)(x;y)( - y / g * b / |B|;x / g * b / |B|), but don't forget about checking that the hypotenuse isn't parallel to coordinate axes.

407B - Long Path

In this problem you had to simulate route of character in graph.
Note that if you are in vertice i, then edges in all vertices with numbers less than i are turned to p_i. It gives us opportunity to see a recurrence formula: let dp_i be number of steps, needed to get from vertice 1 to vertice i, if all edges are rotated back, into p_i. Then dp_i + 1 = 2dp_i + 2 - dp_pi. Answer will be dp_n + 1.

BONUS: Can you solve this task without statement p_i ≤ i? I don't know the solution, it seems difficult.

407C - Curious Array

In this problem you had to find how to add binomial coefficients in array offline.
Let's see, how problem changes due to increasing k from small to big values.

1) All queries have K = 0
Every time you add 1 on subsegment.
For solve this task you can add 1 at some array b[] in b[L] 1, then substract 1 from b[R+1], and after doing all queries make array a[] as array of prefix sums of array b[].

2) All queries have K = 1
Arithmetic progression 1 2 3 4 ... is added on subsegment
For solve this task you can add 1 at some array c[] in c[L] 1, then substract 1 from c[R+1], and after doing all queries make array b[] as array of prefix sums of array c[]. Actually you added 1 1 ... 1 on every subsegment at each query. If you will substract (R — L + 1) from c[R+1], and make array a[] as array of prefix sums of array b[], then it will be an answer: 1 1 ... 1 became 1 2 3 ... (R-L+1).

3) K is arbitrary
Summaring previous results one can see that if we will do

1. a[K+1][L] += 1
2. a[j][R+1] -= C(k + 1 — j + r — l, k + 1 — j) for all 1 <= j <= K + 1

and after that do a[i][j] = a[i][j-1] + a[i+1][j] (making a[i] as array of prefix sums array a[i+1]), a[0] will be the answer.
What is C(k + 1 — j + r — l, k + 1 — j)? This number is need for each query affect only on segment L..R, and you can see, why is it so, in Pascal's Triangle.

If this explanation is not clear for you, you can try to see other participants solutions (for example, Xellos's one).

407D - Largest Submatrix 3

In this task you have to find largest by area submatrix, consisting from different numbers.
Let's see solutions from slow to fast.

1) Solution by O(n⁶):
Iterate through two opposite vertices submatrix-answer and check that all numbers are different.

2) Solution by O(n⁴):
Let's fix Up and Down borders submatrix-answer (O(n²)).
Use two pointers method to iterate Left and Right borders: while in submatrix there are no equal numbers, increment Right, while there are equal numbers — increment Left. Every check — (O(n)), increments — (O(n)).

3) Solution by O(n³logn): Let's construct function maxR(Left) (let's consider that Up <= Down are fixed): maximal value Right, so that in submatrix (Up, Down, Left, Right) there is no equals numbers. You can see that maxR(i) <= maxR(i + 1) is true for every i.
How values of this function changes by shift Down to Down-1? Every value maxR(Left) can only be the same (if segment(Down, Down, Left, maxR(Left)) only added new numbers), or it can decrease.
When maxR(Left) is decreasing? Only when one of the numbers from added segment have already been in the current submatrix.
Shift Down to down let's see all numbers in row Down. For each number (let it be in column j) find indices i and k so i <= j, there is number, equal to a[Down][j] between rows Up and Down-1, i — maximal; k >= j, there is number, equal to a[Down][j] between rows Up and Down-1, k — minimal. When you find these indices (it is easy to find them using set, when you store all columns where number x was between Up and Down for all numbers x), you can try to update maxR[i] with j — 1, maxR[j] with k — 1. It will be enough, if you also update for all i = m..1 maxR[i] = min(maxR[i], maxR[i + 1]). Now maxR(Left) is correct, and you can check answer for these Up and Down by O(n).

4) Now, solution by O(n³). It requires understanding previous solution.
Previous solution, despite good asymptotics, requires to store a lot (about 160 000) sets, where you will store about 160 000 elements. Even at n = 200 it works very slow.
Let's get rid of log. Set is using only for finding nearest left and right elements, which are in rows from Up to Down, and equal to current.
Note that when you do Up = Up — 1, nearest element comes near (by column) to a[i][j], so we can find all numbers, for which the nearest element will be in new row Up, and update them nearest number, and do that in O(n²).
This solution uses O(n²) memory and O(n³) time.

BONUS: Can you solve this task faster than O(n³)? I spend a lot of time and I didn't come to any solution, but I can't show that there is not solution faster.

407E - k-d-sequence

In this problem you have to find longest subsegment, satisfying the condition.

Reduce problem to d = 1.

If d = 0, then answer is longest subsegment from equal numbers, this case we solve separately.

If d ≠ 0, then notice that if on some subsegment there are two numbers a_i, a_j so that a_i%d ≠ a_j%d, then this segment can't be good.
Divide the sequence to consequent subsegments numbers, equal by modulo d, and divide each number by d, and solve task separately with every segment, consider that d = 1.

Notice that segment [L, R] is good if and only if when max(L, R) — min(L, R) — (R — L) <= k, and there are no equal numbers. It is easy to exlain: if there are no equal numbers, then max(L, R) — min(L, R) — (R — L) is exactly number of numbers is needed to add for segment to consist of all numbers from min(L, R) to max(L, R).

For all L lets find such maxR[L], that on segment [L..maxR[l]] there are no equal numbers, and maxR[L] is maximal. It can be done by O(nlogn) by many ways, for example you can use map.

Let's learn how we can maintain array a[R] = max(L, R) — min(L, R) — (R — L). If we have such array, then we have to find rightmost R such that a[R] <= k to get an answer.

We will need two stacks and segment tree with operations "Add number on segment", "Find min element on segment", "Find rightmost number doesn't exceed k".
Let's iterate L from right to left (n downto 1). How does function max(L, R) look like with fixed L? It's values represent a set of segments so that maximum on the segment is leftmost element of segment, and these maximums are increasing. (example: for array 6 4 8 0 7 9 function max(1, R) will be 6 6 8 8 8 9). How function changes with shift L to left? Some segments are absorbed by new element, if new element is bigger than maximum on segment. Maximums on segments are increasing, so we can keep them all in stack, and when we need to add new element we have to only pop some segments from stacks while maximum on top of stack is less then new element, and push new segment after that. If every operation with stack will be accompanied with right operation with segment tree, we can store array a[R] = max(L, R). For get array a[R] = max(L, R) — min(L, R) we need only to maintain second similar stack. For get array a[R] = max(L, R) — min(L, R) we need add -1 on all suffix when we are shitfing L.

Now query "Find fightmost number less of equal k". First, segment tree divides segment of request to log(n) segments with length powers of two. Let's choose rightmost segment with minimum <= k, and do iterative deeping there to find element that we need.

So, for every L we get query on segment L..maxR(L) on rightmost number less or equal k. It is one of candidates to an answer.
We are doing O(n) operation with stack, and every requires query to segment tree, so asymptotics is O(nlogn).