**UPD**: Editorial

Hello!

After the barrage of non-standard contests (memSQL, ABBYY, Yandex), we present you a standard and fun (and strange) Codeforces round! This contest is prepared by Indonesian coders: fushar, jonathanirvings, and me (dolphinigle)! fushar wrote D2-E/D1-C, jonathanirvings wrote D2-B, and I wrote the rest. For me, this is my fourth contest, after Codeforces Beta Round 87 (Div. 1 Only), Croc Champ 2012 - Final, and last week’s MemSQL start[c]up Round 1 (only 1 problem there though). We would also like to thank Gerald for helping with the contest preparation, Delinur for translation, and MikeMirzayanov for the system!

I think this contest is stranger than usual -- The statements are strange, there are pictures everywhere, etc. There is a single problem with very lengthy statement (I am unable to shorten it further without losing clarity, I'm sorry), but I think it's very clear. The other problems have relatively short statements.

fushar drops a message for you:

We think that the solutions to all problems are satisfying to discover. We want to add a special note: you might find that the solutions will not be too “usual” :).

Happy solving!

**UPD**: The contest is finished! Editorial will be posted tomorrow by fushar. Hope you enjoyed the contest!

...Div1-D 329D - The Evil Temple and the Moving Rocks was a little too strange I guess.

**UPD**: Congratulations to the winners!

D1:

D2:

You guys are certainly good at ad hoc problems! :)

**UPD**: Komaki, followed by Marcin_smu finally solved the last problem 329E - Evil after the contest. During the contest, they submitted some solutions with the right idea but got caught by pretest. You guys are awesome! **UPD**: Scores:

D2: standard (500 1000 1500 2000 2500)

D1: 500 1000 1500 **1500** 2500

**UPD**: Important: This contest is held in an unusual time (2 hours earlier than usual): http://www.timeanddate.com/worldclock/fixedtime.html?day=20&month=7&year=2013&hour=17&min=30&sec=0&p1=166

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 EnglishF**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!

i cant wait :3You 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 :)

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.

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

Как решать 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.

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?

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 :)

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.

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)

Hey, that was a good contest. I regret missing it.

By the way, in Div2 B the constraint

`m < n / 2`

made 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

answeris -1, while youroutputis 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