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

Codeforces Beta Round #82 (Div. 2)
Автор Ripatti, 13 лет назад, По-русски

Добрый вечер.

Сегодняшний раунд, как и прошлый, опять мой. Этот раунд будет для участников второго дивизиона, однако участники первого дивизиона тоже смогут принять участие вне конкурса.

Раунд мне помогали готовить RAD, Connector, it4.kp, а также MikeMirzayanov. На английский язык условия перевела Delinur.

На этот раз контест будет проходить в старых добрых традициях Codeforces. Никаких нововведений, в меру короткие и понятные условия.

Разбалловка задач стандартная: 500-1000-1500-2000-2500.

Всем удачи!


UPD. Раунд завершен, рейтинги обновлены.

Победители:

1. tsundere

2. jte

3. abacadaea

4. ltaravilse

5. Billy_Herrington

Разбор задач.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Давно просто div. 2 не было. Написать что ли по фану...
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
there are any precision issues like last contest :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
By the way who is Delinur? Isn't he a coder or someone who belongs to CODEFORCES? Moreover i appreciate his/her translations. Thanks for all your great works. :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is rating affected by reading the problem statements? Or only if you try to submit a problem?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Good luck and good ratings to everyone
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I wonder why people gave negative votes to Mehran-r but gives  positive votes to schirevko? I think that there is no difference between those comments at all. 
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Короткие и понятные условия. Ура. Они услышали глас народа. Спасибо. Удачи всем
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

(70 * 2)3 * 100 операций с даблами - в запуске 1.3 сек. Это кодфорсес, детка:)

P.S. - увидел прекрасное и спешу поделиться. Пропих wrong на задачу Е великолепен! Получил от него чисто эстетическое удовольствие!
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я явно чего-то не понимаю в этой жизни. Ведь задача Е, очевидно, включает в себя центр сферы по 4 точкам, так?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Или по 2 в конце диаметра или по 3 на центральной окружности. Но в общем вроде да.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      66 человек ее сдало...
      Пора мне на пенсию...
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        tourist тоже не сдал, ему тоже пора, сразу после школы :)
        → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Я же прав, что ещё можно её вогнать тремя вложенными тернарниками по каждой из координат? Потому что функция len(v) - расстояние от точки v до наиудалённейшей планеты из точки = mini{|v - vi|} где vi - положение i-ой планеты - функция выпуклая.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Можно, но нужно грамотно для новых границ трихотомии определять, принадлежит ли новая точка текущему многограннику.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не нужно. Если она не принадлежит, то расстояние не улучшится.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          но функция же себя вроде бы не так хорошо ведет, или я неправ?
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ещё раз. Функция f(v) = |v - v_i|, где v_i - какая-то фиксированная точка, точнее, одна из планет - выпуклая вниз очевидно.
            А максимум из набора выпуклых вних функций - тоже выпуклая функция. Тернарники летают, как показывает практика.
            → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не хватило 20ти секунд чтобы заметить тупой баг в D Т_Т
Глубокий 2 дивизион, привет.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И не говори...
    Я North и South местами перепутал и вместо + был - и наоборот в D. Заметил за 20 секунд до окончания но ничего уже не мог поделать...
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Так это же первым претестом уже ловится вроде бы, который в условии был.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я видел что у меня не тот результат но не мог понять почему ...
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я писал на жабе, и она мне выкинула экпшен за границы, поэтому и отловил быстро.
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
+ авторам контеста! условия очень порадовали! спасибо! ждем разбора :)
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

У меня вопрос к составителю контеста:
Ответ будет засчитан, если расстояние от данной точки до самой удаленной планеты будет отличаться от результата жюри не более чем на 10 - 6 по абсолютному или относительному значению.

