Single Round Match 527

12 лет назад, # ^ |

Тебе везде ссылочку надо, как я посмотрю (:

А сейчас куда ссылку? На TopCoder? Так она в посте есть.

→ Ответить

PavelKunyavskiy

12 лет назад, # ^ |

Да мне сложно что ли? Я сделал уже давно. Не знаю правда ту ли ссылку которую человек хотел.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

-9

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

На той странице есть ВСЕ, что нужно: ссылка на арену, на помощь, на время начала в других зонах (она, в принципе, и здесь есть), на правила. TopCoder в этом смысле очень хорошо структурирован.

→ Ответить

ivan.popelyshev

12 лет назад, # |

-9

Субботний наш вечерный СРМ.

→ Ответить

Alex_KPR

12 лет назад, # ^ |

+52

"Субботний наш вечерный СРМ", сказал ivan.popelyshev, оставив все задачи в состоянии unopened ;)

→ Ответить

ivan.popelyshev

12 лет назад, # ^ |

+53

Зато поспал хорошо.

→ Ответить

12 лет назад, # |

У меня экзамен завтра по математике, печально-то как :(
Обязательно бы написал TC, и так уже из-за сессии дофига пропустил SRM'ов.(

→ Ответить

SkyHawk

12 лет назад, # |

Какой сейчас лимит на число участников?

→ Ответить

12 лет назад, # ^ |

2300, вроде.

→ Ответить

SyFy

12 лет назад, # |

← Rev. 2 →

-49

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

~~задача 550, почему в примере {1, 3, 0} ответ 8, а не 12 ?~~

~~мы ведь можем соединить все вершины (ака квадрат получится)...~~

ЧИТАЮ УСЛОВИЕ... вопрос снят.

→ Ответить

pkhaustov

12 лет назад, # ^ |

+31

Пока идет раунд, задачи запрещено обсуждать. Даже просто условия.

→ Ответить

SyFy

12 лет назад, # ^ |

-82

кэп рулит.

первый раз простительно.

→ Ответить

12 лет назад, # ^ |

+19

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

→ Ответить

Alex_KPR

12 лет назад, # |

+122

System> Petr is viewing the source of Alex_KPR's 450-point problem.

...

System> Petr closed Alex_KPR's 450-point problem.

это всегда хороший знак =)

→ Ответить

Petr

12 лет назад, # ^ |

← Rev. 2 →

+92

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

→ Ответить

JKeeJ1e30

12 лет назад, # ^ |

А, если бы не было похоже, стали бы придумывать тест где отличается? И, как я понимаю, мелкие неточности(типа написал 1<<34 вместо 1ll<<34) вы не ищете, экономя время и предпочитая искать паленые идеи?

→ Ответить

Petr

12 лет назад, # ^ |

+29

По-разному бывает. Когда решение длинное - то да, обычно ищу паленые идеи. Если совсем короткое - то читаю целиком ища и такие баги. Если догадываюсь, какой баг все должны сделать - сразу ищу его.

Можно на "ты" :)

→ Ответить

valikluks1995

12 лет назад, # ^ |

+18

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

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

→ Ответить

Tranvick

12 лет назад, # |

Зря после COCI его писал =/ такая ошибка идиотская

→ Ответить

Scorpy

12 лет назад, # |

Как решать 250, 500?

→ Ответить

riadwaw

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

250-ка:

Заметим, что сумма степеней всех вершин у нас всегда 2*(n-1). Так как вершин всегда n, то наша задача сводится к рюкзаку. f[i][j] равняется максимальной сумме, когда у нас уже i вершин расставлена и сумма степеней у них равна j.
Ответ = f[n][2*(n-1)]

→ Ответить

dalex

12 лет назад, # ^ |

Надеюсь, это правильно...

→ Ответить

12 лет назад, # ^ |

← Rev. 4 →

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

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

→ Ответить

dalex

12 лет назад, # ^ |

Passed System Tests. Just as planned.

→ Ответить

luckyi

12 лет назад, # ^ |

-16

как осознать (кроме как заметив, порисовав на бумажке), что сумма степеней вершин в дереве 2 * (n - 1) ?

→ Ответить

12 лет назад, # ^ |

+14

Ребер n-1, ребро соединяет 2 вершины, следовательно сумма степеней 2*(n-1)

→ Ответить

luckyi

12 лет назад, # ^ |

мда.. логично.. спасибо

→ Ответить

caustique

12 лет назад, # ^ |

А почему это работает?

Я смотрел-смотрел твое решение и так и не понял.

Сначала я написал именно рюкзак, но он не заработал на тесте {5, 0, 0}. N = 4, 2 * (N - 1) = 6 и рюкзак просто брал 6 вершин степени 1, что, понятно, неправильно.

Я наделал if'ов, потом перебирал количество вершин степени 1, но так и не завелось.

Кстати, на чем ты меня завалил?

→ Ответить

luckyi

12 лет назад, # ^ |

а откуда 6 вершин из 4х имеющихся?

→ Ответить

12 лет назад, # ^ |

Тест:
10000 и 5 маленьких чисел

→ Ответить

12 лет назад, # ^ |

