SNSS 2012, Round 1 - Codeforces

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

← Rev. 2 →

Не приходил mail, в спаме тоже нет. Переотправьте плз...

→ Ответить

Rubanenko

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

+13

Извините, а у Вас с задачей С все нормально?

→ Ответить

Prestige

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

Я вошел в систему, но растерялся. Здесь и счетчик в котором 20 мин осталось и написано не начался и везде написано виртуальный контест и длительность 80 мин. А на календаре аропана написано что длительность еще 7 дней. Что происходит? Подскажите!

→ Ответить

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

Такие правила проведение — ты можешь в любой момент начать решать до окончания раунда, но решать будешь только 80 минут.

→ Ответить

Prestige

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

-16

а что значит вот это:"00:33:36 / НЕ НАЧАЛСЯ" в зеленой полосочке?

→ Ответить

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

Текущее время, я полагаю.

→ Ответить

Fefer_Ivan

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

← Rev. 2 →

+87

Правила не читай
@
Контест начинай

→ Ответить

Jokser

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

А куда пропал таймер у людей, которые в данный момент пишут раунд, на страничке Standings?

→ Ответить

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

← Rev. 2 →

Было бы неплохо открыть дорешку или какой-нибудь еще контест, чтобы можно было проверить, что твой шаблон нормально компилируется и запускается на сервере. У меня внезапно возникли RE 1 на Java, причем решения с таким же шаблоном нормально заходят в дорешку Opencup. Видимо, из-за политики безопасности какие-то функции нельзя вызывать.

→ Ответить

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

Дорешивание есть в этом же контесте, сразу после окончания.

→ Ответить

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

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

→ Ответить

knightL

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

А для чего там находится задача X? разве не для того,чтобы посылать туда ерунду и смотреть, как она работает?

→ Ответить

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

но обратно же, до начала соревнования не потестишь...

→ Ответить

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

Я выяснил, что происходит. На Java 6 нельзя создавать новый Thread — падает с Runtime Error. На Java 7 все работает.

Кому интересно, вот код, который работает на Java 7 и вызывает Runtime Error на Java 6.

→ Ответить

OSt

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

Надеюсь, что фраза "в одной задаче слабые тесты" подпадает под пункт правил "обсуждение неточностей или ошибок" не ведёт к дисквалификации". Если нет — поправьте.

→ Ответить

Rubanenko

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

Ты о чем?

→ Ответить

OSt

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

← Rev. 2 →

-9

О том, что по одной задаче заходит аж 2 неверных алгоритма, которые на нормальных тестах дают TL с приличным запасом. Не будем это обсуждать до конца раунда. Тесты я уже отправил судьям. Может это только я такой глупый :-)

UPD: Хм... Раунд закончился, а ответа от судей или падения хотя бы своих решений я так и не увидел...

→ Ответить

Egor

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

Раунд еще не закончился
Есть правило, что на АСМ контестах ОК не пересуживается

→ Ответить

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

← Rev. 2 →

Добавление тестов после того, как хотя бы один участник сдал задачу, противоречит правилам. Вне зависимости от того, будет пересужен соответствующий OK или нет (участники оказываются в неравных условиях).

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

→ Ответить

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

Думаю это все же лучше во время соревнования донести до судей, а уже после окончания — общественности...

→ Ответить

de_troit

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

Раунд закончился. Как решать B ?

→ Ответить

riadwaw

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

+10

Я построил Карася на 1 строке. переходы из конечного состояния в него же.

Суем в корень 1, далее N раз из каждоый вершины переносим и 0, и 1.

→ Ответить

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

Карась легко строится при помощи КМП функции...

→ Ответить

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

← Rev. 2 →

Динамика f_i_j_t — количество слов длины i, максимальная длина префикса, который равен суффиксу ключа у этих слов равна j, и t false|true — содержат ли слова ключ как подстроку.

Рекомендуемое знание алгоритмов КМП, Ахо-Карасик.

→ Ответить

gen

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

+14

Ещё одна динамика: f_n — количество слов длины n, в которых ключ встречается только в конце, но не раньше. Если длина ключа m, то тогда f_n равняется 2^n - m (общее количество строк длины n, которые оканчиваются на ключ) минус количество строк длины n, которые содержат ключ так же и раньше. А это:

f_k * 2^{n - k - m}, если k + m ≤ n (то есть, если первое вхождение ключа не перекрывается с последним);
f_k, если первое вхождение ключа перекрывается с последним (т.е., если суффикс равен префиксу ключа длины перекрытия).

