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
.
- Point
P
must be inside a circle with center 'cinema' and radiusx
. This follows directly from the main observation. x + distance(P, home) <= T2
— Bob must be able to go home in time. This condition means thatP
must be inside a circle with centerhome
and radiusmax(0, T2 - x)
.x + distance(P, shop) + distance(shop, home) <= T1
— Alan must be able to go home in time. This condition means thatP
must be inside circle with centershop
and radiusmax(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
Sorry, I was wrong. It is not always working.
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 :)
I couldn't solve Problem C. Can anyone tell me the approach? Thanks.
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.
please can you elaborate how dp is working,I am a beginner.
excuse me, can you explain why only need the first item but not all ?
wierd for problems of this round, can't view AC codes unless ACed the problem.
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?
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!
樱文题解呀
有ac代码吗
In my opinion,you'd better ask your question in English.
He's asking"Is there any Ac codes?"
Are there any AC codes? He means...
For Problem C... Hint -> don't forget we can either pick one or two object at a time and then we have to go to the origin
For further explanation check the spoiler
First though process would be-> states as [mask of objects picked up and, previous element]. Then you would pick the current element either alone or with an additional element.
BUT this would definitely exceed time limit.
So think of the problem like this. We do not need to worry about the previous element, why?? Because if we pick either one or two objects at a time we will go to origin for sure. So previous element will always be the origin. Now simply take a mask, choose the first element which has been picked up , take it as a single object. Also take this object with all other possible 'on' bits in the mask.
For ex :- if there are three objects ->( I am counting from right for the bits)
mask — 001 , I take the first bit(right most) , calc it's distance as single element then I consider all other 'on' bits as second element with this object(none are there).
mask — 010 — take second bit as single object
mask — 011 , now take first bit as single element , and then take it with second bit for two objects at a time.
In this manner you'll see all possibilities will be covered... I hope this helps
How to solve the C problem..I got stuck on how to use bitmask dp in this question...
I don't think I could have solved E without hints.