chrome's blog

Topcoder Single Round Match 655
By chrome, 11 years ago, translation, In English

Ciao!

Today at 18:00 MSK will be held Topcoder SRM 655.

Let's discuss problems after contest.

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

»
11 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

Starts in 4.5 hours!

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

Fuck. I am late again T.T

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

Editorial of Div1-Easy and Div1-Hard: http://mirror.codeforces.com/blog/entry/17341

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

250 was a really funny problem for me... At first I thought that the intended solution is to check whether there is a monochromatic k*k square and whether there is a monochromatic segment of length k in each row and in each column. But I couldn't prove it's correct and after some time I found a counterexample. So I left the 250 be and moved to the other two problems.

In the challenge phase I used my counterexample to challenge two solutions and I think that I could challenge ~4 more, if I was fast enough (it's quite hard to challenge when in same room with tourist). So, at the end, I would gain more than 250 points for 250, without even solving it :)

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

    What was the counterexample for your initial idea?

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

    My room had only 5 wrong 250s, 3 of which used a greedy "paint the square with whatever color it is" algorithm and 2 used this row checking idea, so there were only 100 points for the picking with that case :(

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

How to solve div2 250 pt?

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

    My approach —
    There are only 2 possible patterns for the board, either it starts with 'W' or 'B'. After that we can fill the board according to the question.
    So there we obtain 2 possible patterns, say C and D.
    Now loop through the given board and wherever the character is not '?', compare it with C(pattern).

    if(board[i][j] != '?' && board[i][j] != C[i][j])

    If the condition is true, means board is not equal to pattern C.
    SImilarly do for pattern D.
    If both C and D does not match then answer is "Impossible" otherwise "Possible".

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

    I ran into a bit of trouble too while trying to figure out the logic, so I ran a bfs starting from the first square on the board that isn't a '?' (that is, starting from the first coloured square you come across on the board).

    Suppose your current starting square is white, check the 4 adjacent squares. If any of them is the same colour, return -1. If it is a question mark, colour it the opposite colour(black). Then push all four into the queue, keeping track of the visited squares.

    → Reply