### SimB4's blog

By SimB4, history, 6 years ago, translation,

Let's discuss problems.

What was your solution for problems E and J?

• +31

 » 6 years ago, # |   0 Auto comment: topic has been translated by SimB4 (original revision, translated revision, compare)
 » 6 years ago, # |   0 We've done problem G with Suffix Array + Segment Tree + Treap in each vertex of ST. May be there is simpler approach?
•  » » 6 years ago, # ^ |   0 More details?
•  » » » 6 years ago, # ^ |   +8 Let's reverse both strings. Then let build suffix array on string S'#T'. For each suffix you have pair (suffixIndex, a[suffixIndex]). Now, to find answer to query you need to find appropriate suffix of t in suffix array, then find interval where this t can be found as prefix using lcp. On this interval you need to find sum of a[i]'s where i is in [s1, s2], which can be done with Segment Tree + Treap in each node of Segment Tree.
 » 6 years ago, # |   0 What is the upper bound we need to count knapsack dp in D? I counted up to 500000 and got OK, but how to prove it?
•  » » 6 years ago, # ^ |   0 It is guaranteed that aj = 1 for some j (1 ≤ j ≤ n). The answer <= 4000 => upper bound is 400000
•  » » 6 years ago, # ^ | ← Rev. 4 →   +19 Actually you can use upper bound = 4000 as you can move both up and down, so you can calculate answer in such a way that all middle values do not exceed max(k, 2·max(ai)).
 » 6 years ago, # |   0 J is an old GCJ problem.(I had trouble with TL, maybe because of a heavy constant — if someone has a solution that works under 0.5s, could you share it?)K: Let dp[x] be the optimal score we can get from a square of side lengths x. It turns out that dp[x] is approximately 0.0755605242906x3, so with some calculus we can get the optimal square size approximately. Is there a simpler solution?
•  » » 6 years ago, # ^ |   0 We can find dp[x] with binary search
•  » » » 6 years ago, # ^ |   +5 For a given x, we want to find i that maximizes (x - 2i)2i + dp[i] * 4. How do we use binary search here?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Look here: for (int i=3;i<=1000000;i++) { int l=1; int r=(i-1)/2; while(l+1
•  » » » » » 6 years ago, # ^ |   +3 So, did you assume that the function is convex?Actually the function is not convex (for example, print V for a = b = 10000 and various x, the function has both local maximum and local minimum), but it seems your solution works for magical reasons.
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 For random a = b = N I found only one local maximum and only one local minimum; for example, if N = 10000, then local minimim is at 1736 and local maximum at 4462,and if N = 3456, then local minimim is at 600 and local maximum at 1542. Each time the local minimum is greater than N / 4, so it doesn't infuence on the binary search.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 We assumed that since derivative is linear then optimal solution can be found incrementally (optimal point for dp[x] shouldn't be less than optimal point for dp[x + 1]) or with ternary search.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 We can calculate dp[x] linearly.Lets define z as optimal size of the squares that we need to cut from corners of our square of size x to get optimal result dp[x].We can notice that z can only increase if we increase x. So when we calculate dp[x] we can keep this value z that is currently provides best score for x - 1, we can push z to the right while it improves our answer. So z will be pushed right less than 106 times.
•  » » 6 years ago, # ^ |   +10 J code is here. This runs in 215 ms.
 » 6 years ago, # | ← Rev. 2 →   +3 How to solve E?
•  » » 6 years ago, # ^ |   +14 We have quite complicated solution, I wander if there exists a simpler one.Find all blocks of the graph. If there exists block with vertices of all three colors then answer is YES. You can always find necessary cycle. For example, it's possible to find an edge with two endpoints of distinct colors, find a vertex with the third color and find a cycle containing that edge and that vertex (as I remember there is a theorem that a graph is 2-vertex-connected if and only if for each edge and vertex of the graph there exists simple cycle going through the edge and the vertex).Cycle can be found with maxflow if the vertex is source and endpoints of the edge are sink. Complexity will be O(maxflow·(M + N)) = O(2(M + N)) = O(M + N).If no such block exists answer is NO.
•  » » 6 years ago, # ^ |   0 If a tour exists, it will be contained in a single block (biconnected component). Hence we process each block separately. If every block contains at most two types of breweries, the answer is NO.Otherwise take vertices a, b, c of different types of breweries and compute two internally vertex disjoint paths between every pair of them. If they contain the third type of brewery, we join the two paths to a cycle to get a tour.Otherwise (this part actually never executed on the judge) just remember one path between every pair. Our goal is to make these 3 paths internally vertex-disjoint. If we take two paths, then they share one vertex X out of and the other two endpoints Y, Z differ. Let U be the vertex furthest from X that is contained in both of the paths. Note that U has the same brewery type as X. Taking the subpaths from Y to U and form Z to U makes them vertex disjoint without loosing any brewery type. Repeat this for all pairs.
 » 6 years ago, # |   +11 Is there a nice Solution for I? If you do binary search for the water level and decompose the iceberg into tetrahedra with 3D-convex-hull, the problem reduces to finding the volume of a tetrahedron clipped with a half-space.My approach was to integrate the horizontal cross-section (it's piecewise quadratic if we exclude discontinuities) of the tetrahedron by using Simpson's rule on each piece. This leads to some problems with faces perpendicular to ez, as the cross-section is not continuous there.
•  » » 6 years ago, # ^ |   0 You can clip not tetrahedra, but facets of the iceberg (it is much easier), then you have to compute the volume of a convex polyhedron defined by its facets, which is straightforward.
•  » » » 6 years ago, # ^ |   0 But how do you find faces easily? Won't n^4 timeout? or it's not if you check the points in random order?
•  » » » » 6 years ago, # ^ |   0 I found faces in O(n^4) and it passed even though I did all calculations in long doubles.
•  » » 6 years ago, # ^ |   +10 That's my approach as well (integrate piecewise quadratic function). To avoid the issues you mention, I just used segments [i;i+1] (since z is between -100 and 100) and integrated using three points i+0.25, i+0.5, i+0.75, to avoid hitting any vertices. And to find the cross-section I just intersected segments collecting all pairs of points with the plane and found convex hull. That seems to make the code quite sane, modulo convex hull with floating-point inputs.
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ |   +26 Bruteforce precalc works.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -10 Answers:3 14 15 26 57 338 3199 966610 48410111 8612625112 92110261613 69066775514 27777273515 16892764716 86396677717 65671024918 52921172319 95255251720 22627619221 19794988422 30518208023 47305794324 911957625 60761001326 80040136427 12588190128 40439407429 4734165530 12686603931 93707792932 680342212
•  » » 6 years ago, # ^ |   0 Yet another representation: if we think of target string as concatenation of strings A = "01", then operations mean that we can push each A to left for 1 position (first push is creation). we can see that every state of process can be described as point (l1, l2, l3, ..., lk), k — number of A's, and li — number of pushes of Ai to left and li > li + 1 must be satisfied for every i. Hence, the whole process is a path from (0, 0, ...0) to (n - 1, n - 3, ..., 2 - n%2). So You are to calculate the number of specific paths. Actually, the reason that first answers are Catalan numbers (1, 1, 2, 5) is that it counts the number of paths not exceeding diagonal.