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

Автор lperovskaya, история, 9 лет назад, По-русски

6 июня в 13:00 начнется третий отборочный раунд Яндекс.Алгоритма. Раунд продлится 100 минут по правилам TCM/Time.

Участие в нем может принести вам одну из 512 призовых футболок соревнования!

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

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

А что в итоге стало со вторым? Будет ли повторный второй раунд?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    "Время и дата раунда 2.2 уточняется, следите за обновлениями в расписании"

»
9 лет назад, # |
  Проголосовать: нравится +88 Проголосовать: не нравится

Второй контест подряд даёте баян с e-maxx.ru. Не хорошо.

»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

В чём смысл задачи А? За последние 10 минут, пока её решал, так и не понял, как именно падает кость на поверхность.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Случайно выбирается угол поворота, затем она ставится под этим углом и падает в какую-то сторону.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

У меня в F две Дейкстры TL-ятся... Что я делаю не так?

UPD Нашёл: я пытался релаксировать рёбра, исходящие из одной и той же вершины, несколько раз. Исправил — зашло за 1,5с.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Может, нет проверки на отсутствие отрицательных рёбер перед запуском Дейкстр?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня зашло за 366мс.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    TL стоит как 4x от решения с двумя Дейкстрами с сетом, действительно что-то делаешь не так :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А почему в сэмпле в E ответ 1/6?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А в первой задаче что имеется в виду под ориентацией сторон? Одна из четырёх или любая от 0 до ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    Ну, если бы одна из четырёх, то неясно, зачем даны размеры. Так что я предположил, что выбирается угол от 0 до , задал клар, получил "да".

    Но писать "равновероятно выбирается" в геометрии без хоть сколько-нибудь формального определения — крайне опасная вещь. Не понравилось мне это условие.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Вообще я не отправил в открытую только из-за этого странного условия. Ну и того, что Влад получил минус на первой минуте. :)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      А если угол от 0 до , то почему ни слова не сказано о том, как прямоугольник ведёт себя после падения и после этого следует считать верхней гранью?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Полагаю, что это автором считается очевидным из физических соображений.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    Угол. Но условие ужасно сформулировано.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Не то слово ужасно. До последней минуты верил, что угол не надо учитывать.(

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Почему организаторы так любят геометрию? :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Да ладно, сегодня вообще не было геометрий. Были 2 математики (A — тривиальная, E — долго и мучительно считать объёмы разнообразных политопов).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

      тривиальную задачу я еле-еле с девятой попытки за восемь минут до конца контеста запихал :))

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится -19 Проголосовать: не нравится

        Эм, а в чём были проблемы? Посчитать ответ на бумажке (в школах такие задачи в 8ом классе решают, ну, по модулю определения матожидания)? Или вбить с бумажки однострочную формулу?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Наверное, потому же, почему некоторые участники её не любят. Хотя мне кажется, что в этом раунде настоящей геометрии не было.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

      видимо, в зависимости от уровня крутости, люди видят задачи по-разному :) я как нубло вижу тут только геометрию, чемпионы мира видят иначе :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C: can you help me to find my mistake in my code(easy code)

»
9 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Автор задачи А, почему вероятностное пространство не определил? Что значит "равновероятно"? Равновероятно из чего, а?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Именно поэтому я не стал сдавать её "втемную".

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      А я еще и штраф нафармил, пока пытался понять, что имеет в виду автор (вот чего он не имеет — так это элементарной математической культуры, лол)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

What is the solution for C (Oceanic Battle) ?

and if anyone wants the solution for "A" , it is :

double a,b,c,d,e,f;
cin >> a >> b >> c >> d >> e >> f;
double theta = atan(a / b) * 180 / PI;
double s1 = (c + d) / 2.0;
double s2 = (e + f) / 2.0;
double ans = theta * s1 + (90 - theta) * s2;
ans /= 90.0;
printf("%.9lf\n" , ans);

