Facebook HackerCup 2013. Round 2.

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

И сразу вопрос: можно ли сменить настройки часовой зоны в FB, так чтобы во event'ах отражалось местное время

→ Ответить

_dangerous_

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

ссылку можно?

→ Ответить

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

Пока нельзя:)

→ Ответить

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

Добавил

→ Ответить

qwerty787788

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

"You will only be able to access the round if you were in the top 500 from Round 1" — а условия можно будет смотреть?

→ Ответить

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

-8

Думаю, да.

→ Ответить

Winnie_Pooh

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

Три задачи будет?

→ Ответить

Edvard

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

Еще ни разу не было не трех задач)

→ Ответить

eduardische

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

Меня вообще печалит что в Facebook'е на футболки скупятся. У них же огромный запас ещё с 2011 года должен был остаться, когда обещали 300, а раздали 150, потому что никто больше ничего не решил...

→ Ответить

nurzhands

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

+17

На футболках год написан?

→ Ответить

eduardische

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

-6

В 2011 вроде не было (перед, зад).

→ Ответить

NALP

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

+11

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

→ Ответить

Edvard

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

Они же вроде каждый год одни и те же?

→ Ответить

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

На прошлогодней на рукаве написано "2012".

→ Ответить

eatmore

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

+17

А почему пост написан 12.12.2012?

→ Ответить

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

-8

Наблюдателен)

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

→ Ответить

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

А как узнать точную дату поста? Я умею только "2 месяца назад"

→ Ответить

NALP

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

навести курсор на надпись "2 месяца назад" :)

→ Ответить

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

-9

Интуитивная понятность такая понятная :D

→ Ответить

alexyz

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

← Rev. 3 →

Сейчас по ссылке "Запрашиваемая вами страница не найдена." Это из-за того, что я не допущен до 2-ого раунда ?

UPD: Ссылка на таблицу работает.

→ Ответить

qwerty787788

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

LOL, видимо так facebook борется с нагрузкой на их сайт... fail. Выложите кто-нибудь условия посмотреть, пожалуйста.

→ Ответить

NKolotey

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

-29

Если это не является нарушением правил, может ли кто-нибудь объяснить почему в пятом тесте второй задачи (про роботов) аж 60 туров, если роботы такие умные? По мне так кажется, что только 15 роботов, которым не грозит утилизация могут откосить, остальные, обладая сообразительностью, могут догадаться, какая их ждёт судьба, тем более, что второй пример как раз об их догадливости. То есть раунд должен бы состояться всего один.

→ Ответить

eatmore

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

+35

Ну вот я уже всё решил... И чего это раунд такой длинный?

→ Ответить

NALP

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

-42

не, у меня другой вопрос... почему еще не все всё сдали?

→ Ответить

Edvard

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

-26

У кого-то time expired по третьей((

→ Ответить

Sedols

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

-14

turi muti

→ Ответить

Sedols

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

-24

кому твои яйца надо было сдать.

→ Ответить

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

← Rev. 3 →

Codeforces, такой codeforces. Тут всегда минсуют заявления оранжевых и красных о том, что всё было тупо, или даже если содержится хоть малейший намёк на то, что всё было тупо. Просто потому, что сине-зелёных гораздо больше.

И, в общем-то, правильно. Конечно, зависть — плохое чувство, но, всё же надо понимать эмоции людей, для которых пройти во второй раунд было уже достижение, и которые с трудом сдали 1 задачу, и это для них прогресс — многие просто потому, что опыта мало, или просто регион такой, что учить толком некому. Таких людей надо поддерживать и вдохновлять, а не демотивировать...

→ Ответить

Sylvanas

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

Заявления синих и зелёных о том, как всё сложно, минусуются так же усердно :)

→ Ответить

I_love_natalia

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

Я могу назвать N > 1 красных участников Codeforces, которые не сдали все три задачи на этом контесте.

→ Ответить

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

Конечно, ведь три задачи сдали только 52 человека, а красных на кодфорсесе ~200 человек. Ну и что?

→ Ответить

tunyash

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

← Rev. 2 →

Расскажите, пожалуйста, как решать третью.

→ Ответить

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

← Rev. 4 →

UPD: не зашло

Ясно, что дано дерево. Решим задачу для поддерева для каждого числа, стоящего в корне (от 1 до размера поддерева).

Будем добавлять по 1 ребенку, перебирая, какое текущее значение у корня. Рассмотрим 2 случая — больше мы или меньше. Помутим преф.суммы для быстрого добавления всего отрезка.

Итого какой-то куб.

Код

→ Ответить

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

Решение правильное, ищи баг

→ Ответить

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

← Rev. 3 →

~~Не подскажешь верный ответ на input?~~

Туплю, можно же чужой код использовать

→ Ответить

zeliboba

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

На самом деле это квадрат =) потому что все пары вершин ровно один рахз мерджатся

→ Ответить

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

Ага, прочитал уже ниже, спасибо

→ Ответить

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

В инпуте нам дано дерево, на каждом ребре которого записан порядок следования его концов в конечной перестановке. Будем делать динамику по поддеревьям. Пусть f(v, pos) — количество способов разместить поддерево вершины v так, чтобы она стояла на позиции pos. Научимся ее пересчитывать через детей. Для этого заведем динамику g(k, m1, m2), которая говорит, сколько способов расставить первые k детей так, чтобы среди тех, которые должны стоять перед нашей, самый правый стоял на позиции m1. Аналогично, среди тех, которые должны стоять после нашей, самый левый стоит на позиции m2. На самом деле, эту трехмерную динамику можно разбить на 2 двухмерных (для двух типов детей) и в конце посчитать ответ через них. Если переход в двухмерной динамике делать за линию, то в сумме выйдет решение за куб. На всех 20 тестах отрабатывает меньше, чем за секунду.

