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

Автор chrome, 12 лет назад, По-русски

Всем привет!

Завтра, в 20.00 MSK состоится Topcoder SRM 626.

Предлагаю после контеста обсудить здесь задачи.

GL & HF

UPD: Контест закончился. Обсуждаем задачи.

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

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

Thanks, seems like I'm going for my first SRM ever :)

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

It conflicts with Codingame challenge

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

HELP! Не могу зайти на свой аккаунт с арены Ubuntu. С другого ноута заходит, но с моего ноута нельзя зайти ни в какой аккаунт :(

Ошибка: Invalid combination of username and password.

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

Can someone explain why in 500 we get a huge negative score in example 1 using a self loop from a final vertex (vertex 1), but in example 3 we are not allowed to go back and forth between vertices 1 and 2 to get a huge negative score?

Thanks!

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

Как решать Div1 250?

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

    Считаем, какая вероятность получить ровно i для каждого игрока (например, динамикой), пусть это pi для первого и qi для второго. Тогда ответ — по определению матожидания. И надо не забыть про случай с "-1".

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

      А в нем надо не забыть a × b  ≤  c, вместо  < .

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

      Как доказать что точность будет подходить ? чисто теоретический интерес.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
        ← Rev. 4  
        Проголосовать: нравится +14 Проголосовать: не нравится

        Я знаю следующие возможные проблемы с даблами:

        1) Где-нибудь теряется много точности из-за вычитания чисел примерно одного порядка.

        2) Где-нибудь возникает число по модулю больше 10^308, и получается бесконечность.

        3) Где-нибудь возникает число по модулю меньше 10^-308, и что-нибудь важное обращается в ноль.

        4) Где-нибудь происходит много операций с денормализованными числами (около 10^-308), и все работает в 50 раз медленнее.

        Здесь 3) могло бы произойти со знаменателем, но не произойдет, потому что вероятность каждого элементарного исхода не меньше 50^-100. Соответственно, с 4) тоже все в порядке. 1) и 2), очевидно, в порядке.

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

Как решать div2-1000?

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

How was Div2 1000 problem to be solved?

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

В 1000 к сожалению последовательность гуглится на oeis.org. Да, авторы добавили a и b, чтобы было сложнее гуглить, и да, можно решать включением-исключением без гугла. Но всё же...

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

lol, я вообще не решил ни одну из задач, но мой рейтинг поднялся))

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

My fail on 900 this time was quite unusual: the whole problem can be siplified to counting sum of squares of integers coprime to and (the answer's that times a2 + b2), but for some mysterious reason, I decided to count the sum of squares of non-divisors. Not to mention I didn't notice that and though that I'm only failing on the last sample due to some hidden overflow, because what else could cause me to pass the other large sample? (Of course, it's the fact that is a power of 2 in all samples except the last one and the one where the answer's trivially 0.) Boop.

In the end, this reduction's easily solvable by Google Search Algorithm...

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

Кто нибудь может доказать что Форд-Беллман с дополнительным параметром является неправильным решением к div2 1000?

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

А на TopCoder можно дорешивать? И если да, то куда нужно заходить? я что-то не пойму :(

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

For problem 250 div 2 I have solved it with a really fast algorithm but it's status is "challenge succeeded" . I don't know what it means ?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +25 Проголосовать: не нравится

600 див1 как решать?

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

    Я так решал: Посчитаем сначала кратчайшие расстояние между всеми парами вершин, без использования отрицательных ребер. Допустим это G[u][v].

    Теперь будем считать кратчайшие пути с использование не более 2i отрицательных ребер. F[i][u][v] — длина кратчайшего пути из u в v используя не более 2i отрицательных ребер.

    Для 20 — посчитаем влоб: для всех пар u и v выберем минимум по всем ребрам (fromi, toi, wi) выражения G[u][fromi] - wi + G[toi][v]. Пусть это будет F[0][u][v].

    Для остальный 2i при i > 0 будем считать так:
    F[i][u][v] = min(F[i - 1][u][v], minw(F[i - 1][u][w] + F[i - 1][w][v]).
    Т.е. переберем некоторую промежуточную вершину w и воспользуемся 2i - 1 отрицательными ребрами на пути от u к w и на пути от w к v.

    Теперь чтобы посчитать ответ с заданным ограничением — разобьем наш лимит на количество отрицательных ребер по степеням двойки и соберем ответ. Пусть наш лимит . Я решал это динамикой по типу Форда-Беллмана -- dp[i][u] — минимальная стоимость пути от исходной вершины, причем мы шагнули через первые i степени двойки из need.
    dp[0][0] = 0.
    dp[i][v] = minu(dp[i - 1][u] + F[needi - 1][u][v]).

    Ответ min(dp[|need|][n - 1], G[0][n - 1]).

    Ассимпотика получается примерно такой: O(V2·E + V3·log(charges)).

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

      Видимо, это решение можно вкратце описать следующим образом: заметим, что одна итерация Форда-Беллмана действует на массив расстояний как умножение на матрицу с операциями (min, +), поэтому массив расстояний для положительных ребер надо умножить на соответствующую матрицу с отрицательными ребрами в нужной степени. Очень крутая идея, ни разу раньше не встречал. И жаль, что не придумалось за контест.

      UPD: просто Форд-Беллман на исходном графе в данном случае не сработает, потому что положительные и отрицательные ребра могут чередоваться. В матрице aij надо сделать равным длине минимального пути из i в j, содержащего не более одного отрицательного ребра.

  • »
    »
    12 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +16 Проголосовать: не нравится

    У меня другое решение. Работает за O(n5), это полторы секунды на случайном тесте максимального размера. Возможно, можно подумать и сократить время работы хотя бы до O(n4).

    1. Посчитаем динамикой f(k, u, v): минимальное расстояние от вершины u до вершины v при инвертировании не более чем k рёбер по пути. Пригодится таблица примерно до k ≤ n2 + n. У меня это делается за O(n5).

    2. Интуитивно понятно, что для очень больших значений charges выгодно потратить почти все заряды в наиболее «удельно выгодном» для этого цикле данного графа — то есть найти такую вершину u на цикле и такое k > 0, что отношение f(k, u, u) / k максимально. Возможно, нужно будет ещё потратить немного зарядов по дороге от начальной вершины до этого цикла, а также по дороге от этого цикла до конечной вершины. Естественно, пути от начала до u и от u до конца должны существовать.

    3. Утверждение (без доказательства): оптимальный путь состоит из предпериода длины r ≤ n2, периода длины d ≤ n, повторённого целое число раз s, и постпериода длины t ≤ n2. То есть ответ — это минимум f(r, 1, u) + f(d, u, u)·s + f(t, u, n), где r + d·s + t = charges.

    4. Переберём длину предпериода и длину периода. Длину постпериода будем подбирать как можно ближе к n2 + ε, чтобы не перебирать. Если она получится слишком большая, в ней окажется ещё несколько копий периода. У меня это делается за O(n4).

    5. Пример теста (взлом), в котором предпериод и постпериод не могут одновременно быть порядка n: ориентированный цикл из n вершин, в котором можно в одном месте сократить путь на одну вершину. Если, например, n = 50, цикл перебирает вершины по порядку и нужно сделать ровно 2425 шагов от вершины 1 до вершины n, то у диофантова уравнения x·50 + y·49 + 49 = 2425 есть единственное решение с ограничениями x ≥ 0 и y ≥ 0: это x = 24 и y = 24. То есть нужно 24 раза пройти по одному пути и 24 раза по другому в любом порядке.

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

How was Div1 600 problem solved?