Скоро, 16 марта, 19:30 MSK, состоится очередной Codeforces Round #236 для участников из обоих дивизионов.
Автором задач являюсь я. Это мой первый раунд для обоих дивизионов, и я надеюсь не последний. Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке задач, Лось Илье (IlyaLos) и Александру Игнатьеву (aiMR) за тестирование, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
UPD: Распределение баллов:
Div. 2: 500 — 1000 — 1500 — 2000 — 2500
Div. 1: 500 — 1000 — 1500 — 1500 — 2000
UPD:
Соревнование закончено, поздравляем победителей!
Div.2 :
Div. 1:
- 1 sillycross
- 2 KADR
- 2 vepifanov
- 4 Endagorion
- 5 glassices
- 6 cgy4ever
- 7 rowdark
- 8 snuke
- 9 ftiasch
- 10 fsouza
UPD:
UPD:
Наконец-то раунд выпал на выходной день :)
Мне, например, наоборот, неудобно. Дома порой бывает очень сложно сосредоточиться. А в будние дни хорошо писать в универе.
Please don't click on "Rev" because I wrote something bad :(
BEG y'all for some mercy on not so many downvotes, OK?!
why you wrote something bad rather than writing something good like scoring system please don't click on "Rev" before the start of the contest I wrote Scoring System
funny :p
Отлично! я на прошлом Вашем контесте стал фиолетовым!))
Why this entry does not appear in the home page ?
Stop downvoting, it wasn't on the home page indeed at that point.
wish all participants a very happy Holi :)
your first both divisions contest after many Div2 contests :)
I wish it will be a good contest as always !!
:|
Everything is funny for the first time!
Что может больше поднимать настроение, чем вечерний контест в этот воскресный день :)
новость про то, что завтра не нужно идти на пары;)
Кому то завтра не нужно идти на пары))) это поднимает настроение)
Как же поднимает, если ты идешь, а кто-то нет?
Это в некоторых узких кругах называется "умение радоваться за других" ;)
Плохая шутка :)
Since next Div.1 contest is on March 22, this contest is "Good Bye 1392" contest for Iranian Div.1 contestants. Nowruz 1393 is on March 20 so Div.2 contestants have one more contest in 1392 :) Happy Nowruz
Лагаааать сегодня будет....
Не, с такими задачами не будет
I guess, first time DIV2 contest takes a contest-id less than the corresponding DIV1.
true that. it maybe because of the statement of the last contest's problem B
Пойду-ка я лучше тимус порешаю...
DIV1-B: Правильно ли я понимаю, что ограничения выставлены таким образом, чтобы не прошло по времени разложение числа на множители простым пробеганием по 2..sqrt(a[i]) ?
Не успел подобрать максимальное простое число, укладывающееся в ограничения, чтобы опробовать на взломе, но предполагаю, что тест из a = maxPrimes должен много решений свалить.
Нет. Нужно делать разложение за корень
6035948
Разложение за корень с оптимизацией для того, чтобы повторно не ходить по чётным. TLE 43. ЧЯДНТ? Оо
UPD: #define int long long подвёл. Сам себе злой буратино :\
тебе опыта не хватает
Ты просто мне завидуешь
Правильно понимаешь, у меня это только что упало и отбросило на 200 мест.
Вообще не понимаю в чем прикол давать такие задачи как B, в которых главное — распарсить условие и не полениться написать решето.
Лол, а еще вот такая подстава:
for (int i = 2; ll(i)*i <= xx; i++)— TLfor (int i = 2; i*i <= xx; i++)— ACЕсли уж это валить, то надо валить оба варианта.
На мой взгляд, если не требовать решето, то это будет A.
Так — хоть какой-то подвох к тривиальной идее.
А в чём прикол давать такие задачи как А, в которых главное — распарсить условие и не полениться написать два фора?)
Самое интересно, что с небольшой константной оптимизацией не решето на C++ заходит в дорешке.
И без оптимизаций все заходит.
Ну на контесте у меня был TL43.
Да нет, вроде как заходит — 6033105. Как написать разложение за корень принципиально иначе, я не знаю.
Ну я в своем сообщении написал как :) Надо конечно фиолетовым для этого быть — сейчас стану.
Кстати у тебя 935 мс — такое на контесте вполне могло не зайти.
Известно же что решения во время систестов в среднем работают слегка медленнее чем в дорешке.А, это с контеста сабмит. Ну все равно еле-еле уложилось в ТЛ.6032405 — ещё умноженное на логарифм из-за сета.
Ну, мне и в голову не могло прийти, что такое может не заходить. Я даже не запускал на макстесте. Почему-то всегда был уверен, что мы успеваем факторизовать около 10-20 тысяч чисел порядка 10^9 за секунду.
Объясните мне, в чем вообще проблема, и почему оно у вас всех так долго работает.
Я вроде бы написал обычную факторизацию за корень, без решета для простых, без прыжков по нечетным, 6056074, и оно 30 мс работает.
А зачем в первом for приведение типа?
При таких ограничениях оно не нужно. Я один раз пофейлился на такой фигне и начал везде перестраховываться. В результате пофейлился еще раз.
The overall feeling is that tasks are tend to be a bit artificial, especially B.
And for E, I can't understand the statement.
Thank you gridnevvvit! I believe your next round will be better. :)
I feel that problem C just came out of nowhere...
It was horrible Adiv2, but this is the first contest when I'm not sure in my B,C ideas at all) Smth new for me, thanks.
What is the solution for C ?
Is it just me or sometimes constraints on Codeforces are unnecessarily tight? For example today, I resubmitted B because I thought 5000 * sqrt(10 ^ 9) modulo operations won't pass in 1 second. Some time ago I got TLE for 5000 * 5000 in 2 seconds, although that was the expected complexity. Just because I also had 5000 * 5000 memory. Well today, after resubmitting I tried to hack such a solution and it fit into the limit, in something like 0.95.
So why make n = 5000 when you want n ^ 2? Why make n = 5000 today? The only way in which 5000 instead of 1000 (for example) affects the contest is that some sloppy implementations may TLE and others may not, depending on some non-algorithmic issues (cache breaking, input/output speed, speed of used operations, etc).
This was a good contest, congrats to the authors. They're not the target of this post, I'm just saying that generally we could avoid such issues if we just stick to reasonable limits, which don't cause doubts about TLE, be it for submitting or hacking.
Actually there is a faster way then sqrt(10^9)...
What is the faster way?
It's probably O(number of primes < sqrt(10^9))? (if we don't count Pollard's Rho algorithm here)
sqrt(10^9) — something finite
number of primes — infinite
=>
(numbers of primes < sqrt(10^9)) = 0
O(0) is pretty fast :P.
Btw pi(n) = O(n / ln n), where pi(n) if of course number of primes numbers less than n.
Well I know there's a faster way, do you think I resubmitted the same thing? But the optimization brings 0 additional value to the problem. So why think about if it's necessary or not? Why guess if it's needed or not when hacking?
You are using map which is red-black tree. Any number x has not got more then one prime divisor bigger then sqrt(x).
Agreed. 5000 * sqrt(10 ^ 9) failed. That makes me frustrated.
I think precalculate the prime that smaller than sqrt(1000000000) would be better. You can do it in O(n) time. That won't cause a Tle.
I've tried to hack a solution with 2 * 5000 * sqrt(10^9) operations and his solution took 0.998s... (I don't know how it is even possible to do more than 300,000,000 operations in less than 1s). As you say, I think it should have been n <= 1000 if this kind of solution was considered as OK or n <= 10000 if not. Nevermind, goodbye red :D
Totally depends on the operations. 3e8 array indices would probably be too slow, but if everything fits into the registers, you can get close to 2e9 cycles per second or so (= frequency of your processor).
My accepted D1-A solution is as follows:
For each step, create edge (u, v) with the smallest deg[u]^2 + deg[v]^2.
It does not care about p, 2n + p, nor 2k + p. What is the intended solution, then?
If you solve p = 0 then you can add any p edges and the solution will be ok. To solve p = 0 you can make a cycle out of N — 1 nodes, tie the N-th one to them and add 2 more edges somewhere. There are other ways, of course.
I didnt really understand the problem and just generate the pattern for C div2...
and got AC :v
look at this solution for the same problem :P
fuuuu, pascal
tourist usually code in Pascal. That is not make any problem to him to be the first
And what?
The condition is equivalent to saying that removing any vertex should delete at least two edges. So if for every vertex you can pick 2 edges touching it (each edge can be picked by at most 1 vertex), you're ok.
I just connected i to (i+1)%n and (i+2)%n, and added p random additional edges.
I was creating edge for min(degree[i]+degree[j]).
I simply "distributed" 2*n+p edges in the manner hinted in sample solution
1-2,2-3,3-4,4-5 .....,1-3,2-4,3-5,4-6 ....,1-4,2-5,3-7 ...
till the count becomes 2*n + p .. didnt care for the subgraph conditions
I was reducing the code written in 3 minutes (deleting vectors,pairs), until it became my solution)
Кажется, кто-то должен быть наказан.
6031777 6031879
6041332 6041177
Комната #1, обращение к тем, у кого A была заблокирована: удивлен, что мой бред никто не взломал.
Понравилась 2я задача 2го дива. Решение оказалось проще чем то, которое первым в голову пришло.
Жаль пришло это решение после 3х реджектов=(
А как её решать?
Я перебрал, какой элемент лучше всего будет не трогать (т.е. если я его не трогаю, то сколько других мне придется изменить). А потом отталкиваясь от найденного минимума вывел ответ.
Ну более-менее понятно.Спасибо.
Another Tricky Contest but there could be a lot more hacking attemps!
Почему в С работает Флойд?
А он работает? :(
6034764 — не знаю, работает ли, но авторские тесты проходит.
ну ты пушкин
http://mirror.codeforces.com/contest/402/submission/6035354 http://mirror.codeforces.com/contest/402/submission/6035395
Great!
i dont know whats the funniest of the following:
The last point is just to not affect rating if the pretests failed .
Adding comments makes it difficult for system to skip the solution automatically.
oh. so ur saying that if two exactly identical solutions are submitted, system skips the second one automatically?
i dont think this should happen. what if both codes are copied from some old blog post or any other public site?
They actually have cheated in this way during the contests 225, 226, 227, 234 and 235, so this means that their strategy is not this bad...
Sooo when will ratings be updated ???
updated.
Time limit in problem B is too strict. I've got TLE and got AC (after contest) by a small optimization. I think that either TL must be adjusted to 2s-3s or biggest test (test with biggest run time) should be in pretests.
same happened to my code..
Давно ли при нажатии на кнопку "положение" открывается страница с моими результатами, а не первая страница? Это довольно неудобно: вроде бы основной юзкейс таблицы результатов — открыть топ-20 и посмотреть, что и за сколько сдают топы. Теперь это делать чуть неудобнее.
В прошлом матче уже точно было.
А вообще у каждого свои юзкейсы — кому-то, например, интересно посмотреть, есть ли выгода от взлома. Или сколько мест он потерял из-за минуса.
Чтобы все были довольны — надо для этой фичи галочку в настройках сделать.
Минимум с 228. Ещё тогда писал об этом. Действительно неудобно.
Ты аккуратнее, так и Bredor призвать можно.
А я и приврал, ко всему прочему. Фича эта с Рокетона. Полез в посылки смотреть дату последнего контеста, ибо она тогда появилась, и не учёл, что данные за февраль были утеряны.
Ты никогда не опоздаешь туда, где тебя ждут
Видимо баг какой-то, исправим.
Time limit for D : Upgrading Array was too strict.. I got TLE but when I changed some variables from long long int to int, my code got Accepted..
Time limit for D: Upgrading Array was too strict.. I got TLE but when I changed some variables from long long int to int, my code got Acceepted..
What's wrong in my solution of Pro.B Div2? Anyone can help? Submission:6037256
So complicated way. Why dont you just find the first element of the corresponding element of array and count it? And the constraint is so small only about 1000 first element was able to counted.
If there are some element had been in the right order in sequence for a first element most, so its the most probable sequence. Then find differences with corresponding element in array. Just it
Here my solution : 6037944
Thanks.
Putting an advanced topic in a C problem even it's a direct one wasn't a smart idea i think !
Whats wrong with my idea, can anybody tell me? I have confusion with "//*******************" marked lines. http://pastebin.com/vi446T5f
Div2 D,div1 B
Actually it is quite funny mistake :D In those two lines
the iteration at which j==i (the first iteration of the loop) ... the value of Div[i] becomes 1 ... So it is not the correct value for the rest of iterations when j<i
Here is a link of accepted solution after fixing Submisson
I seriously can't understand E. If the edge (x, y) is of different colour than (p, q), then x and y lie in a different tree than p and q, so condition 2 is impossible. No?
Результаты вывесили так даже KADR на фотке повеселее выглядеть стал
I guess vepifanov placed the second, not the third.
Thanks, fixed.
waiting eagerly for Round Statistics which DmitriyH usually posts!
EDIT: its now available here, and i got my wish of my name being published! :)
I am stuck on 402D/403B. I tried several approached but I keep getting TLE. I think I am missing something here. Can someone please have a look :
Using Sieve factorization (TLE at #18) : http://mirror.codeforces.com/contest/402/submission/6050051
Using Normal factorization (TLE at #42) : http://mirror.codeforces.com/contest/402/submission/6046374
Just add this line to your first solution and it becomes fast:
I tested it here: http://mirror.codeforces.com/contest/402/submission/6050585
Thanks a lot pllk !
Задача А Div2 сложнее А Div1..
Нет.
I want to know the problem C why the tree can't have the height of 0
hi, someone can explain solution for problem E div2/C div1?
Just for the strongly connected components A^k means The path length between two points for K
Nice One for Div 2. Thank you for arranging that. Hope You will arrange some more next time. Plz post the tutorial.
There were many chances to hack, but I couldn't do at all =(
why i am not able to register for this round??
Because it has already finished.
Congratulations! codeforces, I appreciate everything that you have done for us. we're gonna have to work together in codeforce!
Hii,
in Editorial of Prblem C, Searching for Graph, Contest #236 they have talked about some 0-intersecting graphs... i dont have any idea and i am unable to find this on internet, so can anyone please give me some link, from where i can gather some information about this topic.
thank you
Laman graph is a
-3-interesting graph.My solution of Problem D is receiving Denial of judgement error. Could anyone please explain to me what is the problem?
The Submissions Ids are
http://mirror.codeforces.com/contest/402/submission/16409847 http://mirror.codeforces.com/contest/402/submission/16409976 http://mirror.codeforces.com/contest/402/submission/16420324
Someone please tell me what should be the countermeasure. Thanks in advance.