Ну а потом ответ считается как сумма всех d_i·2^l - i, т.к. справа всё равно, какие биты стоят (l это нужная в задаче длина).

→ Ответить

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

красивое решение, а то с этими состояниями было не было как-то не приятно... спасибо

→ Ответить

Lepetrandr

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

← Rev. 2 →

+13

Только что отрешал. Кто-нибудь может подсказать что требовалось в D ? Я выводил ((n^k)-1)mod m, WA5

→ Ответить

riadwaw

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

(n^k-1)/(n-1) = 1 + n + n^2 + n^(k-1)

Заметим, что

1 + n^(2k-1) = (n^k+1)(1 + ... + n ^(k-1))

Рекурсивно считаем как возведение в степень. Итого log^2

→ Ответить

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

Ну или матричку ((1,n),(0,n)) можно возвести

→ Ответить

riadwaw

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

О, действительно, спасибо:)

→ Ответить

SkyHawk

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

← Rev. 5 →

Не совсем понятно, что и как рекурсивно считаем? Нам же надо посчитать (N^k - 1) / (N - 1) mod M. Я так понимаю, что можно посчитать N^k-1 mod M*(N-1) и поделить на N-1, но вычисления не помещаются в long long =(

→ Ответить

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

← Rev. 3 →

1 + n + n² + ... + n^k - 1

Если k четное, то эта штука равна (1 + n + ... + n^{k / 2 - 1})(1 + n^k / 2)

Если k нечетное, то посчитаем 1 + n + n² + ... + n^k - 2 и прибавим n^k - 1

→ Ответить

SkyHawk

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

Ух ты, оно таки считается быстро. Понял, спасибо.

→ Ответить

I_love_natalia

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

← Rev. 2 →

+11

Второе проще ans(n,k) = 1 + n * ans(n, k-1)

→ Ответить

Gassa

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

Имелся в виду другой подход. Воспользуемся представлением

$\text{[math]}$

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

→ Ответить

mmaxio

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

Можно и за log, если из 1 + ... + n^2k - 1 выносить 1 + n.

→ Ответить

Fcdkbear

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

Еще можно узнать все степени, которые нам понадобятся, за логарифм сумарно их все посчитать, а потом использовать. Выйдет решение за логарифм.

→ Ответить

al13n

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

+12

Или можно воспользоваться тем, что если a делится на b, то (a / b) % m = (a % (b * m)) / b, где в правой части деление не по модулю, а обычное, причем остатка не будет.

→ Ответить

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

+14

Ты забыл поделить на N - 1, у меня такая же ошибка. Прочитай внимательно условие ;)

→ Ответить

Lepetrandr

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

+14

Судя по монитору нас таких много ) в общем больше не буду сдавать в слепую, толку мне от этого маловато.

→ Ответить

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

Да, не мало, и тесты хорошо подобраны)... Толку не много, но просто надо вбить в себя правило "внимательно читать и писать"

→ Ответить

Gassa

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

Присоединяюсь к клубу.

И ведь искал в условии, сколько сотрудников. Но мысль, что в первых двух предложениях текста может быть часть условия, меня почему-то не посетила. В итоге остановился на понимании «в книге учёта будет одна запись на всех сотрудников». Что, конечно, противоречит условию («... для каждого из сотрудников компании»).

→ Ответить

Ссылка на задачи 1-го тура открывает задачи другого контеста

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

← Rev. 2 →

-20

Блин, я в задаче D забыл, что ограничения до 10⁹, и отправил for от 0 до k-1... Epic Fail.

→ Ответить

de_troit

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

→ Ответить

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

Не так ссылка, вот

→ Ответить

de_troit

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

А что с той ?

→ Ответить

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

я не знать

→ Ответить

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

fixed (почему-то скопировались задачи с SNWS12R1).

→ Ответить

OutSide

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

Как решается F? Динамика за O(сумма всех A[i]) для каждого теста дает тайм

→ Ответить

shevchen

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

← Rev. 2 →

+21

Пройти направо, обеспечивая h[i + 1] ≤ h[i] + 1; пройти налево, обеспечивая h[i - 1] ≤ h[i] + 1. Каждый раз уменьшаем высоту на как можно меньшее число. Легко доказать, что в результате двух проходов получится нужный результат, а в процессе мы не убирали лишних коробок.

→ Ответить

vlad107

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

Можно поподробнее, почему это верно?

→ Ответить

