chrome's blog

Topcoder Single Round Match 655
By chrome, 9 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

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

Starts in 4.5 hours!

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

    No, is starts in ~70 minutes!

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

    People at codeforces are amazing, aren't they?

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

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

        Since the link to your pic starts with googleusercontent.com, it looks like you're linking to Google user content (thanks, Captain Obvious). Trying to view it directly tells me I don't have permissions to view it.

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

          My bad, tried to upload to Google Drive for reusability lol

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

        Can't see the picture.

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

    I really don't understand the reason for so many down votes. I only commented to bring this post closer to the top so more could notice it and suddenly -18, WTF?

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

      Because CF voting system.

      It needs to be done in the opposite way to Disqus: people who downvoted need to be public.

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

      dont need to get angry, go eat a banana and calm down

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

Fuck. I am late again T.T

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

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

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

    What was the counterexample for your initial idea?

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

      k = 2

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

      A more symmetrical example:

      BBBWB
WWWWB
BWWWB
BWWWW
BWBBB

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

How to solve div2 250 pt?

→ Reply
  • »
    »
    9 years ago, # ^ |
      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
  • »
    »
    9 years ago, # ^ |
      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