Давайте прикинем. Посчитать расстояние, кроме как корень из суммы квадратов длин проекций вектора на оси мы, вроде, не можем.
Если d имеет погрешность 10 - 6, то d2 должно иметь погрешность 2d, то есть 2 * 10 - 6. Значит, каждый из трёх квадратов чисел, стоящих под корнем в d должно иметь погрешность 2 / 3 * 10 - 6 < 7 * 10 - 7. Каждый из этих трёх квадратов имеет порядок 108, значит нам нужен тип данных, держащий значимых цифр.
Стандартный дабл (кроме которого, например, в VC++ ничего нет) гарантированно держит 15 цифр. Не знаю как вы, а я бы побоялся давать задачу с такими узкими рамками.

UPD:
0_o зашла...
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "или относительному"
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      А, проглядел. Сейчас, пойму, что это значит в контексте погрешностей логарифмов...

      UPD:
      Так может и пройти, будем ждать систесты.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ого, по всем нашим постам пробежали злобные минусеры. Кто ж так не взлюбил задачу Е?:)
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Погодите. пусть верный ответ - (x, y, z), а мы дали (x+e, y+e, z+e). Погрешность 2*e*(x+y+z)+3*e2 не должна превышать 2*10 - 6. Максимальное х -104, значит порядок е должен быть 10 - 10, как-то так, нет?
    ПС.  Впрочем, теперь и мне стало стрёмно за мои 70 итераций тернарника..:)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Во-во :-) Сейчас я всех перепугаю, как сам напугался к концу контеста))
      У нас получилось в результате x2 + y2 + z2 + 2 * e * (x + y + z) + 3 * e2, а вся эта величина - порядка 3 * 108 из-за первых трёх членов. И уже она должна иметь маленькую погрешность порядка 10( - 6).
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      То что у меня зашло претесты, дает неверный знак уже на 3й позиции числа на входном тесте...
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У меня на тесте:
        1
        10000 10000 10000
        тоже ошибается уже на третьем-четвёртом знаке, походу :-(
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну, логично. Выскакивает квадрат, получается 10 - 6 и оно по краю заходит. А вот когда ответ близко к 104 по координатам, Ваше решение должно начать чудить. Как, впрочем, и все остальные, вероятно.
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Горе от ума:)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I love this contest!
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
great contest..good questions (and this time shorter too).Although my ratings wont increase much but i enjoyed the contest.It was fun and a lot of learning.Thanks Ripatti:)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
testing not started yet?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Usually, when you submit a task, and it fails, it does say whether your solution had WA or TL. My submission was hacked, so I tried to find an error in it. Finally, when I resubmitted it, it said TL on hack 1.

