This was the second SRM in which I used python exclusively, I think I did just okay.

## Div1 250: The one with copy paste

You have one character, you want to reach **smilies** characters (**smilies** is between 2 and 1000). You have three operations: Delete one character. Copy *all* current characters to the clipboard and paste the characters from the clipboard (without replacing the current ones). What is the minimum number of steps?

Define state `(s,c)`, where `s` is the current number of characters and `c` the number of characters in clipboard. Then a delete operation is to move to `(s-1,c)`, a copy operation is to move to `(s,s)` and a paste operation is to move to `(s+c,c)`. The rest is just to code a Breadth-first-search (Or you know, A Dijkstra where all edge weights are 1), because we want to find the minimum-length path from `(1,0)` to any `("smilies",c)` (We start at `(1,0)` because there is one character and the clipboard is empty).

So I just needed to code BFS in python. I had a bit of difficulty because I forgot how to do queues in python... turns out you just do .pop(0) to remove and return the front element.

class EmoticonsDiv1: def printSmiles(self, smiles): v = [ (1,0) ] dist = dict() dist[(1,0)] = 0 def neighbors(s,c): if s > 0: yield (s-1, c) #del yield (s,s) #copy yield (s+c,c) #paste # BFS while len(v) > 0: (s,c) = v.pop(0) d = dist[(s,c)] if s == smiles: return d for x in neighbors(s,c): if x not in dist: dist[x] = d + 1 v.append(x)

Why to do a BFS and not just a dynamic programming? The recurrence relation is cyclic. So, really, don't try to do dynamic programming here.

Note the cute usage of yield.

## Later

Tried div1 medium but seems difficult. Decided to skip the rest of this SRM and finish the editorial for SRM 611.

I think python really helped me in this problem. I was able to quickly modify my tester to quickly test for all possible values of smilies, so I am quite sure I passed. I had a delay remembering about pop(0), but I also coded very quickly thanks to python, I think I would have taken a bit more time in c++-

## No comments :

Post a Comment