Всем привет!
Это 150й (юбилейный?) раунд на Codeforces. Для 1го и 2го дивизионов.
Раунд готовили: Ripatti , Gerald , Delinur .
Enjoy!
UPD. Разбалловка стандартная: 500-1000-1500-2000-2500 для обоих дивизионов.
UPD2. Контест окончен. Читеры удалены. Рейтинги пересчитаны.
Победители в дивизионе 1:
1. scottai1
2. vepifanov
3. rng_58
4. Egor
5. Komaki
Победители дивизиона 2:
1. mochavic
2. hanamaki
3. mfv
4. shef_2318
5. TangJie
Всем спасибо за участие. Приходите еще.
Разбор задач будет завтра.
UPD3. Разбор
юбилейный говоришь, 150 футболок будет?
футболки не предусмотрены
ОЙ КАК Я ЗОЛ!!!!11 ПОСТАВЛЮ МИНУС!!!!11
ОПАСЕН!
I hope problems will be as good as contest number :)
What a short post! Great!!
haha :D
What the 157 symbols!
So being shorter means being great?
Take it easy please. I just said that it was not like the others. :)
Why is 150 a good number?
There's no accounting for taste.
But probably beause we still think of numbers decimally.
ill hope it will be good contest like last
Краткость — сестра таланта. =)
P.S. А разбалловка будет стандартная или динамическая?
Скорее всего — стандартная.
I wanna pass a vector as a reference to a function. can anybody help me??? template code or helping links pls.
cplusplus.com
thanks
Will the problems be sorted by order of difficulty? What is the scoring system gonna be??
I think not,as usually it is.
..... contest number is good, lets try to make our rating good :)
all you guys be cool like me !!
My contribution is positive. What did I do? o.O
Good luck & have fun !
Amazing anniversary :-ss I have never a problems like Div 1.A Amazing or bitwise
Seriously, why? Not enough servers? 'Shut down all the servers' button was clicked by an accident? Slow code? Strange Java behavior? 'The load was so high that we were not ready for it?'
It looks very strange and unnaturaly for me; CF rounds are not beta for a long time and there are still problems sometimes.
sorry to say that but if the server isn't strong enough just limit a registration number : )
mnlfrnnds04 had made many hacks and only one person has been hacked! Guys, how do you like this?
I think it's another user of himself or it's his friend because both users are from Turkey and have the same picture.
mnlfrnnds04 has 24 hacks so far, all of them on the same person. With 1 correct task he is third. Seems legit...
He is very lucky that stay in chicky room, and he got crazy number of successful hacking attempt. Congratulation! =]]
look at their profiles. same photos, same countries, a little bit alike nicknames. that's obvious...
What is his room ??? anyone in his room please tell my some information abou this case please :D
obvious cheater is obvious :d
Yes. now they are 26. The both users are have equal avatar. "Nothing suspicious" :D. And the oth users are from Turkey. Again "Nothing suspicious" :d
In his profile It says he/she is from portugal ? Or maybe I am commiting a mistake ?
+28, hell yeah, How can he do that =)) Please teach me :D
that's better to avoid doing like that:)
Just kidding :D And what admin do next after this ????
+44
mnlfrnnds04 has 44 hack in his room :D and in my room overall was not 44 man
watch
How can we cheat for hacks? I don't get it... The roomates are determined randomly...
it's just luck
Maybe he has tried to do this a couple times and today he got "lucky".
I think he just wrote a solution that passes pretests only, then write some test cases that beat it.
After that, he modify the hacked solution to beat down the hack only and then invent another hack to beat down the solution again
You are GENIUS!!
Had found the same theory a little after my question, and I think you're right. But it will be detected very quickly if it is something like "if(input==hack1) then print(solutionhack1) else if (input==hack2) then print(solutionhack2) etc..." Or else, it can be too a good solution, but altered for permit hack like "if(input==hack1||input==hack2...) then print(42) else print(goodanswer)"
http://codeforces.com/submissions/hgrsm07 :D
The photo is same...
http://codeforces.com/profile/mnlfrnnds04 http://codeforces.com/profile/hgrsm07
I can't be possible...
people who are trying to explain this event, YOU'RE ALL GENIUS!
He would be first even if his A and B won't pass system tests.
А вернут 50 баллов за неверную отправку по задаче A div. 2, когда условия были некорректны?
what kind of sorcery is this :) 44 hacks, same user, same country, same profile :)
Same solutions…
None other than a great coincidence. It's always happens.
PRETEST 4 WAS A TRICKY ONE FOR THE PROBLEM HYDRA............... ALMOST EVERYONE HAS A WRONG ON IT........
NO
Could anyone explain me, what is the statement of the problem B? Let's assume two middle vertexes as S and T. I can't understand, could neighbours of vertex S be connected to vertex T. I thought, no. And, server problems...((
tree with h+t+2 nodes
I think no except you don't select the neighbour nodes for both S and T
Will this compitition be rated?The Net was error for too much time.
But they increased the time to overcome that .. So I suppose it is alright
I'm disagree.
Imagine the following situation (it's from real contest): I opened one problem, solved it and then server gone away. I have to wait and can neither send my solution (and I lose some points), nor read the next problem (here I lose contest's time).
Then imagine one (I know such persons too) who opens all problems in the beginning of contest. So, he have 5 additional minutes over me. Not fair, huh?
You also had the opportunity to open all 5 problems. So it is fair to everyone.
Well, I think it is reasonable precaution to open all tasks when contest starts
Unfortunately, yes. I've said enough about it
My situation was better: I waited for five minutes to send problem, and than waited 5 more without any other opened problem. Than I got WA. Nice:)
I'm just the first situation,and I solve the second problem but I can't submit at once,when I submit it,it's already 20 minutes later.
Imagine if you want to ask a clarification (my case). Let's hope this doesn't keep happening in future rounds.
Как понять эти 44 взлома mnlfrnnds04???
понять, простить...
Простить легко, понять невозможно!
Мне кажется немного странным, что он 44 раза взломал одного и того же человека. ^_^)
Только мне кажется странным, что он взломал 44 раза одного и того же человека, у которого , более того, совпадает с ним аватарка
http://codeforces.com/profile/mnlfrnnds04
http://codeforces.com/profile/hgrsm07
Ок, в следующий раз, если ты взломаешь меня, я поставлю твою аватарку и тебя забанят!!! зловещий смех
Странным? Это чуть более, чем очевидно. А про него уже сообщений 30 написали точно.
Абсолютно очевидно, что писать такое кол-во раз неправильное решение, которое проходит все претесты и взломы, невозможно, если каждый раз не добавлять 1-2 случая (собственно, взломы), для чего необходимо знать эти взломы.
Ага, а ещё более странно, что у них с этим человеком идентичные решения задач.
Его программа -- правильное решение + неправильный вывод на определенном тесте! Капитан очевидность как бы намекает...
mnlfrnnds04 this person should be banned, he is first in div-2 illegally.
of course with this one too hgrsm07 :D
then I will survive unluckiness of 13 in standing :p
Edit: as a result of omitting the cheater person, now I am ranked 12th, and consequently no person is ranked 13th! результаты
And I'm 14th :) (Isn't it 13rd?)
Of course, it's not fair with the other contestants.
MDantas it looks that your solutions are identical to the Manoel's. And also very similar to the rafaelclp's.
4 solutions very similar from 3 guys doesn't seems coincidence.
See for example: 2572280 from SusanBoyle and 2572712 from Manoel.
Not fair, indeed.
автором предполагалось такое классное решение, удивительно, что пробежка по сету заходит?
Сервера codeforces настолько мощные, что...
Размер сета не более 20. У меня такое же.
хм, на первый взгляд кажется подозрительно неверным
При росте числа биты строго увеличиваются. Значит не более 20 различных? Что из этого подозрительно?
И никто задачи не обсуждает :( Мне понравились A и B, хотя по-моему они одинаковой сложности. А вот задачу типа C я уже где-то видел, поэтому она мне не очень понравилась, вот.
В B у меня зашла проверка каждого ребра и хеш-таблица для соседних. По-моему она легче, чем А. Как ее решать?
Как решать C-div2/A-div1?
congratulations mnlfrnnds04!! The successful of a lot of challenges is the very great achievement!!!
...Oops...? Something seems to be wrong... (o_O)
he's a damn cheater
Of course, he is just a cheater.
The expected score for this match was 2158. :D
std::set — зло! Товарищи фиолетовые, я снова с вами!
in Problem E, In pretest, My program prints "NO" in test case 1, but my program prints right answer in custom test. Please check my program..
-------------------------------- Sorry, my program was wrong.
I got this verdict in problem D(case 21) — "wrong output format Unexpected end of file — int32 expected". Does this mean I'm giving too much out-put? Submission link
No, it means exactly the reverse — you gave checker not enough output — it tries to read int32, but gets EOF.
It mean that you miss one (or more) integer
UPD: I was too late(
can tell how made problem B???
Note that there are not a lot of undoubtly lucky number upto 10^9 . So generate all of them
I did a backtracking solution. You try all the pairs of (x,y), after that you produce all the possible numbers with a backtracking. This gives approximately O( 10^2*(2^10-2) ).
Div1 for first time .. so happy :D
Me too man!
Доказательство хорошей сложности алгоритма в B, который перебирает рёбра, и находит пересечение множеств соседей двух вершин.
Допустим, что юзаем хэш-таблицы с операцией за O(1), а при нахождении пересечения ищем элементы меньшего множества в таблице большего множества. Доказываем, что работает за
, аналогично доказательству алгоритма, который считает треугольники в графе (насколько помню, KADR рассказывал в Петрозаводске). Пусть вершина тяжёлая, если у неё больше 
соседей.
Это круто, только в конкретной задаче доказательство гораздо проще есть. При добавлении условия, что у одной вершины рассматриваемого ребра >= h ребер, а у другой >= t, все получается хорошо. Если условие не выполняется мы не рассматриваем ребро, иначе делаем так. Если количество ребер от двух вершин > 2 * (h + t), очевидно, что решение найдется (и "тяжелую" проверку сделаем только один раз). Если же ребер меньше, то сложность алгоритма O (m * (h + t)).
P. S. помню я сколько потребовалось нам попыток, чтобы в Петрозаводске загнать O(m * sqrt(m))... Это плохая сложность (например, со стандартной Java хеш-таблицей она не заходила).
Там был какой-то хак, что никаких таблиц не надо было использовать. Мы потом в дорешке сдали...
Ну понятно — храним массив, в котором для каждой вершины помечаем последнюю из рассматриваемых вершин, с которой у нее есть ребро. Тогда действительно получаются все операции за О(1).
Can anyone tell me why this brute force solution is able to pass Problem A (Div 1)? Solution I am not able to prove its worst case complexity. Perhaps, it is because of the pigeonhole principle. Is it possible that the tests were weak?
Your code is correct and runs in O(N*20) for the worst case. When inner loop breaks with (temp==cur[j]) condition, it means that, a[j] and a[i] has some bit b set in their binary representation, but none of the a[j+1],....,a[i-1] has this bit set. If we contribute (i-j) to b(or to one of the bits which has above property), we see that for each 0<=bit<=20 we will do at most O(N) operations.Therefore complexity is O(N*20).
Was getting a TLE on Test 47 for problem B, and after the contest changing the loop from 0 -> N — 1 to N — 1 -> 0 reduced the time from hitting the TL on 2000ms to 281ms!
I still can't see any sense in making the TL that strict on the problem.
Объясните условие B, пожалуйста. Лишние ребра мешают? Могут ли центральные вершины быть соединены не со своими листами? Последнее не видно из семплов :(
Разобрался. Как и думал, на контесте написал не ту задачу. Пожалуйста, делайте условия понятнее. Я уже раз третий за месяц не могу понять условие во время контеста.
P.s. Позиция "сам дурак" конечно восхитительна, но все же прошу поддержки.)
Как решать C, D, E?
C: будем рассматривать не все координаты подряд, а только интересные. Координата интересная, если чувак останавливался прямо в ней, или в соседней. (Например если чувак двигался из (0, 0) в (10, 0), а затем в (10, 5), то интересные Х координаты будут -1, 0, 1, 9, 10, 11, интересные Y координаты -1, 0, 1, 4, 5, 6). Промасштабируем поле, теперь одна клетка нового поля — какой то прямоугольник на старом поле, причем этот прямоугольник окажется либо целиком заражён, либо нет. Размеры нового поля теперь достаточно маленькие, и можно запускать тупой dfs или bfs из какой нибудь граничной точки. Таким образом мы помечаем всё что сожрут жуки. Остается только пробежаться по нашему полю, найти всё не помеченное, и вспомнить, что наша клетка это какой то прямоугольник в старых координатах, и добавить соответствующую площадь к ответу.
Сходу непонятно, как зная интересные координаты масштабировать поле, то есть сжимать прямоугольники в точки.
посмотрим на передвижения чувака и запомним в каких точках он бывал, соответственно теперь мы знаем интересные координаты. Теперь отсортим их отдельно по Х и по Y, выкинем повторяющиеся. Теперь как узнать по интересной координате xs, xn в новых координатах? Очень просто — xn такое что X[xn] == xs; где Х — массив всех интересных координат. Т.е. одним бинарным поиском по старой координате находим новую. Теперь повторим движения чувака, делая тоже самое, но заменяя его реальные координаты на сжатые. Решим исходную задачу, заведя матрицу всего поля, и думая что у чувака грядка размером 3000х3000 и он ни когда не доходит до её границ. А когда будем считать ответ вспомним, что размер клетки (i, j) на поле не 1x1, а axb, где a = X[i+1] — X[i], b = Y[j+1] — Y[j]; как то так
Большое спасибо за объяснение.
hi, i'm confused that why the java function BigInteger.isProbablePrime always lead to Runtime Error？ It's right in some OJ, but always RE in others like CF. Can you explain it? Thank you!
It has been discussed in Russian somewhere. The problem occurs because of security policies: BigInteger.isProbablePrime() uses SecureRandom which could be prohibited
i see it, thank you!
Как скоро будет разбор?
завтра
When we can have the tutorial??
The post said that day (contest day) "Editorial will be tomorrow." actually it didn't happened. But we can't say the are saying lies. because today it says "Editorial will be tomorrow.".. so logically they can never post a editorial :D but we can hope they will. (just joking) i hope this "tomorrow" will have an upper bound. :D
It seems editorial is ready, but it still isn't available in english, but you can see it in russian.
So how do u solve The Brand New Function
What's the idea of div2_C?
It would be great if we have a tutorial soon :) :). waiting for the tutorial :) :) :) thanks.
tourist ты пьян иди домой)
Why my code get TLE on DIV2_D?2602812,I need your help!
What a coincidence. All the codes of MDantas and Manoel look identical.
Indeed!