It seems inconsistent. If it told be TL with the initial hack message, I would know what to fix straight away... :(
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Great contest! This was my first official contest (since the other one was unrated due to an unusually difficult problem), and I really enjoyed it. It was a good balance of difficulty and coding and thinking.
Can anyone help me with problem E? I know you have to find the minimum enclosing sphere, and that's what I was trying to do, but a lot of other people just seem to be starting at a arbitrary point and stepping towards the correct solution. I was considering this approach, but thought it was too risky, so I'm curious as to what the intended solution is. Since a sphere is uniquely determined by 4 points, the obvious algorithm is O(N^4), but I was wondering if anyone had a faster algorithm. If so, can you please refer it to me? Thanks in advance. (Sorry if this isn't the right place to post this, move this if necessary)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why isn't it possible to see the hacked test case after the contest?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Anyone can explain how to solve problem E?
I had an idea, but I'm not quite sure if it works.
Let C be the optimal point, R be the maximum distance from C to any other point in the input and S be the sphere with center at C and radius R. We have 3 cases:
1 - S has 2 points from the input on its surface in which case C is the center of the line connecting these 2 points.
2 - S has 3 points from the input on its surface in which case C is the center of the circle connecting these 3 points.
3 - S has 4 or more points from the input on its surface and we can determine the center easily given 4 points.
Nice contest BTW, but problems A to D are a bit easier than usual I think.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    That was what I was thinking as well too, but O(N^4) is a little big especially for N=100. 

    The smallest enclosing circle can be found in O(N) time: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm, but I'm not sure how to extend that to 3-d, and what the time complexity would be then too.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Straightforward implementation will be O(N^5). It can be improved to O(N^4), but it's too hard for Div 2 contest.

      I think the intended solution is Hill climbing
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        more details?
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Read accepted solutions. They are very short.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            I loved this solution. BTW do you know other problems that can be solved using Hill climbing? Are these solutions very common?
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Many marathon matches in TopCoder require some kind of Hill climbing or Simulated Annealing.

              However, I have never seen it used in any kind of algorithm competition before. I would also be grateful if somebody could give me some more examples of problems with solutions like these.
              → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            How do you choose the numbers though? They seem pretty arbitrary. I looked through some of the div2 submissions that failed, that either timed out because their stepsize was too small, or wrong answer when their stepsize was too big. Thanks.
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              I have the same question with you. My solution is wrong answer at case 10 because of the stepsize is only 100. but when i set it to 500, 700 or even 1000, it is wrong answer just at case 7.
              → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Considering x and y coordinates only, can't we find minimum enclosing circle's centre and then search for required z coordinate because min_z <= z <= max_z,
            min_z = min. z coordinate in given set of points
            max_z = max. z_coordinate in given set of points

            Though, it might be inefficient as answer can be real number instead of integer value.
            → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        I got O(N^5) accepted by loop unrolling (Upd: actually, the final version works faster without it =) ).

        There are quite a few solutions with nested ternary searches accepted, too.
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Actually it seems that problem E can be solved in linear time according to the original paper by Mediggo in 1983 (see here for reference and code library).

      But I doubt this was the expected solution to implement, as it took like more than a century since the smallest enclosing circle problem was posed by Sylvester in 1857 for a linear algorithm to be found ...
      → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Has anyone thought about using inversion?
    edit: never mind.  I guess I wanted apply a trick in practice like in here, but it doesn't seem to help.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится


      Here is an approach:

      -  Isolate a center point.  Call it C.  Separate it from the others.  We search for a minimum sphere that contains C.

      - Invert with respect to C.  A sphere that contains C is inverted to a plane that does not contain C.  A point inside the sphere is inverted to a point on the other side of the plane.
      In particular, the minimal enclosing sphere is inverted to a plane that is as far as possible from C, and such that all points are on the other side from C.

      - Find the 3d convex hull, in O(N lg(N)), deduce the farthest plane in O(N).

      - Invert again, to get the minimum sphere.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Посмотрите статус - там люди сейчас сдают задачи с этого контеста... Как?!
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Дорешивание.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Дорешивать, когда идёт ожидание системного тестирования? Я проверял - кнопки такой нету, ты уверен, что это дорешивание? 
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Во время ожидания можно, а во время тестирования - нет, насколько я понимаю.
        → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I didn't perform very well on this contest, but I really liked the problems. Thanks Ripatti :)
From A to D it's quite easy to find a solution, but I wasted the first hour on E (because it seemed to me very similar to this).
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Буду внимательно читать условия!!!

Буду внимательно читать условия!!!

Буду внимательно читать условия!!!

Буду внимательно читать условия!!!

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ололо, вот это я мастер... Я умудрился завалить A и C, но вогнать в E тернарник.
Мне понравился этот контест, только надо было его с конца писать))
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Нда. Лично у меня в E проходят 79 итераций тернарника и не проходят 80.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А если сабмитить под GNU C++, то заходят и 80 итераций, то есть в точности мой код с контеста. Удивительное рядом.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Проверял перед отправкой на вкладке Запуск. MS VC++ на 80 итерациях работал около 2300 мс. Сдал на GNU C++ - максимальное время 1690 мс.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я тоже проверял на запуске - работало порядка 1730 мс, если память не изменяет. Правда значения координат были маленькими.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
По E прошло решение за CN4 * N. За 1940 миллисекунд. Да!!!
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    О_о, круто.

    Вот у меня шаманство с квадродеревом не прошло 2й претест по времени =\
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А как ее решать квадродеревом, если не секрет? Что делается после спуска в некую вершины дерева, у которой нет потомков?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Про вершину, у которой нет потомков я не вполне понял вопроса.

        Вообще я пробовал 2 подхода:

        1) Бинпоиск по ответу с октадеревом для нахождения точки пересечения: жёстко тормозит даже на тесте из условия.
        2) Спуск по дереву с поиском минимума: находим значение нашей функции в центре текущей области. Если он больше текущего минимума как минимум на половину "диаметра" области, то отсекаемся иначе спускаемся во все 8 потомков.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А, ясно. Я просто думал о квадродереве, которое обычно строят на точках - разделение на 4 квадрата пока кол-во точек в квадрате превышает некую константу. А тут просто спуск пока есть шанс улучшить. Спасибо.
          → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я шизею.
    THIS
    IS
    CODEFORCES!!!!!!!11
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
About my solution for problem D:

