Let's discuss problems.

What was your solution for problems E and J?

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

Let's discuss problems.

What was your solution for problems E and J?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 19:46:49 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been translated by SimB4 (original revision, translated revision, compare)We've done problem G with Suffix Array + Segment Tree + Treap in each vertex of ST. May be there is simpler approach?

More details?

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 oftin suffix array, then find interval where thistcan be found as prefix using lcp. On this interval you need to find sum ofa[i]'s whereiis in [s_{1},s_{2}], which can be done with Segment Tree + Treap in each node of Segment Tree.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?

It is guaranteed that aj = 1 for some j (1 ≤ j ≤ n). The answer <= 4000 => upper bound is 400000

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(a_{i})).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 lengthsx. It turns out thatdp[x] is approximately 0.0755605242906x^{3}, so with some calculus we can get the optimal square size approximately. Is there a simpler solution?We can find

dp[x] with binary searchFor a given

x, we want to findithat maximizes (x- 2i)^{2}i+dp[i] * 4. How do we use binary search here?Look here:Where V is:

So, did you assume that the function is convex?

Actually the function is not convex (for example, print

Vfora=b= 10000 and variousx, the function has both local maximum and local minimum), but it seems your solution works for magical reasons.For random

a=b=NI found only one local maximum and only one local minimum; for example, ifN= 10000, then local minimim is at 1736 and local maximum at 4462,and ifN= 3456, then local minimim is at 600 and local maximum at 1542. Each time the local minimum is greater thanN/ 4, so it doesn't infuence on the binary search.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 fordp[x+ 1]) or with ternary search.We can calculate

dp[x] linearly.Lets define

zas optimal size of the squares that we need to cut from corners of our square of sizexto get optimal resultdp[x].We can notice that

zcan only increase if we increasex. So when we calculatedp[x] we can keep this valuezthat is currently provides best score forx- 1, we can pushzto the right while it improves our answer. Sozwill be pushed right less than 10^{6}times.J code is here. This runs in 215 ms.

How to solve E?

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.

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,cof 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

Xout of and the other two endpointsY,Zdiffer. LetUbe the vertex furthest fromXthat is contained in both of the paths. Note thatUhas the same brewery type asX. Taking the subpaths fromYtoUand formZtoUmakes them vertex disjoint without loosing any brewery type. Repeat this for all pairs.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

e_{z}, as the cross-section is not continuous there.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.

But how do you find faces easily? Won't n^4 timeout? or it's not if you check the points in random order?

I found faces in O(n^4) and it passed even though I did all calculations in long doubles.

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.

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?

Bruteforce precalc works.

Answers:3 1

4 1

5 2

6 5

7 33

8 319

9 9666

10 484101

11 86126251

12 921102616

13 690667755

14 277772735

15 168927647

16 863966777

17 656710249

18 529211723

19 952552517

20 226276192

21 197949884

22 305182080

23 473057943

24 9119576

25 607610013

26 800401364

27 125881901

28 404394074

29 47341655

30 126866039

31 937077929

32 680342212

Yet another representation: if we think of target string as concatenation of strings

A= "01", then operations mean that we can push eachAto left for 1 position (first push is creation). we can see that every state of process can be described as point (l_{1},l_{2},l_{3}, ...,l_{k}),k— number ofA's, andl_{i}— number of pushes ofA_{i}to left andl_{i}>l_{i + 1}must be satisfied for everyi. 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.