dolphinigle's blog

Codeforces Round #192
By dolphinigle, 11 years ago, In English

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:

  1. espr1t

  2. RAVEman

  3. Psyho

  4. Petr

  5. Shik

D2:

  1. RNS_MHB

  2. Parsa.pordel

  3. s0en1it

  4. RaJin

  5. darrenhp

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

  • Vote: I like it
  • +382
  • Vote: I do not like it

Comments Comments (142)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WOW like that kind of contests.

But to clarify, what do you mean by "unusual" or "unusual solutions"?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Nothing drastic really -- you can compete as if it's a normal round and you should be fine :)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Is it similar to April fools day contest?!

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        Don't you see that author said that it's a normal round?

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it -30 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +72 Vote: I do not like it

What I can say is: the problems will be interesting, and you will be very satisfied when you solve them :)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    What I can add is : When you solve them, you will be proud of yourself, as we are :)

    → Reply
»
11 years ago, # |
  Vote: I like it +39 Vote: I do not like it

You should mention about the unusual time in this contest!

→ Reply
»
11 years ago, # |
  Vote: I like it -25 Vote: I do not like it

i cant wait :3

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    You can wait She can wait He can wait We can wait They can wait

    → Reply
»
11 years ago, # |
  Vote: I like it -12 Vote: I do not like it

is the earlier time because of indonesian setter :P ?

i like this kind of time :D

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    The usual time is 10.30PM in Indonesia. That's too late for some of us :)

    → Reply
»
11 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Everything is unusual. Expecting an unusual increase in rating too :-)

→ Reply
»
11 years ago, # |
  Vote: I like it -13 Vote: I do not like it

The other problems have relatively short statements.

I love short statements.

→ Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Seems a cool contest! "This contest is stranger than usual"

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope that unusual solutions will uplift my rating unusual up. :)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

It's nice to see many up coming contests already scheduled, this is going to be a very interesting week!

→ Reply
»
11 years ago, # |
  Vote: I like it -16 Vote: I do not like it

It's just a test~~~~

Codeforces is a test for me, too~~~~

→ Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

What is the scoring method? If it's static scoring, what are the scores for each problem?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It will be static. We will release the scores some time before the contest.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

the contest will not be usual, en...., but I hope the contest will fit our taste, good luck & have high rating for everyone~

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Does 'mikemon' stand for 'Mike — monster'?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Not intentionally :)

    ...i thought "mi-ke-mon" sounds similar with "po-ke-mon" >:)

    → Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

A really unusual contest!!

→ Reply
»
11 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Is it possible that n can be equal 1 in Problem B div 2???

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

Unusual number of hacks!

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

I really like today's problems! But the number of hacks is a bit disappointing

→ Reply
»
11 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Just find the bug several seconds after the contest finished!!!!WTF

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Как решать D? конструкция 

>>>>>>.vvvvvv
.............
^^^^^..<<<<<<

получает только 85к

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it 
    >>>>.>.V
^.<.<<<<

    Может быть

    UPD: именно то, что написано ниже

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it 
      >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>v
^<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Думаю, что примерно так сработает, если <<<<<<< в конце около 50:

    >>>>>>>>>>>>>>v
^.<.<.<.<<<<<<<
^.<.<.<.<<<<<<<
^.<.<.<.<<<<<<<
^.<.<.<.<<<<<<<
^.<.<.<.<<<<<<<
^.<.<.<.<<<<<<<
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Вроде ряды ниже второго бесполезны тут

      → Reply
»
11 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Was it only me who noticed that 3 questions(!!) had something to do with matrices.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Wonderful contest! All problems are special and enjoyable to solve. It's really amazing to discover solutions!

→ Reply
»
11 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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....

→ Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

still slow…… sbcf…… I pressed "submit" when there were only 10 seconds left. After 20 seconds, Codeforces show me an error page...

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had MLE wtf?

http://codeforces.com/contest/330/submission/4121993

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    visited[i][j]=true; bad idea) Need in if() { visited[i][j]=true; }

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Yeah, it's MLE.

    → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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 :'(

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

very slow system test:|

I solve problem D div2 2 minute after end of the contest:(((((

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    You aren't the one, i only figured a bug in my code of D div2 after the contest ended..

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone point out the mistake in my solution http://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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Try this case:

    4 4
ETTT
0T9T
0TTT
000S
    → Reply
»
11 years ago, # |
  Vote: I like it +54 Vote: I do not like it

It looks like someone throws the testing machine into water...more and more slowly...

→ Reply
»
11 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +23 Vote: I do not like it

My solution for Div2-C is wrong and got AC.

Input:

4
.EEE
.EE.
EEEE
E...

Output:

1 1
4 4
2 4
4 2
4 3

While the minimum number of spells is 4.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it -13 Vote: I do not like it

    If I were you, I would not advertise it

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like 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.

    → Reply
»
11 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Examples were explained very good and pictures were really nice and clear. Thanks for the contest.

→ Reply
»
11 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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"?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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://codeforces.com/contest/329/submission/4123108

      But indeed, it's a really nice problem, thanks for your work. :)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Though I got -49, The contest was really good and encouraging for all, specially for beginner. :)

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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://codeforces.com/contest/330/submission/4116737 http://ideone.com/Wet1Tt

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You didn't initialize your visited array with falses

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But then how it passed 28 test cases?

      → Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The contest was really good . . . .

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how can I see why my submission to "Purification" (div1-A) problem gives compilation error?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok, I see, I forgot #include Anyway, how to use "custom test" to see that?

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mean I forgot "include cstdlib". I don't know how to use "custom test" to see that.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    If you click on compilation error you will see what's the cause of CE. Edited : Sorry! Didn't see your last comment.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It gives "exit was not declared in this scope" on my computer.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      That is not the reason. i is considered to be declared in the loop, so it is not a redeclaration.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In custom test you will see your compilation error on output section.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got the message "Error: Form elements must not have name or id of "submit"." I don't understand this message.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You just check the rows.You should check the columns too.

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Anyone can say me what is wrong with my submission in problem B here:

http://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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not possible

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You have connected nodes 2 and 65 that are not allowed to be connected.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    you connect 2 with 65.

    → Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Nice contest! Thanks!

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

[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?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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://codeforces.com/contest/329/submission/4122055

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it 
    Visual Studio Debug Mode:
Expression: map/set iterator not incrementable.

    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

    → Reply
»
11 years ago, # |
  Vote: I like it -22 Vote: I do not like it

today's contest was a great contest, OMG!! um loving codeforces. Coderforces why you are so lovely and sweet?? :)

→ Reply
»
11 years ago, # |
  Vote: I like it -24 Vote: I do not like it

codeforces i love you

→ Reply
»
11 years ago, # |
  Vote: I like it -24 Vote: I do not like it

codeforces is better than topcoder in all ways.. and its the best in the world

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I haven't see in the table submissions if they don't have AC. It's true only for div2 table viewing friends result

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, thanks for this contest! Now waiting for tutorial)

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Nice (Ad-hoc) Contest. Tutorials please . :)

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :(

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The answer is -1, while your output is not.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            (sigh) it's the answer and i know that but how , please can u explain a bit elaborately :(

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
              ← Rev. 2   Vote: I like it +26 Vote: I do not like it

              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:

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                oops , got a bad eye , sorrry

                → Reply