stostap's blog

Codeforces Beta Round 8. Task C,D,E.
By stostap, 13 years ago, In English
Task C.
I know solution with O(n * 2 ^ n). Why it is working with n = 24? n * 2 ^ n = 402653184

Task D.
I know that this task is for circle intersection. Who can give me more hint's?

Task E.
I have some ideas about Grey's code. But can't find good solution. Can someboby help me?

Thanks :)
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In the task C 4 × 108 operations will work no more than 4 sec on C++. It fits in the limit of 7.5 sec. If you will use "break" in cycle, it can decrease run time to 0.1-0.5 sec.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    But when I tried to make cycle to precalculate some index in for each mask for each position (n * 2 ^ n) it was work more then 5 minutes in my PC :) So I was amazing about how such solution get AC :)
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Task C - AC :)

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Task D - AC :)

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How did u solve task d ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used ternary search + binary search
    1) You can see if they both can go to Shop and after to Home
    2) If not then the point, to which they go together is inside trianlge Cinema, Shop, Home or on his sides.
    So you find with ternaty search the point on side Shop-Cinema (let it is point c1 and c2) then you on line (Cinema , c1) and (Cinema, c2) you can find the biggest distance, which they can go together going this line, with binaty search.

    answer is the binary search in line, which you find whith ternary search described above.
    P.S. also you can watch my code :)
    sorry maybe my poor English :)  
    → Reply