Доброго времени суток!
Рады приветствовать вас на очередном раунде Codeforces для участников Div. 2, в котором традиционно могут участвовать все желающие.
Задачи для вас подготовили Холкин Павел (HolkinPV), Рахов Артем (RAD) и Николай Кузнецов (NALP). Выражаем свою благодарность Михаилу Мирзаянову (MikeMirzayanov) за прекрасную систему, Марии Беловой (Delinur) за перевод условий, а также Агапову Геральду (Gerald) и Куприну Александру (Alex_KPR) за помощь.
Откроем небольшой секрет по поводу сегодняшних задач. Для их решения вам скорее всего понадобятся сортировки)
Распределение баллов по задачам стандартное: 500, 1000, 1500, 2000, 2500.
Всем участникам желаем успехов и высокого рейтинга!
UPD: Соревнование закончено. Разбор задач можно найти здесь.
UPD2: Всем большое спасибо за участие. Надеемся задачи вам понравились. Поздравляем победителей:
Отдельное поздравление участнику Touma_Kazusa, который справился со всеми задачами.
Вопрос по соревнованиям в целом: если я регистрируюсь, но не участвую в олимпиаде, то как это влияет на рейтинг? Я правильно понимаю, что приравнивается к минимальному месту, и как следствие, рейтинг падает.
Нет, не влияет.
Участвующими считаются люди, сделавшие хотя бы одну посылку во время соревнования.
А зачем давать подсказку? И тем более такую? Почти на каждом контесте особенно див2 есть задача с сортировкой.
Например, чтобы желающие могли подготовить AntiQuickSort.
Mergesort for Java
И не жалуйтесь потом :)
А что мешает вызывать сортировку для Integer, Long, Double? Там же mergesort и работает.
qsort, мне так казалось.
У массивов объектов вызывается мержсорт, у примитивных типов — qsort.
Мне кажется это тоже самое, что перед контестом писать "Задачи будут на КМП, поток (... и пр.)".
Это как раунд с счастливыми числами, так что я думаю, что это скорей не подсказка, а фишка этого раунда.
RAD больше не в команде Кодефорсес?
Нет, об этом писали уже. Если я правильно помню он едет стажироваться в лицекнигу.
Крут. Однако, мозг никак не хотел понимать лицекнигу как фейсбук
http://codeforces.com/blog/entry/4012#comment-81960
it's not a good idea to say how can we solve problems
but it's interesting :)
oh, really? is it interesting to know what is the algorithm? :D
It isn't the entire algorithm, we just know that we have to use sort in the final answer. But it's better to find oneself... It's a too big hint, and all the contestants who have seen this post will be advantaged.
Just curious to know why the site has not gone to safe mode today ...Its only 25 mins remaining and in some recent rounds the site went to safe mode some 1 hour back
Сейчас начнется обсуждение различных типов сортирвок, и их реализация :-)
многие откроют на e-maxx.ru статью "Пузырьковая Сортировка" :-)
Блин, почему нельзя сделать окончание регистрации во время начала раунда?? У меня было 18.56 когда я влетел с работы домой, и уже не успел. Это издевательство какое-то. Пересмотрели бы этот вопрос что ли
Через неделю влетишь в 19:01 и будет не менее обидно. А ещё нужно ненулевое время на распределение по комнатам.
просто перед контестом за эти пять минут идет распределение по комнатам
Как мне нравиться, что не успел что-то написать, сразу налетело миллион оленей и заминусовали. Учитывая, что в ветки мне ответили только 2 человека и пояснили почему так. за что им огромное спасибо
Большинству представителей сообщества не нравится, когда один и тот же вопрос задают 100500 раз. Многим уже надоело на него отвечать.
а если я не видел ответа на данный вопрос? или мне что-то или кто-то запрещает спросить данный вопрос, если "большинству представителей сообщества не нравится", то пуская оно идет лесом и ведут тебя более-менее адекватно.
Разумеется, не видели. Но можно подумать и погуглить ответ на вопрос. Никто вам не запрещает спрашивать, но никто не запрещает и любому из пользователей поставить вам минус.
Никто не запрещает. Общество анонимных "минусяк". Пускай соберутся в кружок и минусуются друг-друга.
Они уже собрались в это общество — codeforces.ru, ты просто привёл альтернативное название. Забей 95% пользователей школота. ссылка не работает http://lurkmore.to/95%25_населения_—_идиоты
видимо я из тех 95 процентов :) Скопипасть ссылку или в Яндексе набери, подскажет :)
Я так понял, теперь, например если сдам задачу 4 раза и она не пройдет претесты, то у меня еще вычтут 50*4 баллов? (в итоге задача не прошла)
Нет. Их вычтут только если в конце концов она пройдет.
А меняется ли рейтинг при участии в соревнованиях не своего дивизиона?
если контест только для див.2 то все из первого учатсвуют вне конкурса, а вообще если контест для обоих див-ов, то нельзя участвовать не в своем див-е
можно. только вне конкурса
нет, нельзя.
Не вводите в заблуждение
upd: а, там правка есть оказывается, пардон
Учавствует кто-нибудь из тех, кто завтра пишет VI Открытую олимпиаду школьников по программированию?)
Не участвую :-)
Методом заглушек выяснил 3 тест на задачу С.
3 2 1 1 2
Ответ: 1 1
Но моя прога тоже выдает 1 1!
Что это значит ?
мне тоже хотелось бы узнать, что с 3-м тестом такое происходит...
Вы неправильно обрабатываете последовательности, где есть повторяющиеся числа. В вашем примере (последовательность (1, 1, 2)), отсортированая последовательность пар будет такой: (1, 1), (1, 1), (1, 1), (1, 2), (1, 2), (2, 1), (2, 1), (2, 2).
Чуть поправить: (1, 1), (1, 1), (1, 1), (1, 1), (1, 2), (1, 2), (2, 1), (2, 1), (2, 2). Кол-во пар должно быть n*n все же.
4 6 1 2 2 3 ответ 2 1
любой я не умею считать, но
1,1;1,2;1,2;1,3;2,1;**2,2**;2,2;2,3
всё, понял, я не умею считать
с какой стати ответ 2 1 ? по-мойму, все-таки 2 2
1 1, 1 2, 1 2, 1 3, 2 1, 2 1, 2 2, 2 2, 2 2, 2 2, 2 3, ...
видимо, твоя программа неправильно сработает на тесте
Огромное спасибо автору за задачу С, очень хорошая задача :)
блин, я придумал в Е такую шнягу, что даже интересно, сколько бы у меня это заняло времени написать:
сделаем sqrt декомпозицию по отсортированным автобусам по левому аргументу. В каждом блоке отсортируем по правому. Сделаем в каждом блоке дерево отрезков для поиска с минимальным временем.
Все работает за O(m*sqrtn*logn)
Как делать по нормальному?
Сжатое двумерное дерево отрезков видимо. Но я не решил =)
не думаю
Ну расскажу тогда как по-моему можно решить: естественно сжимаем координаты, сортируем запросы по убыванию времени, теперь делаем так: автобус — добавляем точку (s_i, f_i) со значением, равным времени; пассажир — ищем минимум на прямоугольнике с x <= l_i, и y >= r_i. Но будет интересно взглянуть на авторское решение =)
Можно свести до одномерного дерева отрезков, а именно нужно отвечать на запрос "минимальное i, l <= i <= r такое что A[i] >= x"
не важно, там бред
а как же за временем смотреть?
действительно, там же еще время есть. неверно понял условие, прошу прощения.
видимо таки придется сет заменить на дерево отрезков по сжатому времени.
В дорешке зашло за 3сек.
Думал почему С падает на 8 претесте — k>2*10^9 (facepalm) Вот идиот...
в условии даже написано про 64-битовые числа)
Знаю знаю =)
Someone has published problems D (id DOR17) and E (id DOR16) on SPOJ during the contest. Lame way of cheating...
Someone has no respect for authors and steals your problems. This person doesn't know anything about copyrights. We try your best to do the contest. That's why we shouldn't comment this ugly behavior.
I have just received an email from SPOJ. The problems were removed and the user got banned.
I feel very stupid right know... what was the issue with pretest 3 of problem C?
4 k
1 1 1 2
Something like that
Of course... facepalm
So, what's the trick of duplicate numbers ?
If there no equal numbers it's ok and work — k/n and k%n
Let's look at
3
1 1 2
(1,1)(1,1)(1,1)(1,1)(1,2)(1,2)(2,1)(2,1)(2,2)
So k/n and k%n will print wrong answer —
k=5
Your answer = 1 1
Right answer = 1 2
P.S Sorry for my english :D
Thanks a lot. I made a fool of myself :(
Don't worry. If you look at the submissions you will see that a very large number of people made this mistake (including me). I think it's naturally to forget about the impact of duplicates initially.
the statement seems to emphasize the duplicate situation twice, but i just ignored it... 3ks for the explanation!
You're right. So many users were stuck in C. After 220th ranks in final standing, so many minus numbers are on C.
I know the trick, can you tell me the right solution?
Still right that first number is — a[k / n]. And second is a[(k–n·cnt) / num], where cnt – count of numbers in array that < than a[k / n] and num – count of numbers in array that = a[k / n].
It was written in russian editorial, i just translate it ( hope right =) )
what are the possible pairs for ur testcase?
(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,2)(1,2)(1,2)(2,1)(2,1)(2,1)(2,2)
Кто расскажет решение D и Е?
Простите меня все, кого я сломал. Все равно раунд нерейтинговый.
почему?)
Да, hos.lyric на последней минуте — это сильно.
Совесть мучила до последнего. И я таки не выдержал...
it would be so interesting if we could see our final rank now ;)
Я такой олень.. Потратил 2 попытки и кучу времени на понимание того, что такое нормально считывает только положительные числа..
long long a; scanf("%d",&a);Оно считывает любые числа, не только положительные.
У вас считывается long long, там должно быть %I64d.
Да, я знаю. Просто подумал, что всё равно число влезает в int и %d сработает...
Почему? scanf может и отрицательные считать.
Я к тому, что нельзя читать в long long со спецификатором
%d.Иначе получится такое
Ну дык ясно. потому что положительное число 42 что в 32-битной, что в 64-битной записи будет 000...00101010. А при считывании -42 то, что в int32 было бы отрицательным (32 дополнительный бит — единица), в int64 станет просто большим положительным, так как дополнительный код в 64 бите будет нулём.
Да, спасибо, буду знать!
видно претесты E были слабые — половина закидала E одной лишь сортировкой по времени автобусов. некоторые добавили бинпоиск.
А когда в претестах были максимальные тесты? :)
Ahh
its my first time for entering the contest..
its very interesting :)
u will in love with it :)
Народ, а что делает
(Div. 2)в названии контеста?UPD: я имею в виду, почему в контесте, предназначеного для второго дивизиона, совсем небольшое колличество участников первого дивизиона смогли решить все задачи?
Означает дивизион, для которого предназначен контест.
уж явно не выделяет целую часть числа от деления на двойку
Кто-то в задачи A писал динамику, и она не прошла) 1296561
блин, а я написал рюкзак. Правда он прошел
Я писал все суммы это тоже динамика и зашло.
my submittion of problem A is kinda stuck it says accepted on final test but
where is question mark on it says waiting or judging. http://codeforces.com/contest/160/submission/1296903 what's wrong with it?
it seems accept right now:)
yes it says accepted but in contest rating it says waiting or judging :(
just be patient , everything will be fine after the judging for whole contest:)
A,B,C explanations
Any idea about problem D?
I think it has something to do with Cycle Property and Cut Property. As I had never before implemented any flow/cut algorithm, I couldn't complete it in time. http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cut_property
Yeah, solutions seem to be checking for exactly that, thanks.
Div 1 now, congratulations!
The article on Wikipedia only states the sufficient conditions for being included in every MST and in no MST. How do you prove they are actually the necessary conditions?
is segment tree should be used in problem E?
It is solvable by using binary-indexed tree (Fenwick Tree).
i should learn it ... thanks for the important hint! :)
Why is the system testing stuck on 100% from the last 10 mins.I want to check my C solution ..
Maybe it will be better to make such rounds not only for div2 but for mixed div1 and div2, because I think D and E were good enough for div1.
is there failed pretest or re-submission penalty from this round ? I saw the statement about this penalty during contest, but I think I did not receive penalty at my final score.
Can anyone explain why this submission (1304142) for C timed out? It works in O(n) time, I simply rad the array, count the occurencies of numbers using HashMap and then iterate at most n times. I see no way to fail it on timelimit... The only possibly slow operation is adding elements to map, but on other tests with maximum n, it worked in around 100ms. Where's the problem?
Well, I submited the exactly same sulution again and it failed on another test, which run in 130ms before. I don't get it, where's the pitfall? Something in HashMap?
They are antiquicksort tests. Shuffle the array after reading and get AC.
Well, it passed with Integer[] instead of int[]. I think this is the most stupid thing I ever saw on programming contest. I see no point in not letting pass the solution with the correct idea and implementation... Just because of testcase challenging in fact Arrays.sort method of Java authors, not my code. What will be next, tests concentrating on possible bugs in GCC compiler? I probably should start coding in Turing machine instructions in next round.
Actually, there are a lot of cool stories of unsuccessfull hacks/TC challenges with correct output from function that returns correct value despite having no return statement inside.
We should never believe a compiler and runtime library. C'est la vie
Yes, I fully understand this, in fact, I'm glad in some way that I have learned today about a pitfall in commonly used part of standard library. But there's a difference between non-defined behaviour of C/C++ and "abusing" a weak spot by carefully chosen input. In first case, a challenger/systemtester is in disadvantage and knows his attempt can fail. If he will succeed, a code with a bug will be identified and will gain zero points. He's aware about the risk, it's a lottery. In second case, it's about choosing a very special case that timeouts in fact correct solution. A coder who got a correct idea and implemented it will gain zero points. I see a clear difference between these cases. But, however, both of them are following rules and there's no one to blame. But it's questionable if the second one is fair. But yes, there's no "guilty", just a "victim". So the victim will write slightly angry comment after the contest and life moves on :)
It makes absolutely no sense that I failed C with an O(n log n) algorithm just bcoz I coded in Java. This gives no chance at all for Java coders. All I did was to sort and proceed like every other AC algorithm.
It seems you have the same problem that I have. The strange thing is my solution once passed test 66 in 130ms and then it didn't make it in one second. Maybe some problem with system tester?
may be it was AntiQuickSort test?
What does that mean ?
as I understood from previous posts Java Arrays.sort uses quicksort, which can be hacked with special generated test which causes Arrays.sort to do O(N^2) operations.
AFAIK, Java implements using dual pivot quick sort which is faster than normal quick sort.
Any quick sort impelementation with determinate algotrithm of choosing element for partition can be failed to O(N^2) time. Java implementation too.
It seems you are right. What I did now is to push all elements in a priority queue and then pop them all and it was AC. I never thought that the built in sort would time out, never met that idea in a contest.
More easy is to shuffle data before sorting. But i don't think simeting like this will hapen often on codeforecs. It's not very sporting behavior.
Is shuffle is determined too? If so, it's possible to antiQuickSortAfterShuffleTest
You can shuffle yourself using Random, with seed got from time.
oh, sure
AFAIK Java use mergesort not quicksort for sorting.
There are many AC Java solutions. There are even Ruby AC solutions for that problem
quicksort IS NOT N LOG N. it's o(n^2)
and o(n log n) on random test
Что значит ошибка RUNTIME_ERROR на C# ? Возникла в задаче С: http://codeforces.com/contest/160/submission/1304818
Скорее всего, попытка создать массив размера 10^10.
I have a question concerning problem statement of 160D - Ребра в MST. It says:
You are given a connected weighted undirected graph without any loops and multiple edges.
But in the first sample there is a loop:
1->2->3->1Is the statement wrong or am I missing something?With loops it meant 1->1
It's true, thanks!
Можно ли решить задачу C за O(n^2)?
Очевидно нет, там же n до 100 000.
Я тоже так думаю. Значит мне просто повезло, что не было теста, когда n = 100 000 и все они равны.
72-ой тест похож на тот, у которого все 10^5 единиц
can someone tell me one reason about why problem C time constrain is 1 second !!!!!!!!!! it's just totally nonsense , the wrong Algorithm will just fail the 2 sec time !!! my solution is O(n logn) and it failed in java but Acc in C++
THANKS !
When I saw the non-standard time limit I thought that they probably put it there to prevent anybody from attempting to solve that by brute force (i.e. creating all possible pairs, sorting them and then selecting the k-th one).
However I agree that Java coders had a significant disadvantage here because of the Anti-Quicksort tests (I got lucky with Ruby I suppose). I agree that coders should think about worst-case complexity which is O(n^2) for Quicksort but if so this should affect all implementations and not just the ones in a single language.
you couldn't create all the pairs. they could be 10^10 in number!
the O(n^2) solution will fail in both memory and time, which makes the 1 sec limit completely ridiculous.
Yes, but that does not mean that the problem isn't solvable in 1 second using Java. As mentioned in previous comments you need to shuffle the data before sorting to avoid the worst-case performance of Java's sorting algorithm.
true but this not the point,the problem is having same Algorithm that passes in one language and not on the other , and this isn't right in an Algorithm competition , specially if the difference very small.
I failed the problem due to anti-quicksort test too. But I think it was a lesson well learned.
i don't think that it's our mistake !
cmon, its just a contest.
well, you are right about that :)
Вопрос: если я сдала задачу не на первой минуте, а, например, на 50-той, то по какой формуле вычисляется количество баллов за нее? (Понятно, что не 500. 490? 450?)
http://codeforces.com/blog/entry/456
Впала Д на последнем тесте:) Anti-QuickSort :)
А зачем вы на C++ написали квиксорт руками?
Ну как-то так получилось. Мне так удобней было. Вынес урок зато:)
Кстати ваш вывод можно сильно упростить, записав там просто
FOR(i,1,m) puts(ans[i].c_str());Видимо проще написать QuickSort, чем сортить массив структур... =)
Видимо, можно просто реализовать для структуры operator<
Видимо, мне стоило там написать "ВНИМАНИЕ САРКАЗМ!!!11".
This is the first time I do in codeforces environment. So I'm sorry if this is an already known issue, but in problem C, using C++, reading a long long integer from std::cin isn't really operated, while on my local machine with gcc 4.2.1 does. I was struggling against this for an hour and found that using scanf("%I64d", &longint) only solves this.
I just took a look at your submissions and realized the problem is that you declared k as int, not long long.
What a pity!The school network was broken at 23:30 and i could not finish the task...and my rating has decreased a lot. :-( TT
sorry for that :(
try to view problems and submit by your phone.
a really cool idea!
what pears do we have on this test?
1 1
and why ? all pears are ~~~~~ (1,1),(1,2),(2,1),(2,2) ~~~~~
try to read all comments before asking questions like this
there is n^2 pairs ;-) (sometimes I miss similar conditions, so I perfectly understand...)
is there anyone can tell me why i got WA on this submission? (http://codeforces.com/contest/160/submission/1299317) i tested on my computer and got a right answer. (15 lines of 'at least one')
is there anyone can tell me why i got WA on this submission? (http://codeforces.com/contest/160/submission/1299317) i tested on my computer and got a right answer. (15 lines of ‘at least one’)
Look carefully and don't be confused between your output and the answer. It must be 1 "any" + 14 "at least one".
OMG I was confused thanks!!
GDE MOJNO GRAMOTNO REKURSIYI NAU4ITS9?
Здесь 12-е и 14-е занятие.