Hello again, it's been a time since I took part in a official SRM (the last one was SRM 559), and it was held in an atypical afternoon here in Brazil, I've just moved, and my home is a mess, I registered early and went to the kitchen, when I got back to computer, the round was about 5 seconds to start.
Starting to talk about the problems itself, I started opening 250, it was an really easy problem, different from the last rounds when the easy problems weren't so easy (solvable in a few minutes). The problem asked whether given 2 strings S and T if it's possible to mix to copies of string S so the string becomes equals to T, as the problems asks for only two copies of S, then it's solvable in O(N) being N the length of string S:
Until the submission for problem 250, the arena was working normally, even with the problem with the examples combo box which doesn't keep track of your last tested example and always get your first example tested by default (in the arena older versions it didn't happened). Then, opening the problem 550, I received the annoying message 'you can only see one problem at time' (I don't remember the message at all but it's something like this), than I had to log off to open the problem again, while coding, there were times when I had to wait more than a minute for a compilation, which made my submission way lower than it should be.
The problem starts talking about a game with two coins in a board, consisting of empty cells '.', obstacles '#' and, you 4 options of plays, move both coins for north, south, east or west, making a move you change both coins to a single direction, if any coin move to a cell with an obstacle, it simply doesn't move. The goal of the game is to move only one single coins out of the board. My solution was an Breadth-First-Search though the graph, using a state of the number of moves, and the location of both coins, simulating the goal of the game:
I'm yet thinking of a state for a dynamic programming solution for problem 1000, it'll be in a edit when available.
I ended up with an +109 rating and becoming green again, I'm pretty happy with good rating after a bad score record.
No comments:
Post a Comment