The problem description (english) of "A" was not that good. I doubt how people got AC in 4 mins :O

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you should find the largest empty rectangle!

    and you can solve it with stack : code

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      Does that code work? For this test case:

      5 5
      1
      0 1 5 4
      

      your code prints 15 (on my computer), but there are just 10 empty cells, the other 15 are covered by the given ship.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        It works correctly, because you are required to calculate "the maximum possible value of a single ship in the final arrangement". The only ship given in your testcase has area equal to 15.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +19 Проголосовать: не нравится

          [insert facepalm here]

          So it seems I failed 2 problems because of trivial mistakes that have nothing to do with algorithmic part of the problems. I need to pay more attention to problem statements...

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    what's the description of A? I still can't understand the falling process?

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Are participants from other countries eligible for t-shirt prizes. Also how do they filter out top 500?? Any help will be appreciated.

»
9 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Перепутал аргументы у atan2

семплы прошли :(

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Так там семплы вообще никакие. В первом семпле квадрат, поэтому углы одинаковые. Во втором семпле на сторонах написаны одинаковые пары чисел, поэтому тоже можно перепутать. Я вот тоже перепутал и послал acos вместо asin.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Как решать С?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Задача C вообще решалась за кубическую асимптотику достаточно глупым алгоритмом с аккуратной реализацией.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Это здорово!

    Дорогие авторы, вы поставили такие ограничения, чтобы отсечь решения За n * n * log или что-то в этом духе.

    Но мое квадратичное решение с константой порядка 10 не проходит.

    Это не совсем правильно на мой взгляд. Хотя я, конечно, виноват первостепенно.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

EDIT: resolved.

Can anyone tell me what's wrong with my F? Still feeling stumped...

If some w_i<0 or c_i=0, then answer 0. Otherwise, find the shortest path (by short we mean sum of w_i) from s to everywhere and from t to everywhere using Dijkstra (which works since w_i>=0).

If the shortest path from s to t is at most b-a, answer 0.

Otherwise, there are 2 options, take the cheaper one:

Option 1: Make some edge negative at cost (w_i+1)*c_i.

Option 2: Only reduce the cost of some single edge i (say, from a to b) and take the shortest path that uses that edge (shortest from s to a, shortest from b to t, w_i). The cost is (weight_of_this_path — (b-a))*c_i. Of course, check for overflow before multiplying (It's easy to prove that the answer is at most 10^18+10^9).

Getting WA8.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Did you check the "s=t" case?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Consider a simple case: two vertices connected by an edge. You need to go from vertex 1 to vertex 1 (note that this works both for indexing from 0 and from 1 :D). The initial and final annoyance is the same. You pass through the only edge twice, so the weight of that path is 2w, but you only need to pay wc, not 2wc.

    Since you need to take at least one edge, it may be worth it to take one edge twice; you pay c for that edge to decrease the annoyance over this path by 2, not 1. There may be other weird situations...

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Huh, where does it say I need to take at least one edge?

      Task statement says: "A path of length (l — 1) is a sequence of intersections..." and "The number l is considered to be positive.".

      So, a path of length 0 means l=1, which is positive, so it's fine. Right?

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        Shit, that's what caused my solution to fail. If I add one line checking if I can make a 0-vertex path, it passes.

        You can still be in a situation where you want to take an edge twice, for example for a graph with edges 1-2 (w=0, c=inf), 2-3 (w=0, c=inf), 2-4 (w=0, c=1). If you want to go from 1 to 3 and a-b is -2, you want to take the path 1-2-4-2-3 and decrease the weight of edge 2-4. It's sufficient to decrease it to -1, with cost 1 and not 2.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yep, one option is to make any w negative and then just go back and forth on that edge many times. Option 1 in my OP.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I see, it does fall under that case when paths of length 0 are allowed. I solved it the same way, then, so you probably just have a different trivial mistake.

            • »
              »
              »
              »
              »
              »
              »
              9 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              May you please explain, why this solution is OK? What if our current edge v1-v2 is a part of the shortest path from s to v1 or from t to v2?

              I used the same approach during the contest, got WA 3, and I thought that the reason is the above case. But it turned out, that I had some other stupid bugs (s==t and long long overflow)

              • »
                »
                »
                »
                »
                »
                »
                »
                9 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                If there are no negative cycles (after decreasing weights), the optimal "path" doesn't contain an edge twice.

                Suppose that we went s-...-v1-v2-...-v1-v2-...-t (we traverse that edge at least twice in the same direction). Then, s-...-v1-v2-...-t is sufficient and doesn't have a bigger weight, so we can take this shorter path instead. After repeating this as long as necessary, we can be sure that no edge is traversed twice in the same direction.

                If we traverse it as s-...-v1-v2-...-v2-v1-...-t, we can take s-...-v1-...-t instead. We can again replace paths by shorter ones and after this, no edge is traversed twice.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится

        Yes, you are right. Test number 8 is the test with answer 1e18 + 1e9, are you sure you are not using infinity 1e18 ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    did you swap u and v while checking the edge? you have to check it from both ends

»
9 лет назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

Остался только один раунд, но я все-таки хочу сказать, что очень хочется, чтобы была возможность смотреть результаты друзей не перебирая по памяти ники... Такое ощущение, что это стало модно, абсолютно та же проблема и у RCC.

»
9 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

OK, so what's the formula in E? I hate such problems.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    For odd N, when (N + 1) / 2 is full square, answer is sqrt((N + 1) / 2) / (N! * 2 ^ ((N — 1) / 2)). Otherwise answer is 1. For even N, when (N + 1) is full square, answer is sqrt((N + 1)) / (N! * 2 ^ (N / 2)). Otherwise answer is 2 ^ (N / 2) / N!. Here is AC solution http://pastebin.com/Zsi2m9Qw

»
9 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Будут ли открытые тесты для этого контеста? Интересует 5 у B и C.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Вот такой баг замечен: попытка искать в результатах раунда по Ctrl+F приводит к какому-то странному дублированию строк. Вот пример: https://youtu.be/PqxJ3KUtVrc

Это, видимо, всегда было на ЯК, помню такое еще несколько лет назад.

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

"Participation might bring to you one of the 512 competition t-shirts!"

Does that mean I'll get a T-Shirt even if I did not get a single solution correct, since the number of participants was less than 512?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А можно где-нибудь увидеть общие результаты по итогам двух раундов?

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Табличка только почему-то без учета штрафного времени

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Забавно, что решившие суммарно хотя бы одну задачу за два раунда начинаются с 450 места, а футболок 512.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ничего, впереди еще один раунд, число решивших хотя бы одну задачу за три раунда будет больше 512!

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Не мог ли кто-нибудь поделиться реализацией задачи C? Сделал всё так, как у e-maxx, но почему-то не проходит тесты(

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    Максимальным может быть один из кораблей, которые были заданы изначально.

    Всё как у e-maxx ищет максимальный корабль, который можно добавить.

    Код http://pastebin.com/njL1yBni

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А можно как-то узнать тесты к задачам?

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Is there any way to see/edit the address I used in the registration? I moved recently and would like to make sure there's my new address in case I win a T-Shirt.

Thanks.

»
9 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

одному мне кажется, что отборочный этап завершился полным провалом? За 3 раунда всего 800 человек сделало хотя бы одну попытку что-то сдать, из них только половина получила хотя бы один AC. Просто напоминаю, какие ожидания были до начала: link

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

On T-shirts:

a) to see if you are eligible for T-shirt — check this link:

https://contest.yandex.ru/algorithm2015/results/

if you are in first 512, then you should be eligible.

b) An hour ago I've got e-mail from Yandex, confirming that I've won the T-shirt. E-mail also contained link to special page where you can provide your address for delivery.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А есть возможность самовывоза футболочек?

»
9 лет назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

Насчёт футболок ничего не слышно? Уже как бы 3 месяца прошло...

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Извините, что поднимаю старую тему, но не могу не сказать организаторам спасибо за клевую футболку! :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    я чуть не выйграл ету футболку трепещите, я иду))))

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Извините, что также поднимаю старую тему, но мне так ничего и не пришло. :( Может, можно из офиса забрать? :)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Мне в понедельник только позвонили. Думаю еще есть шанс дождаться

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ура, таки пришла, спасибо за клевую футболку ^_____^