XXII Open Cup, Grand Prix of BSUIR

Let's discuss the tasks here.

How to solve problem B?

• 9 hours ago, # ^ | ← Rev. 3 →   0 No. There is simple O(n2)O(n2) greedy solution. Note that 11 is always in the answer. Then we should greedily add vertices 22, 33, ... For example, we want to add ii to the answer. We should also add all vertices from ii to 11 and for each we should check that there are no bad vertices added. We can note that check for each vertex need O(n)O(n) time, and if we check all vertices once, we will achieve O(n2)O(n2).

  • 6 hours ago, # ^ | ← Rev. 2 →   0 if we check all vertices once How can we accomplish this? Can you elaborate more? Other than that, my solution is same, except using bitsets to speedup the check to O(nw)O(nw).

    • 5 hours ago, # ^ | ← Rev. 2 →   +7 Suppose we are trying to add vertex vv to the current set SS and we find a path from vv to SS: v=p1,p2,...,plv=p1,p2,...,pl (pl∈Spl∈S). Then we just iteratively check if pipi is consistent with S∪S∪{pi+1,...,pl−1pi+1,...,pl−1}. If we find that some vertex pjpj is a not consistent and we stop at vertex pjpj, we simply mark all vertices in {p1,...,pjp1,...,pj} bad and do not need to re-calculate the consistency of them anymore. On the other hand, if no bad vertices are found, then we just add p1,...,pjp1,...,pj to set SS. From this you can see that for each pair (u,v)(u,v) we check at most once if the path from uu to vv is a palindrome of length greater than kk.

• 11 hours ago, # ^ | C: For a fixed kk we need to choose g=gcd(a,b)g=gcd(a,b), then a′=a/ga′=a/g and b′=b/gb′=b/g are coprime divisors of k, and gg should be a divisor of k/a′b′(a′+b′)k/a′b′(a′+b′), so you can calculate the number of solution by trying all the possibilities for a′a′ and b′b′ and then calculating the number of divisors. So, to have a lot of solutions kk should have a lot of divisors, so let's generate some reasonable set of candidates (something like highly composite numbers but a bit looser) and check only them. With some very loose criteria (use only primes up to 40, each prime exponent starting from 5 is at most 1 greater than the previous one) works a couple of minutes on my laptop. I would not be surprised if it is possible to choose some tighter criteria so the solution can run on server and fit in TL.

• 10 hours ago, # ^ | There is a well known problem about two players playing a game with probability of winning equal to p for the first player (see https://en.m.wikipedia.org/wiki/Gambler%27s_ruin). You just need to tend the amount of money for one of the players to infinity

  • 10 hours ago, # ^ | I see, thanks

  • 9 hours ago, # ^ | ← Rev. 5 →   0 I have some different solution: Let's solve the problem for one dimension (for many dimensions we should multiply probabilities for separate dimension). Consider we are at position 1. Let's see all possible ways to get 0. We can count this ways using correct bracket sequences. For +1 we will use "(" and for -1 we will use ")". So, probability to get 0 we can calculate using this simple formula: P=C0⋅q+C1⋅p⋅q2+...=(∑∞0Ci⋅(p⋅q)i)⋅qP=C0⋅q+C1⋅p⋅q2+...=(∑0∞Ci⋅(p⋅q)i)⋅q. So we can use generating function of Catalan numbers: G(z)=1−1−4⋅z√2⋅zG(z)=1−1−4⋅z2⋅z. We should calculate G(p⋅q)⋅qG(p⋅q)⋅q. Then we should understand, that if we was at position x, then answer is (G(p⋅q)⋅q)x(G(p⋅q)⋅q)x. Another solution: Let's ww — probability to get −1−1 after some movements. Then w=p+q⋅w2w=p+q⋅w2

• 113 minutes ago, # ^ | Consider the "tightest" constraint in each direction: the leftmost right edge, the rightmost left edge, the topmost bottom edge, and the bottommost top edge. Clearly, we should never place points further outside than these edges. If the leftmost right edge and the rightmost left edge cross, then all rectangles must share a common x-range, so 1D greedy; likewise with the other two. Otherwise, in order to cover all rectangles, there must be at least one point on each of these 4 edges. For m<=3m<=3, this means at least one point must cover two of these edges, so we can pick one of the 4 corners and recurse on the remaining rectangles with m−1m−1. This takes O(4mn)O(4mn) time. For m=4m=4, either one point covers two edges (in which case we pick a corner and recurse on m=3m=3) or there is exactly one point on each edge. Let's visualize the 4 edges as a rectangle, where we pick one point on each side. In this case, each shelter rectangle imposes one of a few types of constraints: If the shelter fully contained, then m=4m=4 is impossible. If the shelter fully covers one side, then it is always satisfied. If the shelter covers a corner, then it imposes an OR constraint on the two adjacent sides. If the shelter intersects two opposite sides, then it imposes an OR constraint on the two opposite sides. Now, let's pick/sweep over all possible locations of the point on the left edge. If this is fixed, then we should greedily pick the points on the top and bottom to be as far right as possible. In particular, casework on either the top point or bottom point to be further left, and choose it as far right as possible to avoid breaking OR constraints with the left side and top/bottom OR constraints. Then, choose the other top/bottom point as far right as possible. Finally, check if there is a valid choice of the right point. To implement this, we just need to be able to query, for a particular choice of one point, which range constraints does it impose on the others. This can be done with several range-update point-query-min/max seg trees, approximately one on each pair of sides. This leads to an O(nlog(n))O(nlog⁡(n)) time solution. Interestingly, this paper claims to also give an O(nlog(n))O(nlog⁡(n)) solution for m=5m=5: https://www.cs.bgu.ac.il/~segal/pierce.pdf. Code