Nedy88's blog

By Nedy88, 12 years ago, In English

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 - Two Friends

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 - Beads

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

  • Vote: I like it
  • +30
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, I was wrong. It is not always working.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial. I don't think I could have solved E without hints. I still haven't solved it yet, but with this editorial there is still hope :)

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't solve Problem C. Can anyone tell me the approach? Thanks.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is a bitmask DP. Let dp[mask] be the cheapest way to collect all items denoted by mask. For each possible mask then you take the first item which was not collected yet + you try take any one additional item. So the complexity is O(n2n). Also when minimizing the value you need to remember the items you took to get there in order to get the full solution finally.

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      please can you elaborate how dp is working,I am a beginner.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      excuse me, can you explain why only need the first item but not all ?

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

wierd for problems of this round, can't view AC codes unless ACed the problem.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I was looking at solutions for Problem C(submission — 2795185). I get what marat.snowbear explains in the above comment. But, i have a fundamental doubt.

Why are we using "break;" in the code. We first build upon 'i', then add 2 objects 'j' and 'k'. But, why are we not building upon further on the solution obtained? And how are we able to manage without it?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See here there is no concept of last! everytime we compute for a mask the last coordinate we visit is of home.

    Now think in this way. While building the answer for 'i', take any 'on' bit. There are two cases 1. It is picked alone. 2. It is picked with one other object. That's it. This covers all the cases for 'i'. So we can compute for these two cases and then break i.e. only one bit is required. Hope it is clear!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

有ac代码吗

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think I could have solved E without hints.