→ Ответить

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

← Rev. 3 →

Легче сделать так: сначала добавляем ребро к ребёнку, берём частичные суммы сначала или с конца смотря больше он или меньше, а уже потом объединяем его с поддеревом. Тогда формула получается симметричной. Если надо объединить таблицы A[pos] и B[pos] в таблицу D[pos] то формула выходит:

for (i=0;i<A.len;i++)
   for (j=0;j<B.len;j++)
       D[i+j] += A[i] * B[j] * C[i+j][i] * C[C.len-(i+j) - 1][A.len-i-1]

Первая C-шка это расстановка элементов меньших корня поддерева между собой, а вторая — больших.

Это, как нетрудно догадаться, квадрат :)

→ Ответить

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

Ну в общем-то у меня примерно так и реализовано. Только я всегда считал, что это куб.

→ Ответить

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

Каждое объединение делается за O(N₁ * N₂) где N_i это количество вершин в поддереве. Можно считать что ты объединяешь каждые две вершины в них. Объединение двух вершин происходит только один раз — в их LCA. Всего пар вершин N * N. Отсюда квадрат :)

→ Ответить

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

Я раньше слышал что в таких случаях сложность выходит квадрат, но мне казалось, что это применимо к несколько другим задачам. А сейчас попытался вспомнить, к каким именно и пришел к выводу, что наша от них ничем не отличается. Но доказательства того, что это будет квадрат я не знал, спасибо.

→ Ответить

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

Ага, а если там за O(min(N1, N2)) то вообще линия выходит. Я до недавнего времени над этим не думал. А потом дошло :)

→ Ответить

alexander.yuriev

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

если там за O(min(N1, N2)) то вообще линия выходит

А разве не n*log(n)? Например, для полного бинарного дерева.

→ Ответить

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

Сорри, я имел ввиду случай min(h1,h2), по высоте :)

→ Ответить

yarrr

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

А никто исходники не выложит сравнить результаты?

→ Ответить

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

1 2 3

→ Ответить

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

Уже даже протестили.

→ Ответить

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

А в 3, небось, подразумевалось n^2*log(n) с БПФ =)

→ Ответить

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

← Rev. 2 →

Фурье вряд ли, т.к. по модулю он не считает, там максимум Карацуба. Хотя и куб меньше чем за секунду на всех 20 тестах отработал.

→ Ответить

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

А, да. У меня 5 сек, но тем не менее)

→ Ответить

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

← Rev. 2 →

NTT (http://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform) еще как считает

→ Ответить

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

Не, ну то что по специальному модулю он считает — это я знаю. Я имел в виду, что по модулю 10⁹ + 7 Фурье не будет работать. Хотя мне интересно, может у __float128 точности хватит, чтобы посчитать в тупую, а в конце округлить и взять остатки по модулю? Даже для ограничения 100000 нужны будут числа порядка 10²³.

→ Ответить

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

проще сделать NTT по двум модулям, а потом КТО и взять по нужному модулю

→ Ответить

I_love_natalia

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

← Rev. 3 →

А почему Фурье не будет работать по модулю 10^9+7?

Upd. Факторизовал p-1, осознал.

→ Ответить

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

Не, куб, БПФ я не рискнул давать :)

→ Ответить

cerealguy

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

Но ведь большинство сдавали чистый квадрат

→ Ответить

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

У меня были решения за квадрат и за n*log(n) (с модулем 1051721729) Для второго раунда ограничение в n<=1000 показалось вполне разумным :)

→ Ответить

I_love_natalia

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

Если честно, мне кажется, что weak tests. Я не верю, что мое решение правильное :)

→ Ответить

luckyi

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

← Rev. 6 →

Такой вопрос, какой код правильнее:

 
if (p > per)
    lf = mid + 1;
else
{
    ans = mid;
    rg = mid — 1;
}

Или

 
if (per > p || fabs(p — per) < eps) {
    ans = mid;
    rg = mid - 1;
}
else
    lf = mid + 1;

Дело в том, что вторая задача с первым вариантом с одной погрешность падает, с другой все ок. С первым вариантом тоже все хорошо. Но вот можно ли всегда так обходить использование eps (просто перейти к нестрогому неравенству)?

→ Ответить

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

Правильнее делать в целых числах:)

→ Ответить

luckyi

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

ну это само собой. :)

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

→ Ответить

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

Где там бинпоиск во второй?

→ Ответить

luckyi

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

Ну можно было длину блока (по k роботов), которые будут голосовать вместе за спасение своих железок, а так же кол-во блоков одинаковой длины бинпоиском.

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

Можно было решать с другой стороны и не делить, а умножать. В конце останется N%K роботов (или K если остаток 0), все они не голосуют. Пусть на каком-то шаге есть X неголосующих роботов. Считаем сколько блоков голосующих роботов надо добавить чтобы выборы состоялись, пусть при этом роботов станет Y. Если Y > N то ответ (N - X) / K + 1 . Если нет — считаем X=Y, так как все эти роботы теперь в безопасности. При P=100 считаем Y очень большим.

→ Ответить