Пусть у нас есть N вершин со степенями от 1 до N-1 и их суммарная степень равна 2N-2. Jacob снизу показал, как можно построить из них дерево с такими степенями - на каждом шаге берем вершину степени 1 (она есть по принципу Дирихле) и соединяем ее с другой вершиной (если шаг не последний, то степень другой вершины должна быть >1, но такая вершина тоже всегда есть)) и уменьшаем степень ее и ее нового соседа.

→ Ответить

sweiss

12 лет назад, # ^ |

← Rev. 2 →

а у меня одномерная динамика в 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. Такое решение ниже описали, сорри)

→ Ответить

SkyHawk

12 лет назад, # |

Здравствуй, второй дивизион! =)

→ Ответить

Kenny_HORROR

12 лет назад, # |

+15

Я буду внимательно читать условия... В 450 долгое время думал, что и строки и столбцы можно менять местами. В итоге как уже в когда-то было, строки нельзя менять....

→ Ответить

12 лет назад, # |

-10

Блин, что же я в Medium'е так тупил. Давно же установил для себя главное топкодерское правило - если происходящее в задаче кажется непонятной хренью, скажи, что это граф. А здесь до парсоча догадался не сразу. И в dfs-е опечатка на пятьдесят очков.

По теме:

1) как доказывать решение в первой (то есть конструктивно строить дерево по весам)?

2) как третья делается? Я, видимо, научился делать ее, когда sum делится на a[n-1], в общем случае не могу придумать, что делать с остатками.

→ Ответить

PavelKunyavskiy

12 лет назад, # ^ |

1) конструктивно??? А динамика не судьба?

2) А еще очень забавно если прочитать что обе матрицы в непонятном порядке.

3) Я умею выписывать красивые N вложенных сумм. Что с ними дальше делать не представляю.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

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

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

Ну да, суммы я тоже выписал. Получилось что-то похожее на COCI #2, задача 5. Так вот, если сумма делится на максимальное число, я умею приводить задачу к быстрому нахождению $\text{[math]}$ . Может, есть красивая формула, но я умею это делать за O(log²k). А в общем случае ничего не понятно.

→ Ответить

KADR

12 лет назад, # ^ |

Ну в первой можно другую динамику: по количеству поставленных вершин и по количеству вершин степени 1. На каждом шагу заменяем вершину степени 1 вершиной бОльшей степени. Тут вроде бы очевидно, почему верно.

→ Ответить

PavelKunyavskiy

12 лет назад, # ^ |

В первой вообще очень много динамик есть. Например по количеству вершин и степени корня.

→ Ответить

1a1a1a

12 лет назад, # ^ |

у меня просто динамика по количеству вершин, правда, весь СРМ ее делал ((

→ Ответить

OutSide

12 лет назад, # ^ |

У меня похожее решение, но я убрал с динамики параметр " количество вершин степени 1 ", так как листья в дереве есть всегда, и не важно к какому листу мы цепляем новые вершины. Потому получился квадрат.

→ Ответить

goo.gl_SsAhv

12 лет назад, # ^ |

← Rev. 2 →

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). ну и запоминание нужно прикрутить к этой динамике.

→ Ответить

Jacob

12 лет назад, # ^ |

+13

По поводу доказательства в первой: по принципу Дирихле есть вершина степени один. Подвесим её куда-нибудь в вершину степени больше 1 (при n>1 такие тоже есть). Повторим до готовности.

→ Ответить

Dmitry_Egorov

12 лет назад, # ^ |

← 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-е место из того, что не хватило пары минут(

→ Ответить

12 лет назад, # ^ |

В целом понятно. Я не догадался перейти к кольцу остатков (хотя маленький модуль намекал) и отталкивался от log(sum). Получается, что ответ на задачу для S равен ответу для S%mod? Я туплю и это следует считать очевидным или нет?

→ Ответить

Dmitry_Egorov

12 лет назад, # ^ |

S - это исходный Sum? Если да, то так сходу не понятно - я действую тоньше. Переход к кольцу остатков происходит лишь в итоговой формуле для D[i][j], которая с исходным Sum слабо связано. А вот почему именно в формуле для D[i][j] можно перейти к кольцу я особо понятно объяснять не умею - надо взять ручку и честно посмотреть самому, помня, что ответ для нас - это сумма D[0][i], т.е. прибавление какой-то константы сразу ко всем D[i][j] при i=const не влияет на итоговый результат, а потому на это забить - отсюда и понимаем, что множества из D[i][j] и D[i][j+mod] - эквиваленты с точки зрения конечного ответа.

→ Ответить

Egor

12 лет назад, # ^ |

+14

Мое решение харда: пусть f(i, j) - количество способов составить из первых i монет сумму j. Тогда f(i, j / values[i]) - многочлен. Доказывается по индукции - получается сумма многочленов по аргументам от 0 до чего-то, а это многочлен степени на 1 больше. Тогда просто будем считать эти многочлены путем аппроксимации сумм приедыдущих Ньютоном

→ Ответить

Jokser

12 лет назад, # |

Эх, надо было сначала 450 открывать. Идейно она проще чем 275. В итоге почти все время убил на 275, но хоть прошла.

→ Ответить

Jokser

12 лет назад, # |

-15

Но я даже рад, что слил. Т.к. уйду с не очень хорошего места в общем рейтинге :) :

→ Ответить

_jte_

12 лет назад, # ^ |

-6

А что плохого в этом числе?

→ Ответить