Блог пользователя stostap

Codeforces Beta Round 8. Task C,D,E.
Автор stostap, 13 лет назад, По-английски
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 :)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 :)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Task C - AC :)

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Task D - AC :)

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How did u solve task d ?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 :)  
    → Ответить