Всем привет!
В четверг, 6 декабря в 19:30 MSK состоится Codeforces Round #153, автором которого являюсь я. Это уже третий мой раунд на Codeforces и я надеюсь, что будут еще.
Спасибо Shtrix, Seyaua и sdya за помощь в тестировании задач, а также Gerald за помощь в подготовке раунда. Отдельное спасибо Delinur за перевод условий на английский.
Надеюсь, задачи вам понравятся.
Всем удачи!
UPD: Опубликован разбор задач.
Поздравляем победителей!
Division 1:
Division 2:
All that red color suggest a hard contest :)
I guess that not hard but interesting :)
Thx for negative votes :D
You're always welcome)
It's better to not write anything :)
It looks like NiVeR is trying to reach a new low of negative comment rating and he's doing a pretty good job at it. :)
And hes not alone :d
LMAO GUYS YOU'RE SO FUNNY)))))))))))))))))
OH MY GOD IT'S THE BEST JOKE I'VE HEARD!!!!)))))
Hope so :)
So gì mà so
This was discussed a short time ago: http://codeforces.net/blog/entry/5975
AT LAST !!
Сколько лет, сколько зим!))) После последовательных Codeforces раундов, промежуток между последним и этим контестом кажется немножечко долгим:) Хорошего контеста!)))))
Отлично!Новый раунд!
Какая предполагается разболовка?
Хотелось бы, чтобы была динамическая разбаловка, но в порядке увеличения сложности.
Надеюсь этот раунд не будет слишком трудным как прошедший раунд.
I have to go to school on Dec.7 Maybe i can't do this.
T T
:| who cares ??!!
Chinese education only has exams!
One guy already said WHO CARES but i think we should repeat it. WHO CARES.
So better go to school. You can use "virtual contest" in Codeforces, but you can't use "virtual life" option.
I understand you.
omg
yeees!Can you make more contests,please?It's boring when there's nothing on codeforces...:)
Привет с UOI?
Are the scores of the problems decided? edit: Sorry, I was not asking for the scores of the problems, but if they will be static or dynamic :)
I think contest had better be arranged in Friday or Saturday，in that case more people can compete in contest.
No it wouldn't be better because we would had to wait more. Everyone is getting bored from waiting.
Let's hope the server will stable during competition
Let's pray for the welfare of the server. 42. Amen.
Seyaua, sdya are the same person ! :D ****
No. They are twins :D **** [link]
hmmm...but their pictures are same... how can it be?
I think it has been long since last competition. Thanks for all the contests and their makers, I really enjoy myself in the contests!
Good Luck Everybody!
GOOD LUCK TO EVERYONE IN TONIGHTS CONTEST.
Всем поменять цвет !
А тебе — до серого!
Мда, добрый человек. Ладно, тебе оранжевого. Может, будет как в мультфильме: "Это я раньше злой был, когда у меня велосипеда не было..."
Да, прошлый раунд был для меня первым. Не ожидал такого уровня задач. И потерял от начального рейтинга 86. Попробую еще раз, надеюсь, что-то получится. Чего и всем желаю.
Good luck everyone!! Have fun!! :D:D
если кто не в курсе, вышла IntelliJ IDEA 12. Стартует и компилирует быстрее предыдущей, CHelper вроде не глючит. До контеста еще целых 50 минут. Обновляемся, посоны!))
Только Eclipse! Только ПО, доступное на финале! Только хардкор!
ради интереса зашел посмотреть список зарегистрированных на контест див 1 и заметил: подряд зареганые два аккаунта — himemeizhi и hime . причем почта(префикс до @) второго аккаунта совпадает с ником первого. какова вероятность, что это разные люди?
Мало того, у них в 144 раунде решения одинаковые :)
У них (него) даже аватары совпадают.
И рейтинг одинаковый! По любому это связь.
Оба из Китая, Ченду )
В Китае такие совпадения никого не удивляют :)
с точки зрения правил кодфорсис это должно удивлять =)
А какие 2 остальные ?
Was I the only man who had "error 502" now?
There is one thing that I will never forget about this contest
There is one thing that I will never forget about this contest
There's only one thing Petya likes more than numbers: playing with little Masha.
Little Petya likes "a lot of things" a lot :D
Sometimes you get a mistake, the author is the same :D Sorry for my bad english :p
Contest
Опять эти проблемы с большими очередями. Очень напрягает. Сегодня мне не хватило 30 секунд залить решение по Д, а потерял на очереди я минут 5.
I solve problem B of Div.1
then lock my answer
and go hack two contestant with same Test Case
but unfortunately when i checked my hack TC too my code , I saw my solve give WA too :|
What was the challenge case for Div 1 Problem B? No one did many challenges in my room, so my solution could be wrong :( .
2 3
2 1
2 1
Answer: NO
3 3
2 3 1
3 1 2
Answer: YES
Now that someone tells me, I'm scared of testing my code on it...
My code managed to pass those tests. Do you mind sharing what test you used to hack me?
4 3
2 3 1 4
3 1 2 4
YES?
Something like
4 7
2 1 4 3
2 1 4 3
NO?
Correct answer is "NO".
1 1 1 1
Answer NO :)
I think if there was no challenges, it would be a lot of WA. This task checks contestant's attention.
Для меня контест прикольный, кроме Д (исключительно из того что не люблю эти ксоры с системами по модулю).
Но в любом случае + автору.
Very slow system testing :(
объясните пожалуйста как решать задачи D и Е(div 2)?
Д-шка вроде решалась так: заведем 2 массива: в первом перестановка Пети, во втором — перестановка Маши.
Создадим функцию check, которая принимает на вход 2 перестановки и число k, и возвращает булеан. В ней создаем перестановку (1, 2, .. n). Затем в цикле от 1 до k применяем к ней первую перестановку. Если на каком-то шаге получили вторую перестановку, то если разность текущего шага и k четна, возвращаем true, иначе false. В конце возвращаем false.
В основной программе создаем перестановку, обратную перестановке Пети. Затем запускаем функцию сначала от перестановки Пети, Маши, и числа k. Потом меняем перестановку Пети на обратную, и опять запускаем функцию. Если хоть 1 раз вернулся true, выводим YES, иначе — NO.
UPD: Может быть неправильно, систесты не прошла(
У тебя первая и вторая операция могут давать одинаковый результат.
В Е суть в том, что число T=НОК(2,3,...,k) формирует своеобразный период, так как Петя не сможет никоим образом обойти числа, которые делятся на T. Соответственно его оптимальные действия будут повторятся с этим периодом.
Поэтому достаточно рассмотреть динамикой один такой период, от 0 до Т, а также кусок, когда между текущим числом, и тем числом, которое нужно получить, не останется ни одного числа делящегося на Т (это будет или от b%T до T, либо от b%T до a%T, если b/T=a/T)
Итоговая сложность О(Т)
спасибо за объяснение. Попытаюсь сдать в дорешке
Намного детальнее, чем в предварительном разборе! Спасибо!
Are the solutions being checked manually?
Seems that they put too many test cases in Little Xor.
it's slowlyest system testing....
Sooooo slow system testing :(
The problems are harder and harder?T T need to work hard^ ^
Sorry to say but it's easier than the last contest :)
Ну вот... Зафейлил С, ибо: 1. Забыл поставить break, из-за чего решение вместо 2*N стало квадратичным. 2. Использовал int, что привело к его переполнению.
Unlike Codeforces Round #152, this contest has a very low speed system testing... :(
Может, имеет смысл ограничивать количество зарегистрированных на контест? Очень медленное тестирование на претестах ведь реально влияет на результат! Ты послал задачу, ждешь вердикта 10 минут и получаешь WA — нужно исправлять. Получается, -10 * 2 * i (где i — номер задачи) баллов за задачу, потому что в нормальном случае тестируется (и находится в очереди) задача не дольше 20-30 секунд.
Ограничивать участие? Ну вы даете..
На TopCoder так и делается. Там лимит раньше был 2200 участников, сейчас, может быть, увеличили.
А как вы предлагаете отбирать тех, кто будет контест писать? По рейтингу или кто раньше зарегался?
Контест интересный, но слишком много математики. На мой взгляд, лучше, когда задачи на разные темы.
А мне наоборот понравилось, потому что задачи идейные, а кода немного получается.
Немного??? Вы смотрели коды на B div 2?
Там есть короткое решение. Мы в начале проверяем, что есть хотя бы 2 различных числа. А потом мы перебираем все пары позиций, пытаемся поменять местами числа на них и проверяем, не отсортирован ли массив. Если нет -- выводим ответ. Если не нашли нужной пары -- выводим "-1". Можно понять, что для N > 3 ответ всегда существует (при условии, что есть 2 различных числа) и что этот алгоритм найдет его за O(N).
Я прочитал разбор... Но все-таки такие решения...
По любой задаче есть "такое" решение, дело не в задаче.
можно достаточно коротко) например:
http://codeforces.net/contest/252/submission/2711810
Everybody seems to get WA in test case 12 in Div 2 -problem B. I wonder what that test case is ?
I guess a case with n<3.
I think many people think that "-1"'s case is only on n <= 2 and all array fill whit the same number. if N = 3 and array is {2, 1, 2} we can't do any swap.
You can see this test case after the contest.
System testing has already lasted 20 minutes, but checked solutions of first 15 minutes of contest, that's amazing speed:)
why you need that too many test cases !!! :o
very slow test system(((
Seems strange, but I think Problem B was harder than Problem C. Problem C was quite standard, and non-standard problems cause much more trouble for the competitors:)
It is so bad of me that I even did not check the tricky case that I generated for Div 2 B.
Классный раунд, как и все прошлые раунды от тебя. Жалко, что решил только две задачи: всякую математику, теорию чисел и ксоры не умею делать...
Div. 2 B не должна быть Div. 2 B
Может наоборот? Div.2 B должна соответствовать Div.2 B
Да, должна, но в этом контесте не соответствовала.
Авторы контеста — вообще ребята! Четко!
Thank you for really nice problems and amazing contest :)
Here is my solution to problem B div 1: http://codeforces.net/contest/251/submission/2710934 The veredict was: "Runtime error on test 1". But I tested the same test in my computer with the same code and it worked fine. Has anyone had this problem?
For Problem B ,Div 2 , an O(n^3) solution is also passing [code]
I noticed through the test case that it is actually never going O(n^3) when all elements of the array are not the same and when n is large . But I can not understand why this happens .Can anyone explain please
The complexity of this solution is O(N).
Suppose N > 3. Then it's enough to check only 3 different pairs of distinct integers. One of them will be the solution we are looking for. The reason is that these 3 pairs lead to 3 different arrays, but there are only 2 possible sorted arrays, so one of these 3 arrays will be unsorted.
+1 to that. Thanks.
.. . How to solve Problem E. ? ... QAQ
I'll post the complete editorial in a few days. Now I can give you a hint.
Suppose there exists a node of degree 3. Let's take any such node and call it a root. Then we can reduce our problem to the following one: given a non-root node v we need to calculate the number of ways to place the sub-tree of node v on a rectangle 2xK for some K with the restriction that v is placed to the upper-left corner of this rectangle. Note that the value of K can be determined uniquely from the size of sub-tree. This problem can be solved with DP in linear time.
The reduction to the described problem is also non-trivial, but at least it's easier than the whole problem.
。。。THX alot !...
editorial in English too, I hope? Google Translate doesn't work well sometimes.
How to solve problem D div 1 ?
BFS + DFS + Bitmap + convex hull (Y)
Can anyone show me the logic in choosing 0 (numbers that divide lcm(2..k)) to be the mediate value in problem C div 1?
In case you misunderstood my words (I assume that by seeing those down votes), this is merely a question :)
Anyone can tell me how to solve C div 1 :( Just a hint, plz :D
The essential trick was that if your current integer is divisible by all numbers from 2 to k, then the only thing you can do is to decrease this integer by one. Therefore, you can use dynamic programming to count how much time you need to reduce your integer by LCM. For instance, suppose a=80, b=3, k=3. Then LCM(2,3)=6. So you count separately the time you need to get from 80 to 78, then from 78 to 72, the from 72 to 66, ..., from 12 to 6, and finally from 6 to 3. It's easy to notice that all of those in the middle are equal.
P.S. That's a shame that I didn't see this trick during the contest, but I was thinking of some DP with LCM...
Then LCM(2,3)=6
2 what ????
I don't get your question. LCM(2..k)=LCM(2,3)=6.
Sorry, I already understand your answer :D Okay :D thanks for your hint :)
Fail (( My solution in D(div2) was correct ... I just forgot to clear my array ...
Салам всем. Почему я у себя компилирую и выполняю файл с тестом 6 3 10 выводит 2. А на кодефорсес выводит 1. Может подскажете в чем ошибка?
Editorial is published in Russian here @ http://codeforces.net/blog/entry/6054
I wonder if it is possible for someone to please kindly translate that into English for me?
http://translate.google.co.jp/translate?sl=auto&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&eotf=1&u=http%3A%2F%2Fcodeforces.com%2Fblog%2Fentry%2F6054&act=url
Google Translate often does not do a sufficiently adequate job, eg. grammar and syntactical structure is not preserved.
Большое спасибо за контест! Задачи очень понравились
Отличный контест, спасибо!
Where can i see the editorial?
Are there any editorial?
only published in Russian, I'm afraid.
I'll publish the complete editorial on both languages soon. Currently I'm out of country and don't have enough time for editorial. Sorry for the delay.
I can't understand the Russian tutorial of Div.1 E. >_< I hope the English tutorial will be published soon. :)