Всем привет!
Совсем скоро, 7 июня в 19:30 MSK состоится Codeforces Round #187, автором которого являюсь я. Это мой седьмой раунд на Codeforces и я надеюсь, что не последний.
Спасибо Геральду Агапову (Gerald), Роману Фурко(Furko) и Аксенову Виталику(Aksenov239) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Gl & hf ! :)
good luck everyone
Thanks!)
have fun everyone
Thanks!)
0
except it is "use"
it's for fun as they don't use a good one
hopefully it won't be my third consecutive unrated round :D
I hope problem statement to be short & easy to understand like your Post :D
I can't understand the guys like you... The link
lol you are right! a post's acceptance is so random!
7 июня, 7 раунд Сергея, 18**7** контест, и при том мой день рождения(1**7** лет)! Надеюсь сегодня контест будет удачный)
Более того, 187 = 1 + 8 + 7 = 16 = 1 + 6 = 7.
Happy bithday!
Thanks!)
С др, кароч. Это еще и второй подряд украинский раунд)
В контесте будет 7 задач, надо полагать.
Sereja, что ты делаешь?!...прекрати!
нееет, продолжай!
Я просто оставлю это здесь.link
Seventh and not the last... very impressive!
Sereja must be the author of the year
Hey bro, wuold you mnid cehcking yuor seplling?
Do you know what's the meaning of my nickname?
Всем Удачи и вердиктов "Претесты пройдены", а позже "Полное решение", с ПЕРВОЙ попытки!
Hope Djo vs Nadal will end before the contest
i'll try my best to reach blue!..bless everyone!..Hope everything goes smoothly
I'll try my best to stay green :D
you don't have to do anything for that
Какая разбалловка?
Ну какая разница? решай все, что можешь.
интересно..
Do you really think that the problem statements are written in English?! I can hardly interpret what's written!!!!!
LOL
Почему в D неправильно делать поворот плоскости на 45 градусов, а потом искать центры масс по X и по Y и считать ответ?
Казалось бы, причем тут центры масс? Скажем, во первый семпл добавим точку -1, 3. Центр тяжести сдвинется, а при этом в правильном ответе — те же 2 прямые
Поворот делать правильно, а при чём тут вообще центр масс?
Согласен, я упоролся...
куча точек очень близко и одна далеко. вы ставите в кучу, а надо по центру.
Тест 4 по С?
У меня, например, искало ответ для всех подпоследовательностей, а не только для неубывающих.
Да, я не умею читать
High five
А я и стресс написал, и переполнение у меня проверяется cojac'ом...
Никак не пойму, что такого в 4-ом тесте С (див 2), что почти все, кто валятся валятся на нем.
Если мне не изменяет память, то там было переполнение.
Really good and fast system test tonight!
After seeing others' submissions to div2 A, I figured out the solution immediately while still couldn't connect the solution to the obscure problem statement.
I understood the statement's intention finally.
Need some help here. Would someone explain the test case 4 for div2 A? Thanks.
4
2 3
1 772
3 870
3 668
Correct answer: 2
using bottle 1, which is (2,3) he can open bottles 3 and 4, which are both of brand 3. this is because bottle i can open any other bottle j if b[i]==a[j].
so the bottles 1 and 2 are left unopened. hence answer = 2
Thanks for the reply. I got it now.
You can use the 1-st bottle to open bottles of brand 3 (3rd and 4th). The 1st and 2nd bottles can't open. Answer:2 .
Did someone proofread the problem statements? At least I made many assumptions for solving D1-C and I can't understand D1-A at all before reading the example...
"Pay attention to the analysis of the first test case for a better understanding of the statement."
YOU DON'T SAY!!!
А в E подразумевался квадрат, или что-то более разумное?
На плюсах, то я в 2 секунды запихал, а вот то что это можно сделать на Java я не верю.
Так-то капец. Дожили. 2,5 миллиарда операций укладывается в тайм-лимит 4 секунды. :)
2.5 миллиарда бывают разные. У меня это просто проход по массиву подряд, с операциями прибавление + 2 присвоения на элемент. Все в кеше, так что понятно, что это очень быстро. Но пришлось действительно пихать. В частности делать все в одном массиве, чтобы по памяти идти подряд. В двух работало больше 10 секунд на сервере.
Быстро, codeforces радует :)
I am not able to find test case on which my code for Div 2 A was hacked. Could anybody help ??
I am also doubtful.The first line contains integer n (1 ≤ n ≤ 100) — the number of bottles. I am bit confused by this line .. How come the answer for test case
2
1 1
1 1
isn't 2 if there are 2 bottles .
same with me, but correct answer is 0.
Could you provide a link to your submission which was hacked.
Can anyone tell the intended solution for div2 D ??
you can calculate the max match between a{1...a_size} and c{i...c_size} in advance,record the match times and the c's very last match position . then do b times and count the occurrence of c . finally divide by d is the result . sorry for my bad english.
i don't exactly understand what you mean by "max match".
I think it'd be better if you give some example.
Let a = "abab" and c = "baa"
Can you explain how you operate, choosing suitable values b and d ?
let [a,b] = ["ababab",3] and [c,d] = ["baa",2] .
we preprocess NextMatchPositionOfC[1...c_size] and OccurrenceOfC[1...c_size] .
for a[1...6] = "ababab" , c[1...3] = "baa" , we can get NextMatchPositionOfC[1] = 2 && OccurrenceOfC[1] = 1 . (a' = "baab")
for a[1...6] = "ababab" , c[2...3] = "aa" , we can get NextMatchPositionOfC[2] = 3 && OccurrenceOfC[2] = 1 . (a' = "aaba")
for a[1...6] = "ababab" , c[3...3] = "a" , we can get NextMatchPositionOfC[2] = 2 && OccurrenceOfC[2] = 2 . (a' = "abaab")
then we can set a pointer ic = 1 and do loops for b times.
{ MatchTime += OccurrenceOfC[ic] , ic = NextMatchPositionOfC[ic] . }
we can get MatchTime = 1 + 1 + 2 = 4.
finally MatchTime / d = 4 / 2 = 2 is the result .
and i think this problem is just a deformation of http://poj.org/problem?id=1936 .
hope this helpful .
wow system testing and rating updates completed really fast today! :) thanks Sereja!
I read the problem statement the negligence led me Div2 A FST it. Next must not commit such a mistake!
задача B DIV2 много кто на 11 тесте превысил лимит времени,мало того что код написать,так и надо над оптимизацией думать...хотя логика верна
Как и в любой другой хорошей задаче :)
будем дальше тогда учиться,хорошая задача — это как раз необходимо для развития
Не забывайте держать нас в курсе
hope the tutorial will be published soon.
I spend much time on C's debug, but I couldn't... And my C failed because of the matter of modulo, my solution output -(1000000007-x) instead of x... So sad...
Anyway, thank you for interesting problems!
Будет ли разбор?
Admin , look at both of the submissions . They appear to be almost same .
http://mirror.codeforces.com/contest/315/submission/3841333
http://mirror.codeforces.com/contest/315/submission/3841920
I would like to clarify that I code a lot of times on windows and use Ideone for the purpose . So,its very possible that the code is manipulated not by one but a lot of people and since in this case the time remaining was very less , I forgot to make it a private. It won't happen from next time I will take care of that .
Can you also explain the following:
How did he submitted his code 7 minutes before you?
How come that, while you did not use any marco for your previous submissions, for problem C you suddenly start using marcos in a style that is very similar to the coding style of aman181993's? From the submission history one can see that aman181993 started using F(i,a,n), FD(i,a,n) all the way back from May 19.
Why this solution has been skipped?? http://mirror.codeforces.com/contest/315/submission/3837849
Please, retest it again :'(
Problem D was the best in div2
разве это решение нельзя сломать на ТЛ http://mirror.codeforces.com/contest/315/submission/3840568
Мне кажется, что можно.
It seems that both AC solution of Div 1 — E is O(n^2). It should not have been the expected solution.
It is expected solution. Its O(N^2), but to solve this task you should make many optimization that makes O(N^2) --> O(N^2 / big const, near 32).
When writing English version of announcement, please link to codeforces.com for the tutorial -- codeforces.ru automatically changes language to Russian, which is somewhat annoying. But anyway, good round!
Раунд был достатычно интересным. Спасибо!
Can anybody tell me how to solve the pro.E of div1
Where can I find a discussion forum for this topic? I wanted to see the solutions for this Codeforces Division Match. :)
My submission for div1 — D ( 4401712 ) passed lots of test case where it should not:
ok found '85784037.0000000', expected '85784036.5000000', error '0.0000000'
The relative error here is less than 1e-6.
The correct relative error is 0.5. My program always output an integer where it should not.
Edit: Seems like I had some confusion between relative & absolute error. But using relative error in this problem doesn't make sense to me. The answer is always N or N+0.5 (where N = integer). Allowing relative error < 1e-6 may allow incorrect submission to pass. E.g. If I used different algorithm for small N, my wrong solution would have passed.