Мы рады приветствовать всех участников отборочного этапа “Яндекc.Алгоритм 2011 - Раунд 1”.
Авторами сегодняшнего тура являются сразу несколько человек, а именно: Виталий Гольдштейн, Игнат Колесниченко, Станислав Пак и Денис Ярец. Все мы являемся сотрудниками или интернами компании Яндекс. Мы очень признательны Артему Рахову, Марии Беловой и Михаилу Мирзаянову за оказание помощи в подготовке задач. Надеемся, наши задачи окажутся интересными и понравятся вам.
Как вы наверное уже знаете, по результатам сегодняшнего отборочного раунда определятся 200 участников, которые продолжат борьбу за право участвовать в финале чемпионата.
Обратите внимание, что как и во время предыдущих квалификационных раундов, функциональность Codeforces на время соревнования будет немного урезана. Не беспокойтесь, все вернется на место после окончания раунда.
Раунд будет учитываться в рейтинге как для официальных участников отборочного этапа, так и для тех, кто не прошел квалификацию и участвует вне конкурса.
Желаем всем удачи и высокого рейтинга!
Контест завершен. Всем спасибо за участие! Особые поздравления победителю раунда tourist-у и 200-ке лидеров, вышедшей в следующий тур. Ждем вас на заключительном отборочном раунде послезавтра.
UPD Понял...жаль, что на контесте не дошло
Any ideas why?
Here's the code: http://pastebin.com/79PFDzrG
Too bad, that would've been the difference between qualifying and not qualifying :/
What I did was a dp[position][didMistake] for each number.
если действительно за O(N) то как именно?
Зачем вообще очереди? :)
Просто вычисляем время окончания обслуживания j-го человека на i-ом шаге di, j, как время начала обслуживания плюс ti.
А время начала - это максимум из времени окончания обслуживания j-го человека на i - 1-ом шаге (di - 1, j) и времени окончания обслуживания j - ki-го человека на i-ом шаге (di, j - ki), если такой человек существует.
Ну и d0, j - просто время прихода.
Извините за неграмотность.
2) Заметим, что люди будут вставать в очередь следующим образом: пусть есть три кассы и 8 людей. Тогда для первой кассы 1,4,7; для второй 2,5,8; для третьей 3,6
3) Понятно, что худшее время будет для последнегоЛибо заметить, что можно обработать окошки независимо и каждому следующему подавать на вход времена, в которые люди вышли из предыдущего. Это линия
Тогда не знаю. Посмотрите тест, он же есть в дорешивании.
Будем поддерживать счетчик количества доступных касс. Теперь идем по всем чувакам. Если есть свободная касса, то сажаем этого чувака туда и пересчитываем ему время выхода. Если сажать некуда - вытаскиваем из касс чувака с наименьшим номером (иногда надо подождать до его времени выхода) и сажаем в освободившуюся.
Можно доказать, что времена выхода чуваков тоже будут идти в порядке возрастания, как и приходы (т.к. все одно и то же время обслуживаются). Итого ничего не надо сортировать. Решение за O(n).
5 15
3 7
Вроде бинарное дерево поиска.
Разве нет?
больше не наливатьдать выспаться/ \
1 5
/ \
3 4
как то так.
корень не обязан быть с номером 1:)
UPD. немного подредактировал мой ascii-арт...
Гарантируется ли что сложность A<B<C<D<E ?
Почти всегда можно ее вместо дерева загнать --- и тут можно было, 250мс на макс тесте
sum находится линейно, а add и del за логарифм. Учитывая ограничения, мне показалось не логичным описать сложную структур =)
Вы правы, мне подсказали, что insert в vector работает за O(N). Так что чистый квадрат)Наверное, это тоже не слишком хороший показатель, так как многие читают задачи исключительно по порядку, и решают их тоже по порядку. Плюс ещё психологический фактор в духе "да ну, это же Е, наверняка там что-то очень замысловатое". Уверен, что если бы поменять местами D и Е, то разница была бы совсем другой, но это никак не проверить, конечно =)
где ребро между парой вершин есть если их расстояние > ответа. Тогда все пары которые соединены ребром должны относиться к разным генералам т.е. - быть разных цветов. Такая раскраска возможна только, когда граф двудолен. Будем добавлять ребра от самых длинных к более коротким (их можно отсортить сортировкой подсчетом) и смотреть нарушилась ли двудольность или нет. Как тока нарушилась, то мы нашли ответ. А второй параметр ответа это просто 2^(число компонент связности)
Я считал две функции - количество детей в поддереве (пересчитывается очевидно), и для каждого остатка по модулю пять сумму ключей в таких позициях.
Пересчитывать тоже очевидно: перебрали остаток в ребёнке, посмотрели, сколько слева (либо 0, если левый ребёнок, либо 1 + sz[right], если правый) и прибавили туда.
I think C and D are much more interesting to discuss.
In D I used N*Sqrt(N) algorithm which looked obvious to me. The most popular approach was cartesian tree. Some others used Interval trees.
I think C was harder than D. I looked at some passed codes and they look like O(N^2), but I am not sure.
Still, D allowed much more different solutions and therefore, it was easier than C in my opinion.
Но я к тому, что места для взломов должны возникать из-за алгоритмической сложности задачи или из-за интересных, нетривиальных тестов... а не тупо из неестественных ограничений!
Думаю +10-15 хаков к каждой задаче не убьют систему.
Вон --- и по D у человека прошел квадрат.
А в прошлый раз я словил бревно пытаясь хакнуть человека с 10^9 за линию.
КО: достаточно одно дерево, просто в качестве груза хранить 5 сумм :)
Я обычно пишу один класс/шаблон, а потом создаю, сколько хочу.
#include <iostream>#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#define long long long
#ifdef DEBUG
#define WATCH(x) (cerr << #x << '=' << (x) << endl)
#define TRACE(x) (cerr << (x) << endl)
#else
#define WATCH(x) /*()*/
#define TRACE(x) /*()*/
#endif
vector<int> v;
int n;
int main() {
cin >> n;
v.reserve(n);
for(int i = 0; i < n; ++i) {
string s; cin >> s;
if (s == "sum") {
int l = v.size();
long sum = 0;
for(int i = 2; i < l; i += 5) {
sum += v[i];
}
cout << sum << endl;
} else {
int x; cin >> x;
if (s == "add") {
v.insert(lower_bound(v.begin(), v.end(), x), x);
} else { // s == "del"
v.erase(lower_bound(v.begin(), v.end(), x));
}
}
}
}
EDIT: Hehe!! Of course I'm wrong!! Sorry :D
This kind of problems should generate data with defferent monotonicity to beat various brute force approaches.
E was quite actually nice problem. Nice concept. Thanks for the round.