UPD: разбор
UPD:
D2: 500 1000 1500 2000 2500
D1: 500 1000 1500 1500 2500
UPD: Важно: контест проводится в необычное время! http://www.timeanddate.com/worldclock/fixedtime.html?day=20&month=7&year=2013&hour=17&min=30&sec=0&p1=166
Привет!
После шквала нестандартных соревнований (memSQL, ABBYY, Yandex), мы представляем вам стандартный, забавный (и странный) раунд Codeforces. Этот раунд подготовлен группой авторов из Индонезии: fushar, jonathanirvings, и я (dolphinigle)! fushar готовил D2-E/D1-C, jonathanirvings готовил D2-B, остальное делал я. Для меня — это мой четвертый раунд после Codeforces Beta Round 87 (Div. 1 Only), Чемпионат КРОК 2012 - Финал, и раунда на прошлой неделе MemSQL start[c]up Round 1 (там была только одна моя задача). Мы также хотим поблагодарить Gerald за помощь с контестом, Delinur за перевод, и MikeMirzayanov за систему!
Мне кажется, что этот контест более странный, чем обычные контесты — условия странные, куча картинок везде и тому подобное. Есть даже одна задача с очень длинным условием (к сожалению, я не могу сделать его короче не теряя сути условия). Остальные задачи имеют короткие условия.
fushar оставил для вас сообщение:
Мы думаем, что решения всех задач очень интересные для "придумывания". Вам может показаться, что решения задач не такие-то "обыкновенные".
Приятного решения задач!
Хочется поскорее увидеть эти необычные задачи.
И углубится в чтение и понимание условия на 2 часа?
Можно.Но 2 часа уже перебор.Нужно ещё успеть код написать.
WOW like that kind of contests.
But to clarify, what do you mean by "unusual" or "unusual solutions"?
Nothing drastic really -- you can compete as if it's a normal round and you should be fine :)
Is it similar to April fools day contest?!
Don't you see that author said that it's a normal round?
May be the problems will have less similarity with past problems and the solutions are not as usual as we seen before.That means no chance to have a common problem. But that's only my point of view. :)
What you said really arouse my curiosity."you might find that the solutions will not be too “usual” " I hope I can solve some of them.
I imagine some crazy ad-hocs (contruction algorithms with tolerance, debugging a code, games where game theory is useless...) as strange tasks. In general, I don't find "strange" good, because it's easier to mess up when preparing such problems... oh well, I'm travelling to IMO during the contest, so I won't be able to participate no matter what.
This is a good time to test out the new polygon's features then!
Tests for checkers and validators! >:)
This new feature is awesome. It really helps!
I think it was tested in Test round 8.
I have used polygon for a contest and my problems are ready.But I don't know what should I do now!How to submit theme to Gerald or... ? Sorry for poor English
F**k IMO, compete at CF!!!
That's really rude. :/
What I can say is: the problems will be interesting, and you will be very satisfied when you solve them :)
What I can add is : When you solve them, you will be proud of yourself, as we are :)
You should mention about the unusual time in this contest!
Right! Thank you!
"Есть даже одна задача с очень длинным условием (к сожалению, я не могу сделать его короче не теряя сути условия)."
А вот в ABBYY это могут сделать) Кто был на онсайте поймёт)
Или те, кто читал разбор.
Краткость — сестра таланта
i cant wait :3
You can wait She can wait He can wait We can wait They can wait
is the earlier time because of indonesian setter :P ?
i like this kind of time :D
The usual time is 10.30PM in Indonesia. That's too late for some of us :)
Супер, после шквала нестандартных соревнований будет стандартный, но странный раунд. :)
И я за! Даешь задачи для div2, а то решать одни и те же задачи c div1 сложновато. На последнем соревновании (ABBYY Cup 3.0 — Finals (онлайн-трансляция)) занял 362 место и ... понизился на 15 пунктов в рейтинге.
Изменение рейтинга определяется не только занятым местом. Оно определяется также тем, насколько занятое место отличается от предварительно расчитанного ожидаемого. Ожидаемое место расчитывается исходя из рейтингов всех участников раунда. Поэтому нет ничего страшного в том, что в смешанном раунде есть участники с большим рейтингом. Если выступил "как обычно", т.е. как ожидалось, то рейтинг изменится приблизительно также, как если бы это был Div2/Div1 раунд. А вот если будучи "синим" прыгнуть выше головы и обойти большинство оранжевых, то прирост будет гораздо больше, чем если бы это был Div2. Бывают случаи, что синий прыгает через два цвета и становится оранжевым, например. В Div2-only раунде такое невозможно.
Everything is unusual. Expecting an unusual increase in rating too :-)
Слова "стандартный" и "забавный" раунд меня радуют, но "странный" почему-то пугает. а особенно условия "в картинках" — всегда с ребусами проблемы были
The other problems have relatively short statements.
I love short statements.
Seems a cool contest! "This contest is stranger than usual"
I hope I am able to solve at least one! I'm not very good at these contests and this would be my third contest
Hope that unusual solutions will uplift my rating unusual up. :)
Lol like someone already commented: http://mirror.codeforces.com/blog/entry/8402#comment-141506
It's nice to see many up coming contests already scheduled, this is going to be a very interesting week!
It's just a test~~~~
Codeforces is a test for me, too~~~~
What is the scoring method? If it's static scoring, what are the scores for each problem?
It will be static. We will release the scores some time before the contest.
Ничего не сказано о разбаловке... Может для "интересных для придумывания задач" лучше динамическую UPD: Недоглядел английский коментарий автора соревнования
the contest will not be usual, en...., but I hope the contest will fit our taste, good luck & have high rating for everyone~
Ура, толпа не слишком сложных задач — это здорово =)
Я совершенно уверен, что регистрировался на раунд. Меня, правда, тогда почему-то перенаправило на страницу со списком команд, которые меня приглашают, но я не придал этому значения. Можно ли это все-таки как-то исправить?
Does 'mikemon' stand for 'Mike — monster'?
Not intentionally :)
...i thought "mi-ke-mon" sounds similar with "po-ke-mon" >:)
A really unusual contest!!
Is it possible that n can be equal 1 in Problem B div 2???
Sure: http://mirror.codeforces.com/renderer/94f406a06721e89d57a14b6dfade59c6341e93e8.png
yes ... number of roads is 0
Unusual number of hacks!
I really like today's problems! But the number of hacks is a bit disappointing
Just find the bug several seconds after the contest finished!!!!WTF
Div-1 C — Разбор случаев?
Или random_shuffle. =) Я не придумал, как его валить.
UPD: А вот свалилось, поди ж ты.
UPD2: Если увеличить количество итераций в 10 раз, заходит.
Можно поподробнее, пожалуйста? У меня задача свелась к тому, чтоб разбирать циклы длины 3, 4 и цепочки длины 2, 3, 4.
Много раз берем случайную перестановку вершин, пытаемся соединить их в указанном порядке.
Утверждается, что на больших тестах вероятность зафейлиться крайне мала, а на маленьких можно успеть перебрать все перестановки.
Фигачишь ребра рандомные, чтобы степень у каждой вершины была не больше 2. Если все получилось — выводишь, не получилось — еще раз пробуешь :)
Впрочем, я верю, что задача решается честно каким-нибудь разбиением вершин на классы, но лень было думать, когда можно заслать незаваливаемую фигню. =)
Вы пробуете много раз рандом шафлить вершины, потом пытаетесь поставить рёбра вида i,i+1. потом у вас образуется много цепочек. и каждую цепочку пытаетесь сделать циклом. Если рёбер уже хватает, то бряк. Утверждается, что на больших тестах это зайдёт потому, что маленькая вероятность попадания на запрещённые вершины, а на маленьких, потому что много успеет перебрать.
Пытался решать жадным конструктивом, основанным на текущем множестве вершин степени 0, множестве вершин степени 1 и множестве запрещенных ребер. Претест 10 — WA. Весь контест не мог понять, почему он может давать неправильный ответ. Когда откроют тесты, станет понятно, ошибка в коде или алгоритм неверный.
Около трехсот с лишним мест занимают люди, решившие 2 задачи. Раунд = кто быстрей закодит халяву.
Как решать D? конструкция
получает только 85к
Может быть
UPD: именно то, что написано ниже
repeated 50 times. Initial active stone is at (99, 1).
One cycle gives 66 sounds (33 at the top and 33 at the bottom), and there are 33 cycles (until “^” can freely move up, where it activates the next cycle and gives another sound.
50 × (66 × 33 + 1) = 108950 sounds in total.
Думаю, что примерно так сработает, если <<<<<<< в конце около 50:
Вроде ряды ниже второго бесполезны тут
Was it only me who noticed that 3 questions(!!) had something to do with matrices.
Wonderful contest. I don't think the problems are as strange as I expected before, but Div 1 D is certainly strange (pretests are all tests, and it's not really a programming problem) and it is certainly my favorite.
Also, in my room, only I submitted a hardcoded answer (for D)? Only I ripped off the first two cases from the sample cases (which then I regretted as it makes the second test case run for absurdly long)? :P
Wonderful contest! All problems are special and enjoyable to solve. It's really amazing to discover solutions!
Thank you for the contest! D was definitely memorable.
Speaking about D, does anyone have a successful ring-based approach? I get a feeling there might be a solution but it'll be considerably harder than snake-based approach. My best try took about 85.8K.
this is my first time to join the codeforces contest and i feel really excited to beat the buzzer~....the questions were not too unusual....
still slow…… sbcf…… I pressed "submit" when there were only 10 seconds left. After 20 seconds, Codeforces show me an error page...
But it seems like you didn't participated in this round :D
sorry to hear that but= =..YM!
What does sbcf mean?
I had MLE wtf?
http://mirror.codeforces.com/contest/330/submission/4121993
visited[i][j]=true; bad idea) Need in if() { visited[i][j]=true; }
Looks like you can add vertices to the queue more than one time, because you don't check visited before adding. Try empty field 20x20 and look at the size of your queue.
Yeah, it's MLE.
Found D1-B funny: despite the huge statement about mikemon breeders looking at the path beforehand, it is completely irrelevant for their optimal strategy anyway (they should all just run to the exit as soon as they can!)
Exactly. That, I believe, is the crucial deduction; after that it's just implementing breadth-first search from the exit to see which breeders can reach the exit before or at the same time as we can.
Additionally, even though we're not required to minimize the number of moves, the optimal strategy is indeed to minimize the number of moves to reach the exit.
It was a very amusing contest , In problem D , I spent a very long time in the contest trying to figure how to get the shortest path from some nodes to a node avoiding high complexity, and I totally forgot that it's the same from the other side :D Changing the starting point of the BFS will make the code pass :'(
very slow system test:|
I solve problem D div2 2 minute after end of the contest:(((((
You aren't the one, i only figured a bug in my code of D div2 after the contest ended..
for problem div2 B Road Construction. in case 1 is WA for input 4 1 1 3 output 3 1 2 1 4 2 3 why is incorrect?
The distance between every two nodes should be at most 2 roads , in your solution the distance between 4 and 2 will be three roads.
You need 3 roads to go to #3 from #4
.
because you would need three steps to go from 4 to 3
I don't know if I got the question wrong. some of the solutions are accepted but for the following test case they give wrong result.
4 2 1 2 3 4
For above test case they dont print anything but solution exists. 1 3 1 4 2 3 2 4
Number of deleted edges (m) must be less than half of number of vercies (n).
thanx dude! I got it.
Can anyone point out the mistake in my solution http://mirror.codeforces.com/contest/330/submission/4121524 for Div2 D/Div1 B — Biridian Forest? I have used a bfs to compute distance of the exit from each point. I have stored the graph in 1-indexed arrays and put trees on the boundary so that the algorithm does not process invalid points.
I don't see where you check vis array when computing the answer. You may add to result points from which finish is unreachable.
See the comment below for the example.
I check it here: for(int i=0;i<4;++i){ int newx=x+dx[i]; int newy=y+dy[i]; if(vis[newx][newy]||(inp[newx][newy]=='T')) continue; vis[newx][newy]=1; } I don't include a point if it is a tree. I have added trees along the boundary too. How can unreachable points go into the queue?
EDIT: Got it. This mistake cost me a colour change :(
Try this case:
Thanks a lot. I got the same mistake as kira.
Found it. Thanks
It looks like someone throws the testing machine into water...more and more slowly...
Proud to be Indonesian! too bad I competed on Div 1, my skill is not enough to "enjoy" all the problem, lucky I could solve 500 pts problem.
Btw, I'm a big fan of fushar/Ashar Fuadi (yes, I said that). I never beat him on local contest, my team's best result was able to solve as much problem as fushar's, but beaten by time penalty. He's a very good problem solver/setter, and a humble person too. This year is my last year in university, so last year competition season was my last season. So good luck for you and your team fushar, hope you all will achieve World Final next year. And good luck for jonathanirvings too, Go Get Gold! And dolphinigle too! (too bad I don't know dolphinigle personally).
Well, thank you very much! ^ ^
My solution for Div2-C is wrong and got AC.
Input:
Output:
While the minimum number of spells is 4.
If I were you, I would not advertise it
Looks like I missed this test case.
Originally the problem has more than 120 test cases, but to make system test faster we decide to reduce it to 60. It's likely that I accidentally removed the case that would've countered your solution.
Sorry and thanks.
Единственное зашедшее решение по Div2-Е 4121855
Убило! :D
Examples were explained very good and pictures were really nice and clear. Thanks for the contest.
Ого, так быстро рейтинг посчитали
Really love this kind of contests. Thank you dolphinigle, fushar and jonathanirvings!
I spend one hour to find a deterministic way to solve C, but it's too complicated to code. After some minutes of despair, I figured out if N is large then there will be lots of solutions, so I code a naive random algorithm and passed.
After the contest I read the problem D, it's more interesting! If I read both C and D, I will definitely try D first. :)
By the way, does "mikemon" in problem B refers "pokemon"?
Thank you! I'm really happy to hear people enjoying my contests :)
...and for the other question, I replaced "po" with "mi" >:). You should read it "mi" "ke" "mon", not "mike" mon.
Actually my personal intended solution is the deterministic one, but we also let randomized solutions pass quite easily :)
By the way, there exists a deterministic solution that is not very complicated (although there are too many tricky cases for this problem) in the editorial soon.
Yes, this actually refers to Pokemon, but we were afraid of copyright infringement so we changed it to mikemon :P
Here comes a deterministic solution.
First check whether this graph has a connected component of size no less than 5, if so, we can use these vertex to construct a circle. It's easy if we connect vertex i with (i+2)%size and be careful when size%2 == 0.
Otherwise if there exist two different connected component of same size 2,3 or 4, we can construct the circle easily by union them. You can also do this when you have four isolate vertex.
Now we keep this circle in hand, then for all other connected component, if its size is large than 4, we just construct a new circle by themself, otherwise we can insert them to the circle we keep because the circle's size is no less than four.
The only question now is how to deal with the situation that we can not build a circle first. If so, this graph can just contain at most 3+2+3+4=12 vertex, then we can do a simple search algorithm for that.
I come up with this idea durning the contest and spend more than half an hour to code it but finally fail, it's really a huge work for poor me. I feel very depressed when I see so many random solution pass the system test >_<.
Here is my accept code, it's a little bit ugly... http://mirror.codeforces.com/contest/329/submission/4123108
But indeed, it's a really nice problem, thanks for your work. :)
Do we have some guarantees of the accuracy of the randomized one. Actually I use a deterministic solution employ divide and conquer of time complexity of O(nlogn) and deal with a tricky case of circle_length=3.
Thank you. I'm really happy to hear that. Actually I only wrote Div-2 problem, so I couldn't "entertain" Div-1 users in this contest. (Well, maybe next time :))
Though I got -49, The contest was really good and encouraging for all, specially for beginner. :)
can anyone please tell me why my solution of Div 2-B is giving WA on test 29 as it is giving correct ans on ideone as well as on my system also... my solution-- http://mirror.codeforces.com/contest/330/submission/4116737 http://ideone.com/Wet1Tt
You didn't initialize your visited array with falses
But then how it passed 28 test cases?
Как решалась бы Div-2 D, если бы, когда заходишь на выход и не ждешь микемонов, то есть сразу выходишь?
В моем решении просто знак <= поменять на <.
Нет, вся идея, что надо ждать у выхода сломается, и в случае одновременного прихода придется смотреть кто с какой стороны пришел.
Если бы не ждали у выхода, то ждали бы у одной из четырех соседних клеток.
The contest was really good . . . .
how can I see why my submission to "Purification" (div1-A) problem gives compilation error?
Ok, I see, I forgot #include Anyway, how to use "custom test" to see that?
I mean I forgot "include cstdlib". I don't know how to use "custom test" to see that.
If you click on compilation error you will see what's the cause of CE. Edited : Sorry! Didn't see your last comment.
It gives "exit was not declared in this scope" on my computer.
You should be able to click on the "Compilation error"?
But anyway, you declared i four times, in each for loop. That gives the compilation error (redeclaration of variable).
EDIT: Weird, I tested redeclaration and got compilation error, but when I copied your code instead, it gave the "exit was not declared" error as above. So the reason I gave above might be incorrect.
That is not the reason. i is considered to be declared in the loop, so it is not a redeclaration.
In custom test you will see your compilation error on output section.
I got the message "Error: Form elements must not have name or id of "submit"." I don't understand this message.
I don't know about this message but I slightly modified your code and it gets wrong answer instead of compilation error. Here is the link : http://ideone.com/CzovZo Can you give me the link of your last code?
You just check the rows.You should check the columns too.
Anyone can say me what is wrong with my submission in problem B here:
http://mirror.codeforces.com/contest/330/submission/4121515
The checker simply says that : wrong answer You cannot constract bad roads.
Which bad road did i constract? How can i see it. How can i see whole input, answer and output for the wrong test?
It's not possible
You have connected nodes 2 and 65 that are not allowed to be connected.
you connect 2 with 65.
Nice contest! Thanks!
(Y) (Y)
I didn't manage to participate, but my friends are saying it was lots of fun. I hope problem setters make more of this kind :)
Прочел сейчас задачи второго дивизиона, меня одного смущает это в первой задаче?
Ну и первый же пример — "квадрат" 3х4
Меня не смущает. Торт 3х4 вполне может быть квадратным, если состоит из прямоугольных ячеек (4см х 3см, например). А вот "квадрат" на рисунке действительно смущает
Very interesting contest! Like Problem D in Div-2 the most! I always enjoy solving the problems that seem complicated and require the contestants to think in a clever way.
BTW, can someone give me a hint for E in Div-2? It has puzzled me for a while.
[Div2:B]After the contest, I suddenly tend to realize the importance of the constraint m < n/2, which ascertains the existence of a central junction which could be connected to all the remaining cities. My Question is: What if we relax the condition m < n/2. Let m be any number.
For example (A test case):
6 7
1 3
1 4
1 5
2 6
3 4
3 5
4 5
Here there is no central junction but there is still a solution which is:
8
1 2
1 6
3 2
3 6
4 2
4 6
5 2
5 6
What would be the algorithm in this case?
Sorry, that was a bad idea.
If the solution exists, it would certainly be a complete bipartite graph, but I don't know the algorithm for dividing the vertices between the two sides.
haha
http://mirror.codeforces.com/contest/330/submission/4120466
hey well done guys, it was an interesting contest! the only thing i would like to suggest for future contests is that u increase the possibility of hacking by excluding a few corner cases (not all, mind you! :P ) from the pretests!!
Could anyone please tell me why this code behaves differently on Codeforces and ideone (also my laptop, if that's a valid standard for anyone)? I get wrong answer on pretest 12, but it works correctly on the aforementioned platforms.
Thank you in advance.
http://ideone.com/c5kfDT http://mirror.codeforces.com/contest/329/submission/4122055
You are removing some elements from the set in another level of recursion, and when you go back the iterator still points to the removed element.
Check this code (same error): http://ideone.com/nzrPXb
Thank you :)
today's contest was a great contest, OMG!! um loving codeforces. Coderforces why you are so lovely and sweet?? :)
codeforces i love you
Want to get minus? -_-
codeforces is better than topcoder in all ways.. and its the best in the world
I haven't see in the table submissions if they don't have AC. It's true only for div2 table viewing friends result
you better working on your grammar side.
You too.
Guys, thanks for this contest! Now waiting for tutorial)
Здравствуйте, объясните пожалуйста идейно задачу Div.2 (B) Заранее признателен...)
div1(B)
Если мы возьмем какой-то город и соединим его со всеми остальными городами, то получится как раз то, что нужно. Осталось только найти такой город, который не принадлежит ни одной из запрещенных m дорог и соединить его с остальными (n — 1) городами. Такой город найдется, поскольку m < n / 2.
Hey, that was a good contest. I regret missing it.
By the way, in Div2 B the constraint
m < n / 2made it pretty simple.How would you solve it without this constraint?
Some solutions to Div1-C work as follows: choose a random cycle on the N nodes and see if it works (some edges in the cycle may be invalid and we can ignore those).
Why does this work? What's the worst case probability that a randomly chosen cycles isn't valid?
One bad case seems to be when every node in the input graph has degree 2. In this case, every edge in our random cycle must be a valid edge.
This is one of the intended solutions -- we set the time limit so high that even python solutions will pass using this method.
A rough approximation I used is by evaluating ((n — 2) / (n))**n. On n=100,000, it is 0.135. I think the actual number shouldn't differ too much from this (like how Derangement Probability does not differ too much from ((n-1)/n)**n).
Nice (Ad-hoc) Contest. Tutorials please . :)
Here it is! http://mirror.codeforces.com/blog/entry/8417
Problem C:can anyone explain how the case no 10 can be purified ? , the answer that is given cannot purify cell no (5,7) & (5,8). my answer is -1 and it gave wrong ans. :(
in edition according to editorial as it has 5th row and 8th column completely full with E it can't be purified , am i understood wrong? :( PS — it's test ( not pretest ) i am talking about.
The correct answer of tenth test case is -1.
So what goes wrong? It is YOUR code gives a solution, which is invalid, not jury's.
sorry , i just wanted to know why wrong and not who's wrong ; and i believe jury's are much much better than me and i'm not being disrespectful; :) editorial says: "If there exist a row consisting of entirely "E" cells and a column consisting of entirely "E" cells, then the answer is -1. This is since the cell with that row and that column cannot be purifed." test 10 input: 17
EE...E.EE.EE..E..
E.....EE..E..E..E
EEEE.EEEE..E..E.E
.E.E.EEE.EEEEE...
EEEEEEEEEEEEEEEEE
EE.E.EEEEE.E.....
..E.EE.EEE.E....E
.E..E..E...EE.E.E
EEEE.EEE.E.EEEE..
...E...EEEEEEE.E.
..E.E.EE..E.EE..E
.E..E..E.EEE.....
.E.....E..EEE.EE.
EE.E...E.EEEE.EE.
...EEEEEEE.E..E.E
EEEE.EEEEEE....E.
..EEEEEEE....EEEE
the 5th row and 8th column is entirely of E
so , why the answer is not -1 occured to me.
hope i got a explanation not what's correct answer
The answer is -1, while your output is not.
(sigh) it's the answer and i know that but how , please can u explain a bit elaborately :(
But you have already explained it — as long as fifth row and eighth column both contain only 'E', answer is -1, because you can't purify (5, 8) anyhow. What else do you want to know further?
Notice how judge's verdict is located:
oops , got a bad eye , sorrry
This often happens with me XD
Задачи были хорошимы. Единственный минус — взломов почти не было!