Good morning. Does anyone knows if the 2nd division of GP of Europe will be held today? It's 40 minutes after the contest should have started.

11.11.2018 12:00 Grand Prix of Europe

**Upd.** div. 2 system appeared and is planning to start at 13:00

Auto comment: topic has been updated by rsFalse (previous revision, new revision, compare).What's the idea for D/G/L/M?

G: Every number can be represented as 2^x*3^y*z, group them by z and let (x,y) be its coordinate, then it is a standard mask-DP problem on the grid(you can't choose a shape like 'L').

which one needs to squeeze hard into TL (we couldn't)

AC in 0.766

You can sort all existing cells, then all interesting cells are in a segment, you can do something like two-pointers, each movement of a border of this segment correlate to DP transition.

Max length of this segment is 19, and it is decreasing with x and z quite fast.

CodeI used many methods to decrease the running time, such as:

only consider connected grids.

for all points: y -= min(y).

iterate states carefully, not all states.

But, x, y <= 30 right? So how do you do the mask dp?

y<=18, and larger x has smaller y.

D: first for each query calculate minimum of "when this segment started to accumulate snow after clearing last time" using segment tree or other data strycture. Next, you need to answer queries of type "how much snow was there from moment x to t (current moment)". It will have several full blizzards (use prefix sums for that) and 2 partial blizzards (it's 2 quadratic functions)

"when this segment started to accumulate snow after clearing last time" -> but they might be cleaned partially no?

I mean,

i-th kilometer segment has 1 numberlast_{i}-- "when this segment started to accumulate snow after clearing last time". For each query of type '?' you'll get minmum oflast_{a}, ...,last_{b}L: Use inclusion-exlusion formula. We choose some subset of rows, columns and diagonals such that all cells there are equal and add ± 2

^{number of cells not covered by subset + number of connected components in subset}to the answer. Without diagonals it is easy to do inO(n^{2}). With diagonals when we choose rows and columns we need to keep track of cells on diagonals that are covered by some row and some column. We can do it with dp.M: First kick out all points that can't reach (1,1) or (n,m). What we need to do is to count the number of points each point can reach in the graph. Note that it is a planar graph, so for a point, lets track the wall by our left hand and right hand, we will get a polygon. The answer is equal to the number of points inside the polygon. We can use DP to calculate this. The complexity is linear.

Ternary search passed problem A, is there a solution without ternary search?

I got WA18 by nested ternary search. I got AC after eliminating one TS and did some reflection trick.

I solved it only with reflection trick, but costed me lots of time. Ternary search sounds better.

Isn't there quite a lot case work, if we solve just by reflection?

Three cases: if shortest path to one line passes through other line, that's the answer. (times 2)

Otherwise, if segment between reflection of O over two lines intersects both lines and in the correct order, answer is tbat distance.

If none of these work, answer is path to intersection and back.

Any idea what is WA 115 in A?

It's the case of parallel lines. Try something like -1 0 -1 and 1 0 2

How can one parse the statement for J in a way that Maggy can rest in some moments??

Like no sentence of these imply that! I like the word "exactly" the most from it. Such a nice touch to a already misleading legend!

Is it necessary to set input upto 5 MiB for TL = 1 sec in

O('Sysadmin')? (Can't even read so much with slower language :( )Upsolving page isn't working. It would be nice to have ability to upsolve problems which are div. 2 only (O, P or others).

How to solve E , I ?

EBuild arbitrary MST. If some edge doesn't get included in it then the answer is maximum value of the loop it produces when added to MST. That can be canculated with some binary lifting. This part is trivial)

Now for the edges of MST. Apparently, you want to find the minimum of maximum values of all loops (from the first part) going through that edge. That requires some updates on the path in tree.

However, as it fully offline, the following method works. Split update (

v,u) into (v,lca(v,u)) and (u,lca(v,u)). Now binary lifting style domn[v][i] =min(mn[v][i],val),v=up[v][i] for both updates. And then push the values ofmn[i][j] down tomn[i][j- 1] andmn[up[i][j- 1]][j- 1]. This way the lower vertex of edge (v,u) will have itsmn[i][0] as the answer at the end.I am really terrible at describing solutions, my code will tell it better, I believe)

I: Let (p,t) be points on 2D-plane, rotate the plane by 45 degree. According to Dilworth's theorem, the answer is equal to the length of LDS.

E is an extension of the 2018 USACO US Open problem Disruption. As mentioned, for edges off the MST, you do an LCA query to find the maximum path on the MST between those vertices, and the edges in the MST part can be handled in the way described in the reference solution.

I has probably appeared more than once in other contests, see for example the 2009 BOI problem Candy Machine, except you don't need to produce a proof of the answer. The reference solution here also passes once you omit the extra output.

The problem most recently appeared on VK Cup 2017 827D - Лучший вес для ребра. (Credit to ksun48 for digging up the problem, after contest of course.)

What about J?

J: Sort all numbers, the optimal way is to select consecutive numbers a[l],a[l+1],...,a[r] and change them to a[(l+r)/2]. So two-pointer iterate l and r to find the longest one.

How to solve B?

How to write an integer as the sum of Fibonacci numbers using minimum number of terms? It's called Zeckendorf representation and can be obtained greedily.

Let

f(X,K) be the number of integers up toX, whose Zeckendorf representation contains at mostKterms. IfF_{i}is the largest Fibonacci number less than or equal toX,f(X,K) =f(F_{i}- 1,K) +f(X-F_{i},K- 1) holds. Write memoized recursion using this.I transformed the statement into "counting how many 01 strings with at most k ones, and there are no two adjacent ones in the string", it can be easily solved using DP.

rsFalse uses Perl for every problem :O