Всем привет!
14 ноября, 19:30 MSK состоится Codeforces Round #212 (Div. 2), который был подготовлен коллективом авторов из Саратовского государственного университета в составе: Артем Седанов (FunkyCat), Сергей Сухов (Serega), Ольга Чикатуева (Helga), Дмитрий Зайцев (My-my).
Выражаем благодарность координатору раундов Геральду Агапову (Gerald) за полезные советы и Марии Беловой (Delinur) за перевод условий на английский язык.
Всем удачи и высокого рейтинга!
UPD1. В раунде будет использована динамическая система оценки сложности задач (см. здесь).
UPD2. Разбор задач опубликован здесь.
UPD3. Рейтинг обновлен. Поздравляем победителей, решивших по 4 задачи:
желаю участнику, занявшему 100 место, решить хотя бы 3 задачи :-)
Не судьба. 100 место решило только две :)
И вновь увеличивается количество раундов, проведенных авторами с префиксом Sere
Sereja's round :D Hoping for a good increase again !!! Good-luck to all ...
Sorry But this is Sereja http://codeforces.net/profile/Sereja
Notice the name difference.
Still hoping for an increase in rating :D
Yeah, that was weird to see
Sereja being violetSerega.Я бы даже сказал, авторов, удовлетворяющих regex-шаблону "Sere\wa"
Автор же не виноват, что его зовут СЕРЕга. Почему он должен брать себе другой ник, если уже есть некоторое количество СЕРЕжа, пусть даже и чаще его являющееся авторами раундов?
P.S. не всегда ники совпадают с именами ;)
Hope that we have an interesting contest. ^^
Динамика — это интересно!
Problem statements of previous Serega's contest were horrible! I hope problem statements will be easy to understand!
А как же "По мнению авторов, задачи расположены по неубыванию сложности"? :(
А как же "Cоветуем вам прочитать все задачи"?
Если Вы не заметили то это фитча автора Sereja, а не Serega.
Это еще и фича Burunduk1.
I hope the problems will short for understand :)
Ну просто безпалевность 80 лвл
Извеняюсь за глупый вопрос, я решил задачу "B", заблокировал ее. И теперь хочу взломать чье нибкдь решение.
Через "Положение" смотрю тех участников которые решили эту задачу и заблокировали ее. Когда я открываю ее, там например написано:
Претесты пройдены [претесты] → 5103228
что нужно сделать что бы попробовать взломать решение?
Когда нажимаю на ссылку "5103228", то нечего не происходит.
Может я что то не так делаю?
Можно ломать решения только участников из твоей комнаты. Там сверху вкладка "комната" есть. В этом и фишка :)
спасибо, я впервый раз только учавствую.
Блин 4 мин. до конца контеста осталось, и меня взломали))
обида...
Все задачи кроме "B" на Div 1 годятся.
Задача A в принципе, не такая уж и сложная. Задача C понравилась. Жаль не успел написать :(
Из текста картинки предположу, что в какой — то задаче надо было написать какой — нибудь жесткий алгоритм. Просветите, в какой? :D (Поток в Е не считается, там блин n <= 50)
Что-то мне подсказывает, что считается:D (link)
N блин 50. Можно было написать самый тупой минкост в 15 — 16 строчек за N ^ 5. Сложности в реализации нет, подойти к самой идее намного сложнее :D
Имелась в виду задача E. Я считаю что даже простейший поток это не тема для Div 2. Да он элементарно пишется, но вот понять его полностью и доказать уже тяжелее. А запоминать алгоритмы можно только если это QuickSort.
А, ну ты, скорее всего, прав. Полностью доказать это и правда сложно для Div — 2.
Зачем так гробить задачи?
Зато системное тестирование сразу началось :)
It seems that the final judge in this contest is not sorted by submitting time !
Неужели все — таки чем ниже рейтинг проблемсеттеров, тем выше сложность задач в Div2 — Only?
Problem C and Problem E. Waiting eagerly for their editorial. Especially E, that was really beautiful.
In E you can use min-cost-max-flow algorithm for some graph. Tutorial will be published soon.
Problem D can be solved with Union-Find, right?
I think we can use Heap to solve D.
Pretty sure the solution for D is a combination of greedy (for choice of roads) + implementation of choice (union-find, heap...)
You're right. I solved that way. But I had 2 stupid bugs that made my solution fail.
This indeed was a fun contest. Problems were nice, they were composed in a way that it would be likely for contestants to make some mistakes which later could be hacked. :) Can anyone tell if third problem was solvable with a segment tree. That may not be the optimal way, but I guess it would pass.
Подскажите, в задаче А можно было заполнить две матрицы для каждого коня соответственно(1 — конь будет в данной позиции, 0 — нет), разбив матрицу на четыре подматрицы (начиная с положения коня) int k = 0; for(int i = x;i <= 8; i += 2, ++k){ if(k % 2 == 0) for(int j = y + k * 2;j <= 8; j += 4) f[i][j] = 1; else for(int j = y;j <= 8; j += 4) f[i][j] = 1; }
и потом сравнить как нибудь так?
bool merge = false; for(int i = 1;i <= 8; ++i) for(int j = 1;j <= 8; ++j) if(f1[i][j] == 1 && f1[i][j]== f2[i][j] && map_[i][j] != '#') merge = true;
Нужно было посчитать количество ходов(а конкретней — четность этого количества) для достижения каждой клетки. В одну и ту же клетку нельзя попасть с разной четностью количества ходов — следует из особенности возможных ходов. Если два коня могут попасть в не закрашенную клетку с одинаковой четностью ходов, то ответ, очевидно, 'YES' — недостающие для какого-то коня ходы мы можем делать, двигая его туда-сюда, не теряя четности.
Один из вариантов — поиск в ширину, подобно решению задачи http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=255&chapterid=163, для удобства используем четырёхзначные числа, как маски, обозначающие взаимное расположение коней (пускай у нас число abcd. a,b — координаты первого коня, c,d — координаты второго) и просматриваем все возможные переходы из начальной маски. Если среди всех найденных масок будут числа вида xyxy, то ответ, очевидно, YES, иначе — NO. Решение не отсылал, но, судя по ограничениям, должно работать.
Впрочем, надо отметить, что в данной ситуации возможны и частные решения, как, например, решение demolishka.
Most of the solutions for problem B got accepted only because of pure luck. Solutions that use:
if(s[0]==1||s[m-1]==n) { cout<<"NO\n"; return 0; }should get 'Runtime error' becase m can be 0 :).
You're wrong at least because almost all of theese people check this case like
`if(!m){` ` puts("YES");` ` return 0;` `}`I am afraid I am not wrong :). Please check my room: http://codeforces.net/contest/362/room/44
Positions 1, 3 and 7 have this error. There are also others with this problem in the same room :). Accessing v[-1] memory is undefined behavior :).
Luckers :) It must be runtime, really.
I tried to hack a solution using this but it didn't work. It depends on what value is at address s-1.
this case is covered, check Test #8
I got AC without handling m=0 as sorin said "It depends on what value is at address s-1"
Correct.
I do think that
would pass, but (saw it while reviewing my own code)
could cause RTE. If the first case is true, it won't produces a positive output without testing the another.
Good Problem set, with the wonderful dynamic scoring :) #loved it
Мне понравились задачи, спасибо автору. Жаль, 20 минут не мог найти багу в С:
if (a[j] < a[i]) d--;(вычитал на одну инверсию больше, чем нужно) — лишняя строчка, без неё AC в дорешке.Что касается Е — ну, поток и поток. Это не какой-то сверхсекретный или сверхсложный алгоритм. Я, будучи во втором диве, знал его. А по бложикам, периодически всплывающим на форуме на эту тему, можно понять, что и многие другие из второго дива также его знают. Ну и в конце концов, не всё же лёгкие алгоритмы писать.
in problem B, for the simple test case 1 1 1, which means that he does not have to make any move. My code gives output "YES", i.e. it is reachable, but the answer is "NO", why? I still think the answer should be "NO", for he managed to reach the nth stair. please help me understand if i am going wrong.
read problem statment carefully
"One has to note that anyway Petya should step on the first and last stairs, so if the first or the last stair is dirty, then Petya cannot choose a path with clean steps only."
but for that case, he does not have to step, he was standing on the dirty stair.
he got 1 stair which is dirty and he already step on it , how do you want to find a path with clean stairs only if the starting stair is dirty !!! read the problem again
and his path should start from the next stair he steps to. I knowingly wrote in my code that if n equals 1, then he manages to reach.
he musr start from the stair 1 and stop at stair n , so if one of them is dirty he can not find a path
I still think I should be correct, but am bound to accept. thank you BAHOSAIN
u r welcome
задачи понравились!спасибо за контест!
Баг? Цвет — фиолетовый, а рейтинг — старый (1669)?
Пруф
Изменение рейтинга откатили. Ваш К.О.
Теперь-то уже видно. Благодарю за ответ.
А почему откатили кто-нибудь знает?
может быть из-за этого
Возможно.
In problem A, I tried marking every position K1 can go in matrix a,and every position K1 can go in matrix b. Then I checked for every post if(k1[i][j] && k2[i][j] && original!='#') . why did this algo gave wrong answer in test case 7?
This is because they have to meet at the same time. An example is the test given in the statement.
About problem A, I also want to ask for why the first board of test case 6 can output 'YES'? Could anyone help to explain it?
Check out this case:
Since the knighs move simultaneously they can never reach the same position. For every possible position they can reach one knight has to make an odd number of moves to reach that position while the other has to make an even number of moves. That means they can never be at the same position.
Please tell me, how half-knights can meet on this map?
Half-knights in both cases are on the one square.
oh, they can meet at starting position...thanks
Thanks,I got it. Just neglecting to take 'K'-value-position into account. What a pity.
Yes the bad squares had no use. If they can be on same place they can be on start pos.
both of them go to 2, 2 then both of them go to 0, 0
UPD4: Ratings is fucked!
UPD5: Ratings is updated again.
UPD6: Ratings is fucked again.
This is an infinitive loop :|
k = 0; new_rating = old_rating + k;
In problem B, problem statement says, "The second line contains m different space-separated integers...". But actual test cases did not have the second line if m = 0. That's reason why many answers written in script language got RE.
Why it is so important to have the second line in test case if m=0 ?
I believe that m=0 is enough to check if solution is correct for this case.
Script language like Python or Ruby, there are no easy way to read integer tokens like scanf or iostream, so programs must handle input by lines and split them into integer list.
Please compare these two submissions. 5103785 5103965
Yes, I run into the same problem. I spend half an hour to check my program. Only after the contest do I know where the problem is with practice mode.
Ratings are back ... yeyy, +168.
Old rating again!
In problem C n^2 solutions have passed but my (n^2)(lg n) gave tle. :( . It passed the test case with n=4500 but gave tle with n=5000.
Does any one except me used DFS for A ?!
I didn't understand the main solution but simulation worked perfectly ;)
Code
My solution: if semiknights can meet in first step then "YES" and "NO" otherwise.
I use a BFS.
a better way is to check if (x2-x) mod 4=0 & (y2-y) mod 4=0 then the answer is "Yes" otherwise "No" :)
a much easier algo is just to check if
abs(x2-x1)andabs(y2-y1)are both divisible by 4, then answer is YES. if either of them not then NO.I fail in the most simple test case, a graph with one node.
question of problem C: the third test data: 5 1 3 0 4 2 It can swap(0,2) to get '0 3 1 4 2',so this premutation only needs 3 times of 'swap',but why the standard answer is 4 ?
The third test data is
5 1 3 4 0 2but not5 1 3 0 4 2.Oh,thx..I have made a mistake.
It would have better if pretests had less details especially at problem B like dirtiness of first or last stair ...
Пожалуйста можете объяснить один пример input 1 ...#...# ........ .#...K.. ........ ...#...# ........ .K...#.. ........ output YES Я не могу понять почему YES ведь клетка в которой они могут встретиться одновременно считается "плохой". Надеюсь на вашу помощь
Они могут встретиться в клетке, где стоит один из коней, а клетки где стоят кони — хорошие
These problems seem too hard for div2.
EDIT: Deleted (I mistook the thread for round 214 :D)
Well, E was quite hard, and A was definitely much harder than B. Other than that, it was all right.
In fact ,I mean A is a trap, and many people delay on it.
Все прекрасно :)
Разбор опубликован, ссылка на него приведена в посте. А код решений вы вполне можете посмотреть в статусе, в посылках участников.
а почему в задаче А на этот тест программа должна выводить "YES" ?
1 ...#...# ........ .#...K.. ........ ...#...# ........ .K...#.. ........
На первом ходу полукони переходят в "плохую" клетку (5,4), а на втором вместе двигаются в одну из клеток, соответствующих начальному положению полуконей.