Всем привет! Меня зовут Геральд Агапов. Я учусь в Саратовском государственном университете. Сегодня я предоставляю вам набор, надеюсь, интересных задач. Желаю всем удачи!
Хочу поблагодарить RAD, MikeMirzayanov и всю команду Codeforces за отличную систему и возможность провести раунд! (с) dolphinigle
UPD.
Раунд завершен. Всем спасибо за участие, надеюсь вам понравилось!
Top 5 Coders:
1. RAVEman
2. hos.lyric
3. tourist
4. dolphinigle
5. kelvin
Общий, уже на этот вопрос отвечали
И тут
зафиксил вершину , разбил остальные на две группы: те что идут в нее и те что из нее.
Посчитал кол-во ребер которые выходят из вершин первой группы и кол-во вершин которые в нее идут, ну и еще я знаю кол-во ребер между группами, теперь нахожу сколько ребер идут из второй группы в первую (по этим данным система выходит), а потом если оно положительное то ищу ответ за Н*Н, он гарантированно есть.
иначе возьмем цикл. если 3 его вершины подряд образуют цикл длины 3 - выводим его. иначе мы можем наш цикл уменьшить на 1 (ну там ребро так идет для этих 3х вершин).
ну и так далее пока или не найдем сразу длины 3 или пока не сожмем большой цикл до длины 3. думаю, нигде не накосячил и это пройдет.
стоп, а почему не турнир?
if(pi[v]!=-1 && pi[pi[v]]!=-1 && pi[pi[v]]==i)
то все, цикл длиной три найден. Мое решение валится на 34 тесте, не могу понять почему. http://pastebin.com/VKPbmHsW
4
0000
1001
1100
1010
Правильный ответ 2 4 3
Зашло, а как доказать, не знаю. Может это вообще неверно.
Кто-нибудь может дать претест 3 по C?
У меня какая-то тупая бага и я её не могу найти.
Не могу не отметить полёт фантазии автора задачи A:
"10^5 участников финала RCC". Это круто!
Because I am printing only two type of answers :: "2" and "1 000000001"
Задача А. Тест "10^5 2 / 1 2 10^8 / 1 2 10^8"
Этим тестом валил чужие решения.
Мое решение на таком тесте отработало секунд 20, но на финальных тестах прошло.
Скажите, это нормально?
локально решение C на жаве падает со stack overflow.
а на вкладке "запуск" генератор теста вбить не дают.
то, что его можно вшить в само решение, я догадался уже после ресабмита на плюсах и одного неудачного взлома...
кстати, чем именно обусловлена такая разница?
ключи запуска совпадают с указанными тут, java1.6.0_23, win7 x86.
почему я ее прочитал в начале второго часа?! идиот
Понравилось все, кроме задачи А. Писал ее полчаса и получившаяся фигня в конце концов упала. Наверно там есть простое решение, но оно мне как то не очевидно.
Чуток не успел дописать D. Ждем дорешивания.
Возможны такие случаи:
начальная совпадает с конечной - ответ понятен
начальная ниже конечной - считаем, когда лифт впервые будет подниматься через этаж, на который приходит участник, после того, как он уже туда пришел (удобней всего считать номер цикла "вверх-вниз"). В этом же цикле он и выйдет на нужном ему этаже.
начальная выше конечной - аналогично со вторым случаем, только надо искать номер цикла, в котором лифт будет опускаться вниз.
Мне очень не хотелось разбирать случаи.
Поэтому я написал 2 бинпоиска. Первый - для времени за которое лифт доедет до 1го этажа, второй - для времени за которое он доедет от 1го этажа до 2го. Наверно у меня кривые руки, но это получает ТЛ 19 =_=.
UPD. Как оказалось, руки не при чем, это все тормозной stl. vector -> массив дает AC =_=.
I only wished it has a larger memory limit though.
cout<< "100000 10\n";
for (int i=1; i<=100000; i++)
{
cout<< rand() % 10 + 1<<' '<< rand() % 10<<' '<< rand() % 1000000 + 90000000<<'\n';
}
прошло все тесты!((( как так? вроде же простой тест....
It were like you said some time ago. Now it's better, because if you have an issue and can't come back home, then you don't need to unregister (this happened to me)
Because the rating system is flawd sorry.
Не, мне, конечно, грех жаловаться, ведь рейтинг-то в итоге вырос, но, скажем, на полуфинале я бы такой задаче не обрадовался.
I liked problems C and D. But I fear this round might have been too hard for the division2 participants.
Thanks a lot for the round :)
Isn't it unfair that if somebody read problems and couldn't submit any solution then that round will be unrated for him.
Big thanks to the author for the contest.
Nice problems too. :)
1. Try to find any cycle. If there are no cycles prints -1.
Because of definition of tournament graph. If A[i][j] = 0 then A[j][i] = 1 (i != j).
Here's my somewhat different approach:
sorry, wrong branch
Could You explain more clearly point 3 ? If I iterate over all Inward set and for every element in Inward I check all edges to Outward I will definitely get |Inward| * |Onward|, so N^2, so the whole alogrithm will be working in N^3. I suppose point 3 should work in linear time, but I don't know how.
I totally misread this part in the contest ! :( Sorry for that.
If I understood correctly , the two para's are respectively "if" and "only if" parts for proving count[u] >= count[v] for existence of cycle , right ?
This is my opinion:
See the graph as a real tournament, every pairs of different teams plays exactly 1 match. We use an array rank[], in which teams with lower rank always win teams with higher one.
- Firstly, rank[1] = 1.
- Consider team I.
- Find the best team (smallest rank) that team I wins, call it W.
- Find the worst team (highest rank) that team I loses, call it L.
We easily observe that rank[L]+1>=rank[W].
If team W wins team L, we have a cycle I wins W, W wins L and L wins I.
Otherwise rank[I]=rank[L]+1, and rank[W→array end]+=1
It works in O(n^2).
initially rank[1] = 1 then rank[I] = rank[L] + 1 and rank[W->array end] += 1.
Are rank[] initially filled with 0's ?
If u know something about FFT(Fast Fourier Transform), it should be better to get in that. Here's my very complex solve, if u had better, plz tell me. : )
До этого я довольно много экспериментировал - сдавал одно и то же и так и эдак и был убежден, что Delphi всегда работает как минимум не медленнее, а обычно и процентов на 20-30 быстрее. Почему такая огромная разница? Лично меня это в данном случае никак не задело - в посылке на conteste был баг из-за невнимательности, но хотелось бы знать на будущее.
Конкретно - посылки 719273 и 719825.
Probably because fgets is faster than cin.
EDIT: missing word.