Recently, I started solving codeforces problems from the beginning. I just solved Codeforces Beta Round 8. I couldn't find any tutorial for the round so I decided to write tutorial for the last two problems. The others I solve long time ago in the real contest. Problem E took me quite some time and I couldn't find even a discussion about it, so here are my solutions.

D. 8D - Два товарища

The main observation for this problem is the following: If Alan and/or Bob is at some point X and moves following some curve and travels distance d, then the point at which they finish can be ANY point on or inside the circle with center X and radius d. In other words: If you start at some point X and go to some point Y, you can do this on as long curve as we want(only not shorter then the distance(X, Y). Now, for convenience, lets say that T1 is the longest allowed path for Alan and T2 is the longest allowed path for Bob. These values are easily calculated:

T1 = distance(cinema, shop) + distance(shop, home) + t1
T2 = distance(cinema, home) + t2

Now, there are two cases. The first and trivial case is when distance(cinema, shop) + distance(shop, home) <= T2. In this case, it is OK for Bob to go to the shop with Alan. If they go to the shop together there is no need for them to ever split. So they go together all the way from the cinema to the shop and then from the shop to their home. In this case the solution is min(T1, T2) Why? (Hint: here the observation in the beginning is important).

The second case is when Bob cannot go to the shop with Alan. We'll solve this case with binary search on the distance that they could cover together before splitting. Let's assume that the go to some point P together covering some distance x. After they split Bob goes home in straight line and Alan first goes to the shop in straight line and then goes home again in straight line. This circumstance forces three condition for the point P.

1. Point P must be inside a circle with center 'cinema' and radius x. This follows directly from the main observation.
2. x + distance(P, home) <= T2 — Bob must be able to go home in time. This condition means that P must be inside a circle with center home and radius max(0, T2 - x).
3. x + distance(P, shop) + distance(shop, home) <= T1 — Alan must be able to go home in time. This condition means that P must be inside circle with center shop and radius max(0, T1 - x - distance(shop, home).

Now we have three circles and if they intersect, then it's possible to choose point P in such a way that Alan and Bob will the together the first x meters of their journey.

Now, the problem is to check if three circles intersect. I come up with easy solution for this problem. I haven't proven it correct, but it seem to work. I don't know if there is some standard algorithm for this problem. My idea is the following. Let the 3 circles be C1, C2 and C3. If C1 and C2 intersect they do it in one or two point. Now we check is some of these points is inside C3. If there is such point, then the 3 circles intersect, but if there is no such point, it doesn't necessarily mean thath the 3 circles doesn't intersect. We should try all permutations of the 3 circles. That is we first check C1 and C2 and the intersected points with C3, then C1 and C3 and the intersected points with C2, and so on.

Here is my solution for reference: 1632676

E. 8E - Бусы

This is quite an interesting problem for me. We must find the k-th lexicographically smallest number from a subset of the numbers from 0 to 2^N(It is easier to increase K with one and consider the all zeroes and all ones case, too). The numbers which we want to count are those which are smaller or equal to their inverted number(flip zeroes and ones), their reversed number(read the bits of the number from right to left) and their reversed and inverted number.

Let's call a prefix the first half of the numbers, i.e. when only the first N/2 bits are set. Since N <= 50, there are at most 2 ^ 25 such numbers. Also we will only consider numbers with 0 at the first bit. If it is 1, then the inverse number will be smaller, so there are at most 2^24 prefixes. Now if we have some prefix, using dynamic programming we will see in how many ways can we finish it to a real number. The state of the dp is: (int pos, bool less, bool lessInv) and dp[pos][less][lessInv] is the number of ways to finish the number if we have to choose the pos-th bit now. less shows if so far we are less then or equal to the reversed number and lessInv shows if so far we are less then or equal to the inverted and reversed number. Using the dp we could easily find the k-th number.

There is one final note. The DP here is run for every possible prefix and the prefixes could be up to 2^24. Every time we clear the DP table before running it. This makes the solution slow even for the 5 seconds time limit. There is one more observation which makes the solution run in time. We iterate the prefixes in order, that is in each step newprefix = oldprefix + 1. In this case only the last few bits of the prefix are changed. The other part of the prefix remains the same and there is no need to clear the whole DP table, only the parts that changed due to changing the last few bits. This is left for exercise and my solution using this method is: 1644014