http://gyazo.com/0b862656e379b4d4512a513fe884ac36

It seems to be correct, but the checker says this is wrong answer.
I want some explanation about this.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Now I know the problem.

    My program's output contains leading '\0's.

    That was my program's bug :(
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А когда пересчитают рейтинг?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
there was lot of submission for problem E but only a few passed. What is the solution for this prob?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I like all problems except C. To understand this problem required Oxford dictionary...
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Код по задаче Е у индийца utkarshl даже с копирайтам какого-то ученого из Цюрихского университета :D Причем код здоровенный... И кусок с копирайтом даже два раза написан
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, собственно, не только у него
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а зачем надо было писать что он индус? разве это имеет какое то отношение к делу? просто мне кажется что такими сообщениями вы ухудшаете общее впечатление о нации.... так сказать)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это важно разве что для того чтобы понять что он не автор, ничего другого. Он сам ухудшает отношение к его нации, поступая таким образом. Как показывают результаты, не он один
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hello , can anybody give me the full 5th test of problem D? in the editor only half of it is seen 
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why the rating didn't get updated yet?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is there a way to know the full test case that my solution fail on? When I'm looking at the Judge protocol it shows only n first bytes of the test case.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

8th on the division and only +97?! I have got +176 before for rank 49th and less number of contestants with approximately the same rating! Is there volatility like TopCoder or what?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I feel that when falling to div 2 , it's very hard to return to div 1 because being in top 20 div 2 just add so few rating.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Well they are just updated 
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Another good problemset from ripatti :).
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Народ объясните, плиз, почему в 3 задаче в 10 тесте:
10 2 13 100
20 1 3 10
20 1 2 6

ответ 32... а не 30???
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Are the ratings updated for the "out of competition" participants?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "out of competition" contestants are really out of competition :) So there are no new rating for them.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вы даже не представляете какие глупые решения проходят на задачу Е

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Функция просто очень хорошая. Если бы она не была такой выпуклой, градиентный спуск бы не работал.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      даа, надо было мне это решение на контесте писать, после контеста я его блин за 3 минуты написал)
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
[code]
point center;
double iter = 1000000.0;
while(iter > 0.0)
{
iter -= 1.0;
double step = (iter/10000.0)*(iter/10000.0);

int id = 0;
double max_s = 0.0, d;
for(int i = 0; i < n; i++)
{
d = center.dist2(v[i]);
if(d > max_s)
{
max_s = d;
id = i;
}
}
double dx = p[id][0]-x;
double dy = p[id][1]-y;
double dz = p[id][2]-z;
double s = fabs(dx)+fabs(dy)+fabs(dz);

if(fabs(s) < 1e-8)
break;

x += dx/s * step;
y += dy/s * step;
z += dz/s * step;

}
cout << center.x << " " << center.y << " " << center.z << endl;
[/code]
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
простое численное решение. Во время контеста я даже писать его не хотел, дкмал как-то глупо. Вообще прикольно)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
any one can explain what this statement mean in problem "C"
Lavrenty knows that he has ai grams left of the i-th stuffing
thanks
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Lavrenty knows that he has ai grams left of the i-th stuffing. It takes exactly bi grams of stuffing i and ci grams of dough to cook a bun with the i-th stuffing.


    With bi of i-th stuffing (and ci of dough) baker can make a bun. So if he has ai grams, he can make at most ai/bi (integer division) buns with i-th stuffing.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Oh, I had a hard time understanding this, seriously.
      I misread this way:

      Lavrenty knows that he has ai grams of dough left after using the i-th stuffing. It takes exactly bi grams of stuffing i andci grams of dough to cook a bun with the i-th stuffing.

      So I asked a question and the answer was sth like "please read statement" :)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        I read the same thing as you hence I was puzzled for a moment before realizing reading the sentence twice solved my bewilderment.

        I guess the following formulation would have been less prone to misinterpretation : « Lavrenty knows that he possesses ai grams of stuffing i. It takes exaclty ... ».

        But part of solving a problem is understanding its statement =)
        → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        В принципе, решать E можно еще проще, без какого-либо тернарного поиска - этакий метод наискорейшего спуска - light.
