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

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

Сегодня в 21:00 MSD состоится Single Round Match 527. Так как темы до сих пор почему-то не было, я решил создать.

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

»
13 лет назад, # |
  Проголосовать: нравится -71 Проголосовать: не нравится
Ссылочку, пожалуйста.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Тебе везде ссылочку надо, как я посмотрю (:

    А сейчас куда ссылку? На TopCoder? Так она в посте есть.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Да мне сложно что ли? Я сделал уже давно. Не знаю правда ту ли ссылку которую человек хотел.
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

        А какую еще ему дать?

        На той странице есть ВСЕ, что нужно: ссылка на арену, на помощь, на время начала в других зонах (она, в принципе, и здесь есть), на правила. TopCoder в этом смысле очень хорошо структурирован.
»
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Субботний наш вечерный СРМ.
»
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
У меня экзамен завтра по математике, печально-то как :(
Обязательно бы написал TC, и так уже из-за сессии дофига пропустил SRM'ов.(
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какой сейчас лимит на число участников?
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится -49 Проголосовать: не нравится

Ребят, приношу извинения за тупость (может быть) . На ТС впервые.


задача 550, почему в примере {1, 3, 0} ответ 8, а не 12 ?
мы ведь можем соединить все вершины (ака квадрат получится)...

ЧИТАЮ УСЛОВИЕ...  вопрос снят.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится
    Пока идет раунд, задачи запрещено обсуждать. Даже просто условия.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -82 Проголосовать: не нравится
      кэп рулит.
      первый раз простительно. 
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +19 Проголосовать: не нравится
        Не простительно. Были бы админы слишком суровы, это был бы твой первый и последний раз.
»
13 лет назад, # |
  Проголосовать: нравится +122 Проголосовать: не нравится
System> Petr is viewing the source of Alex_KPR's 450-point problem.
...
System> Petr closed Alex_KPR's 450-point problem.

это всегда хороший знак =)
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +92 Проголосовать: не нравится

    Ну я просто смотрел, похоже ли решение на моё :)

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      А, если бы не было похоже, стали бы придумывать тест где отличается? И, как я понимаю, мелкие неточности(типа написал 1<<34 вместо 1ll<<34) вы не ищете, экономя время и предпочитая искать паленые идеи?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +29 Проголосовать: не нравится
        По-разному бывает. Когда решение длинное - то да, обычно ищу паленые идеи. Если совсем короткое - то читаю целиком ища и такие баги. Если догадываюсь, какой баг все должны сделать - сразу ищу его.

        Можно на "ты" :)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Это что-то типа

    "Все неправильные решения челенджит Петр, остальным автоматически выставляется Passed System Tests"?

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Зря после COCI его писал =/ такая ошибка идиотская
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать 250, 500?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    250. Подвесим за произвольную вершину, разобьем всеми возможными способами n-1 на часть , для них ответ посчитали также предварительно динамикой, прибавим к ответу scores[кол-во частей(+1 если считаем еще не ответ, а пром. состояние)] 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    250-ка:

    Заметим, что сумма степеней всех вершин у нас всегда 2*(n-1). Так как вершин всегда n, то наша задача сводится к рюкзаку. f[i][j] равняется максимальной сумме, когда у нас уже i вершин расставлена и сумма степеней у них равна j.
    Ответ = f[n][2*(n-1)]
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Надеюсь, это правильно...
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        У меня почти вся комната так решала, и мой сокомандник, который красный :)

        UPD: Мой сокомандник все-таки по-другому решал эту задачу :)

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится
      как осознать (кроме как заметив, порисовав на бумажке), что сумма степеней вершин в дереве 2 * (n - 1) ?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится
        Ребер n-1, ребро соединяет 2 вершины, следовательно сумма степеней 2*(n-1)
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А почему это работает?
      Я смотрел-смотрел твое решение и так и не понял.
      Сначала я написал именно рюкзак, но он не заработал на тесте {5, 0, 0}. N = 4, 2 * (N - 1) = 6 и рюкзак просто брал 6 вершин степени 1, что, понятно, неправильно.
      Я наделал if'ов, потом перебирал количество вершин степени 1, но так и не завелось.

      Кстати, на чем ты меня завалил?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        а откуда 6 вершин из 4х имеющихся?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Тест:
        10000 и 5 маленьких чисел
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Пусть у нас есть N вершин со степенями от 1 до N-1 и их суммарная степень равна 2N-2. Jacob снизу показал, как можно построить из них дерево с такими степенями - на каждом шаге берем вершину степени 1 (она есть по принципу Дирихле) и соединяем ее с другой вершиной (если шаг не последний, то степень другой вершины должна быть >1, но такая вершина тоже всегда есть)) и уменьшаем степень ее и ее нового соседа.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    а у меня одномерная динамика в 250
    пусть dp[k] - оптимум для дерева из k вершин
    поскольку у нас дерево, хоть один лист у него да есть
    возьмем любой лист и будем в цикле добавлять к нему вершины от 1 до тех пор, пока количество вершин в дереве не будет равняться N
    при этом у нас степень листа изменится с 1 на i + 1 и добавится i новых листьев
    что в конечном итоге даст нам: dp[k + i] = max(dp[k + i], dp[k] + (cost[i] - cost[0]) + cost[0] * i)
    ну и начальная инициализация dp[2] = cost[0] * 2

    Upd. Такое решение ниже описали, сорри)