shevchen

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

← Rev. 2 →

Заметим, что мы никогда не убираем лишнего: если мы снимаем коробки сверху с i башни, значит, h[i] = h[i ± 1] + 1. Высота соседа со временем не увеличится, а значит, текущее значение h[i] также не меньше максимально возможного ответа. По индукции, мы никогда не теряем оптимальности.

После первого прохода нам известно, что h[i - 1] ≥ h[i] - 1. Во время второго прохода h[i] может только уменьшиться, неравенство сохранится до момента обработки h[i - 1]. Далее возможны два случая:

1) h[i] - 1 ≤ h[i - 1] ≤ h[i] + 1. Высоту h[i - 1] менять не будем.

2) h[i - 1] > h[i] + 1. Тогда новая h[i - 1] = h[i] + 1 > h[i] - 1.

Значит, неравенство h[i - 1] ≥ h[i] - 1 сохранится. В свою очередь, во время второго прохода установится и h[i - 1] ≤ h[i] + 1. Получили то, что нужно.

→ Ответить

Fcdkbear

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

Сдал динамику по позиции и высоте последнего зафиксированного ящика, зашло без проблем. Сложность, похоже, такая как у тебя.

→ Ответить

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

+11

Я в приоритетную очередь кидал столбики из ящиков и каждый раз вытаскивал самый маленький и забирал лишнее ящики у соседей

→ Ответить

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

← Rev. 2 →

Ох ты ж блин, с set-ом TL, с priority_queue OK! Авторам незачет, NlogN тут явно надо было отсекать.

→ Ответить

gen

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

То же самое и с A.

→ Ответить

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

Кстати, на Java руками-написанная-куча заходит. PriorityQueue, конечно же, TL-ит.

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

→ Ответить

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

Странно, у меня на Java PriorityQueue с использованием объектов заходит.

→ Ответить

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

← Rev. 2 →

Кстати, это решение легко переделывается в линейное используя вместо приоритетной очереди n списков и сразу отсекая кучи у которых больше n ящиков

→ Ответить

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

← Rev. 2 →

У меня немного укуренное решение. Посортим массив подсчетом, будем хранить в ids[x] номера элементов, значение которых равно x. Теперь бежим по этим элементам, начиная с меньших значений. Когда мы рассматриваем элемент с номером i, равный x, надо элементы с номерами i-1 и i+1, если они были больше, уменьшить до величины x+1 и засунуть в ids[x+1]. Получается, что элементы могут находиться в нескольких ids-ах, поэтому надо проверять их корректность условием вида if (a[i] == x), это чем-то похоже на пропуск некорректных элементов в Дейкстре с priority_queue.

Это решение, однако, явно использует, что a[i] <= 100, если бы этого ограничения не было, то же самое приходилось бы делать set<pair<int,int>>-ом за NlogN, что у меня поначалу не зашло. Так что оно нехорошее:)

P.S. priority_queue таки заходит, см. коммент выше. Пичалька.

→ Ответить

SkyHawk

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

Я делал так: идём слева направо, уменьшая по надобности высоты блоков. Если пришлось уменьшить высоту из-за того, что блок справа слишком низкий, то возвращаемся к предыдущему блоку и продолжаем процесс. Опирался на тот факт, что высота каждого столбика не больше 100, на каждом шаге назад мы уменьшали высоту какого-то блока, а 10^7 — это не очень много =) Да и вообще, мы не сможем сделать более 100 шагов назад подряд, так что прошло без проблем.

→ Ответить

AlexanderBolshakov

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

Краткий разбор Е:

Как известно, кратчайшие пути из конкретной вершины в графе без отрицательных циклов образуют ориентированный ациклический граф. Нам нужно найти наиболее удаленную от офиса вершину, такую, чтобы из нее были достижимы дома обоих программистов. Решение: Дейкстра (построение графа кратчайших путей из офиса) + ДФС из домов обоих программистов по обратным ребрам графа, построенного на предыдущем шаге (определение достижимости).

→ Ответить

knightL

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

+15

Можно просто запустить три дейкстры: из офиса и из каждого дома. Потом переберем все вершины v. Эта вершина может быть в пути, если растояние от офиса до v + v до i-того дома = расстоянию от офиса до i-того дома. Ответом будет минимум расстояний от офиса до вершины v по всем вершинам, которе могут быть на пути.

→ Ответить

knightL

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

А задача C должна решаться обычным перебором или там что-то хитрее должно быть?

→ Ответить