Берем произвольную стартовую точку. Для нее выбираем самую удаленную планету. Чуть-чуть двигаемся в сторону самой удаленной планеты (например на 0,1 этого расстояния). И так много-много раз. Потом уменьшаем коэффициент, с которым мы продвигаемся в сторону самой удаленной планеты.
И все.  
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Выше уже обсуждалось.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
            Объяснение тому весьма банальное.  Через час после контеста прочитал задачу E - обычный метод градиентного спуска, почти 20 лет как читаю студентам. Жалко, что не прочитал во время контеста, всяко проще и C и D. Наутро закодил и тут же, не прочитав  все комментарии (на глаза попались только лишь про тернарный поиск), написал об этом методе.   
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Greetings,

During the contest some fatboy hacked my solution for Treasure Island, the verdict was TLE. But when i see other solutions i see that people are doing simple brute force. Now my question is, the problem says "Walk n miles in the y direction" is the form of instructions and i see that accepted solution just jump directly n miles and dont check all the blocks in between. Isnt this wrong? Tell me.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Let Up[i][j] will be the maximum free cells Up from (i, j) and Left[i][j] - will be the same for left direction. So, to check is there any block to the North: if (Up[i][j] >= n) that's all, you can jump to the north, having enough free cells for moving.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Let a[i][j]=1 if the cell is blocked and 0 otherwise.
      Then, for example, the way from (x, y) to (x+dx, y) is clear if a[x][y] + ... +  a[x+dx][y] = 0.
      These sums can be precalculated just after reading the matrix and then obtained in O(1) time.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I'm sorry but can the author of this round tell me why my program return the wrong answer on test 12 of the C problem on Div2. I ran it on my computer and it return the correct answer. Sorry because I don't know ask you where :D.
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Unfortunately I missed this round. but when I was solving problems today I wrote exactly same algorithm for Problem D in java and c++, but java got TLE and c++ got Accepted.
Isn't getting a problem accepted, algorithm dependent and language independent?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I believe no, 'cause my java solution got accepted with 420ms as maximal execution time per test. So, if you have good algorithm and realization, u'll pass system tests in majority of cases.
    Here is my source code, if any.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      yeah, you're right, my algorithm wasn't good.
      but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.
      otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges.

      BTW, you used Thread, how much faster is it than using a simple class?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.- this is wrong in some cases, e.g. some manipulations with memory, etc.
        otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges. - This was discussed, and  MikeMirzayanov mentioned this will be done some day.
        Nowadays using Thread's  not much faster than using simple class, it's a kind of tradition)
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I think it's OK that timelimit is same

          1) You can choose C++ and be availabale to shooting your legs or choose Java, get safe, but someproblems with timelimit

          2) adavydow wrote here about example of set big timelimit for ruby:
          > most of string problems solved more easy in Ruby, then in other languages because they are only optimized library function call(writed on C/C++). There are a lot of example of passed O(n^2) ruby solution instead of O(n) C++ ones
          Besides, not-standart algo's in Ruby overwise can be not passed, even with good asymptotics

          So, as I can see it may solve old problems badly and get new problems
          → Ответить