### rsFalse's blog

By rsFalse, history, 6 years ago,

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

• +39

 » 6 years ago, # |   0 Auto comment: topic has been updated by rsFalse (previous revision, new revision, compare).
 » 6 years ago, # |   +8 What's the idea for D/G/L/M?
•  » » 6 years ago, # ^ |   +8 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').
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +18 which one needs to squeeze hard into TL (we couldn't)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +9 AC in 0.766You 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. Codevoid removeOne(int S) { for (int mask = 0; mask < (1 << (S - 1)); mask++) dp[mask] = max(dp[2 * mask], dp[2 * mask + 1]); } int solve(vector a) { sort(a.begin(), a.end()); dp[0] = 0; int l = 0; for (int r = 0; r < (int)a.size(); r++) { while(l < r && (a[l].first < a[r].first - 1 || (a[l].first == a[r].first - 1 && a[l].second < a[r].second))) { removeOne(r - l); l++; } int S = r - l; if (S >= 2 && a[l].first == a[r].first - 1 && a[l].second == a[r].second && a[l + 1].first == a[r].first - 1 && a[l + 1].second == a[r].second + 1) { for (int mask = 0; mask < (1 << S); mask++) { dp[mask ^ (1 << S)] = ((mask & 3) == 3 ? 0 : dp[mask] + 1); } } else { for (int mask = 0; mask < (1 << S); mask++) { dp[mask ^ (1 << S)] = dp[mask] + 1; } } } int S = (int)a.size() - l; int ans = 0; for (int mask = 0; mask < (1 << S); mask++) ans = max(ans, dp[mask]); return ans; } 
•  » » » » 6 years ago, # ^ |   +8 I 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.
•  » » » 6 years ago, # ^ |   +8 But, x, y <= 30 right? So how do you do the mask dp?
•  » » » » 6 years ago, # ^ |   +8 y<=18, and larger x has smaller y.
•  » » 6 years ago, # ^ |   +8 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)
•  » » » 6 years ago, # ^ |   +8 "when this segment started to accumulate snow after clearing last time" -> but they might be cleaned partially no?
•  » » » » 6 years ago, # ^ |   0 I mean, i-th kilometer segment has 1 number lasti -- "when this segment started to accumulate snow after clearing last time". For each query of type '?' you'll get minmum of lasta, ..., lastb
•  » » 6 years ago, # ^ |   +10 L: Use inclusion-exlusion formula. We choose some subset of rows, columns and diagonals such that all cells there are equal and add  ± 2number of cells not covered by subset + number of connected components in subset to the answer. Without diagonals it is easy to do in O(n2). 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +20 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.
 » 6 years ago, # |   0 Ternary search passed problem A, is there a solution without ternary search?
•  » » 6 years ago, # ^ |   0 I got WA18 by nested ternary search. I got AC after eliminating one TS and did some reflection trick.
•  » » 6 years ago, # ^ |   +3 I solved it only with reflection trick, but costed me lots of time. Ternary search sounds better.
•  » » » 6 years ago, # ^ |   0 Isn't there quite a lot case work, if we solve just by reflection?
•  » » 6 years ago, # ^ |   +20 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Any idea what is WA 115 in A?
•  » » » 6 years ago, # ^ |   0 It's the case of parallel lines. Try something like -1 0 -1 and 1 0 2
 » 6 years ago, # |   +10 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! He announced that he would return shortly, after exactly k moments. Maggy knows the current lengths of all scarves and both stitching and unravelling a row takes her one moment. Help Maggy – compute how many scarves of equal length she can produce.
 » 6 years ago, # |   0 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 :( )
 » 6 years ago, # |   0 Upsolving page isn't working. It would be nice to have ability to upsolve problems which are div. 2 only (O, P or others).
 » 6 years ago, # |   +8 How to solve E , I ?
•  » » 6 years ago, # ^ |   +20 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 do mn[v][i] = min(mn[v][i], val), v = up[v][i] for both updates. And then push the values of mn[i][j] down to mn[i][j - 1] and mn[up[i][j - 1]][j - 1]. This way the lower vertex of edge (v, u) will have its mn[i][0] as the answer at the end.I am really terrible at describing solutions, my code will tell it better, I believe)
•  » » 6 years ago, # ^ |   +18 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.
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 The problem most recently appeared on VK Cup 2017 827D - Лучший вес для ребра. (Credit to ksun48 for digging up the problem, after contest of course.)
 » 6 years ago, # |   0 What about J?
•  » » 6 years ago, # ^ |   +5 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.
 » 6 years ago, # |   0 How to solve B?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 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 to X, whose Zeckendorf representation contains at most K terms. If Fi is the largest Fibonacci number less than or equal to X, f(X, K) = f(Fi - 1, K) + f(X - Fi, K - 1) holds. Write memoized recursion using this.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +10 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.
 » 6 years ago, # |   +8 rsFalse uses Perl for every problem :O