»
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Здравствуй, второй дивизион! =)
»
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Я буду внимательно читать условия... В 450 долгое время думал, что и строки и столбцы можно менять местами. В итоге как уже в когда-то было, строки нельзя менять....
»
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
Блин, что же я в Medium'е так тупил. Давно же установил для себя главное топкодерское правило - если происходящее в задаче кажется непонятной хренью, скажи, что это граф. А здесь до парсоча догадался не сразу. И в dfs-е опечатка на пятьдесят очков.

По теме:
1) как доказывать решение в первой (то есть конструктивно строить дерево по весам)?
2) как третья делается? Я, видимо, научился делать ее, когда sum делится на a[n-1], в общем случае не могу придумать, что делать с остатками.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1) конструктивно??? А динамика не судьба?
    2) А еще очень забавно если прочитать что обе матрицы в непонятном порядке.
    3) Я умею выписывать красивые N вложенных сумм. Что с ними дальше делать не представляю.
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Нет, я динамику и написал. Может, это лажа, но у меня динамика находит разложение числа 2n - 2 на n слагаемых, каждое из которых лежит на отрезке [1, n - 1]. Как по таким весам дерево строить? Я ни способ найти не могу, ни контрпример.


      Тоже так подумал, но быстро перечитал и начал рисовать уже правильное.

      Ну да, суммы я тоже выписал. Получилось что-то похожее на COCI #2, задача 5. Так вот, если сумма делится на максимальное число, я умею приводить задачу к быстрому нахождению . Может, есть красивая формула, но я умею это делать за O(log2k). А в общем случае ничего не понятно.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Ну в первой можно другую динамику: по количеству поставленных вершин и по количеству вершин степени 1. На каждом шагу заменяем вершину степени 1 вершиной бОльшей степени. Тут вроде бы очевидно, почему верно.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          В первой вообще очень много динамик есть. Например по количеству вершин и степени корня.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            у меня просто динамика по количеству вершин, правда, весь СРМ ее делал ((
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          У меня похожее решение, но я убрал с динамики параметр " количество вершин степени 1 ", так как листья в дереве есть всегда, и не важно к какому листу мы цепляем новые вершины. Потому получился квадрат.
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        int D(int n, int k)
        {
            if (n == 0)
                return scores[k - 1];
            res = 0;
            for (int i = 1; i <= n; i++)
                res = max(res, D(n - i, k + 1) + D(i - 1, 1));
            return res;
        }
        

        k - степень корня, той вершины к которой мы сейчас будем детей подвешивать, n - количество вершин в данном поддереве не считая корня. перебираем по i количество вершин в поддереве первого ребенка D(i - 1, 1) - динамика для этого поддерева, прибавляем динамику остальных детей D(n - i, k + 1) - уменьшаем кол-во вершин, увеличиваем степень корня

        Ну а ответ на задачу это D(n - 1, 0). ну и запоминание нужно прикрутить к этой динамике.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    По поводу доказательства в первой: по принципу Дирихле есть вершина степени один. Подвесим её куда-нибудь в вершину степени больше 1 (при n>1 такие тоже есть). Повторим до готовности.
  • »
    »
    13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

    Мда... решать 275-ку 20минут, затем открыв 475-ку, мгновенно ее решив и еще минут за 5 написав хз сколько ловить опечатку в дфс-е (вместо u[i] было написано u[v]), а за оставшиеся полчаса решить, написать и (как мне кажется, с вероятностью 99%) добедагать 1050 с точностью до нескольких символов в одной строчке - столь эмоционального SRM-а у меня еще не было, жаль, что намного больше отрицательных эмоций, да и еще с красным цветом чуть было не попрощался.

    Вот что я писал в 1000-ке.

    Пусть V1<V2<...<Vn достоинства монет, Sum - необходимая сумма. Пусть Si=Sum/Vi.

    Общая идея такова - в любом множестве сначала склеим как можно больше монет V1 в монеты V2, потом склеим как можно больше монет V2 (с учетом полученных из склеивания V1) в монеты V3, и т.д. (кстати, в конце мы получим всегда один и тот же набор монет).

    Считать ответ мы будем разворачивая этот процесс. Будем считать динамику D[i][j] - где 1<=i<=n && 0<=j<mod и D[i][j] - число множеств (по модулю 10^6+3) которые могли получить после i-1 склеивания (т.е. в последний раз мы склеивали V(i-1) в Vi) в которых число монет Vi дает остаток j.  Осталось заметить, что в любом таком наборе число монет вида Vi равняется (Si%(V[i+1]/V[i]))+t*(V[i+1]/V[i]) - где t - это число монет V[i+1], склеенных из монет Vi. Причем число монет V[i+1], которые мы можем расклеить ограничено лишь их общим числом, причем все эти способы дают различные итоговые множества, т.е. если r=Si%(V[i+1]/Vi), d=V[i+1]/V[i], то D[i][j] - сумма некоторых D[i+1][что-то], причем D[i+1][k] участвует в качестве слагаемого в выражении D[i][j] тогда и только тогда, когда существует h<=k : j=(h*d+r)%mod. Осталось подсчитать суммы на суффиксах массивов D[i], чтобы пересчитывать каждый новый слой за линию, ну и заметить что все переходы от формул, которые очевидны в целых числах к кольцу остатков корректны.

    Upd. Ну, и конечно же, хранить достаточно только один слой и динамика получается с линией памяти.

    Upd.2. Да, это действительно работает. Очень обидно сливать 3-е место из того, что не хватило пары минут(

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В целом понятно. Я не догадался перейти к кольцу остатков (хотя маленький модуль намекал) и отталкивался от log(sum). Получается, что ответ на задачу для S равен ответу для S%mod? Я туплю и это следует считать очевидным или нет? 
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        S - это исходный Sum? Если да, то так сходу не понятно - я действую тоньше. Переход к кольцу остатков происходит лишь в итоговой формуле для D[i][j], которая с исходным Sum слабо связано. А вот почему именно в формуле для D[i][j] можно перейти к кольцу я особо понятно объяснять не умею - надо взять ручку и честно посмотреть самому, помня, что ответ для нас - это сумма D[0][i], т.е. прибавление какой-то константы сразу ко всем D[i][j] при i=const не влияет на итоговый результат, а потому на это забить - отсюда и понимаем, что множества из D[i][j] и D[i][j+mod] - эквиваленты с точки зрения конечного ответа.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится
    Мое решение харда: пусть f(i, j) - количество способов составить из первых i монет сумму j. Тогда f(i, j / values[i]) - многочлен. Доказывается по индукции - получается сумма многочленов по аргументам от 0 до чего-то, а это многочлен степени на 1 больше. Тогда просто будем считать эти многочлены путем аппроксимации сумм приедыдущих Ньютоном
»
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Эх, надо было сначала 450 открывать. Идейно она проще чем 275. В итоге почти все время убил на 275, но хоть прошла.
»
13 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится
Но я даже рад, что слил. Т.к. уйду с не очень хорошего места в общем рейтинге :) :
»
13 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится
Теперь я снова красный на топкодере и при этом в какой-то жёлто-оранжевой зоне здесь. Когда тут следующий вечерний контест, но не во вторник и не в пятницу?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится
    24.12.2011 (суббота) в 16:00 MSK.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится
      Хотелось бы, конечно, чуть более вечерний, ну да ладно, может и получится.