It was a fine match. Actually the first SRM problem set by tourist. Well, it is also the sixth match of 10 matches in my python challenge. Having finished 60% of it, I have a new perspective. At this moment, I think that when the challenge ends, in SRM 621, I might actually still use python. At least in problems where I am sure it can shine.
Div1 250 - The one with alarm clocks
Match starts, open the easy problem in division 1. Meet a simulation problem. problem statement. In this problem, you start with a value `S` at time 0. Every second, S is increased by `D`, then the alarms scheduled to run at that second ring. Each alarm that rings will decrease `S` by some special value specific to the alarm. We have the alarms periods (Between 1 and 10), first ring time (between 1 and its period) and volume (the value by which `S` is decreased). Each alarm rings at times: start, start + period, start + 2*period, etc. There are up to 50 alarms. When `S` becomes 0 or less , you wake up immediately. Find the maximum starting value of `S` such that you will eventually wake up. If no matter what value of `S` you pick, you wake up eventually, return -1.
We can combine the cycles together by taking the LCM of all their periods. Because the periods are not more than 10, the combined cycle length is not more than 2520 = 2*2*2*3*3*5*7. You can answer the question by just simulating the first LCM seconds. For more info, read the editorial.
This is a problem that does okay in python. Python can really help keep the code small in comparison to the other languages. I took some advantage of it during the match and got a good score. But in reality, my original code could be improved in many ways. For example, did you know there is a builtin GCD function?.
from fractions import gcd
def lcm(x,y):
return x * (y / gcd(x,y))
class WakingUp:
def maxSleepiness(self, period, start, volume, D):
sleep = 0
n = 0
for i in xrange(1, reduce(lcm, period) +1 ): # LCM is at most 2520
sleep += D
for (p,s,v) in zip(period, start, volume):
if (i - s) % p == 0:
sleep -= v
n = min(n, sleep)
return -1 if (sleep < 0) else -n
Many details, for example using reduce to get the lcm of all the periods. The zip function to iterate through the alarms without having to do much indexing...
A subtle one: To check if an alarm should ring at time i, we use (i - s) % p == 0. In c++ you would need : i % p == s % p. The reason is that python's % operator is not broken for negative numbers. Very handy.
For a comparison, try the fastest c++ submission. The algorithm is exactly the same, but you can see that it has to "weigh" more, it has many sources of complications. Having to use a loop to calculate the LCM of all periods, or using the for j = 0; j < n; j++ to get the special alarms.
Div1 500
After finishing div1 250, I moved to the next problem. It just seemed ... impossible. It turns out that it is just a mathy problem. I am not very good with them.
I skipped this problem during the match. Later I , of course, had to learn it to solve the editorial. Once I understood I implemented a python solution. It actually took a while to code, and I am not sure if it is really using all of python's potential. You can read the code at the editorial.
Div1 1000
I explained this problem in detail before: here
Just like there are topcoder problems that are not my style at all. There are some which are really my style. This was the rare div1 hard I actually solved the instant after reading it. Because I just like grid-bitmasks dp problems a lot.
There is a world of difference between having a correct idea for a problem and actually implementing it. I noticed the `O(n^5)` idea , while correct and possibly able to pass in c++, would fail utterly to run in time in python.
So let's dissect why the following python solution (closest I got to good performance) have much more issues passing than the c++ equivalent you can see in the editorial I linked.
sys.setrecursionlimit(10**6)
class ThreeLLogo:
def countWays(self, grid):
n = len(grid)
m = len(grid[0])
def allValidMasks():
yield 0
for i in xrange(m-1):
yield (1 << i)
for j in xrange(i+1, m-1):
yield (1 << i) | (1 << j)
for k in xrange(j+1, m-1):
yield (1 << i) | (1 << j) | (1 << k)
MAX_MASKS = 4090
validMasks = [0] * MAX_MASKS
getMaskId = dict()
t = 0
for mask in allValidMasks():
validMasks[t] = mask
getMaskId[mask] = t
t += 1
@MemoizedFunction( [n+1,m+1,4,MAX_MASKS,2] )
def f(x,y, need, maskid, horz):
mask = validMasks[maskid]
if x == n:
# base case
return 1 if ( (mask == 0) and (need == 0) ) else 0
elif y == m:
return 0 if (horz == 1) else f(x + 1,0, need, maskid, 0)
elif (1<<y) & mask:
if (horz == 1) or (grid[x][y] == '#'):
#must continue the left "L" shape, but also must continue the above one
return 0
else:
# 1) Finish the L shape above.
nmask = mask ^ (1 << y)
res = f(x,y+1, need, getMaskId[nmask], 1)
# 2) Continue the L shape vertically
res += f(x,y+1, need, maskid, 0)
return res
elif horz == 1:
return 0 if (grid[x][y] == '#') else sum(f(x,y+1, need, maskid, s) for s in (0,1))
else:
# 1) Do nothing
res = f(x,y+1, need, maskid, 0)
# 2) Do something, Create a new L shape
if (grid[x][y] == '.') and (need > 0) and (y < m - 1) :
nmask = mask | (1 << y)
res += f(x,y+1, need - 1, getMaskId[nmask], 0)
return res
return f(0,0, 3, 0, 0)
# decorator that adds memoization to a function using a list of bounds
# ej: @MemoizedFunction( [10, 10, 10] )
def MemoizedFunction(bounds):
def deco(f):
mem = [-1] * reduce( lambda a,b: a*b, bounds )
def g(*args):
p = 1
k = 0
for i in xrange(len(args)):
(a,b) = (args[i], bounds[i])
k = a * p + k
p = p * b
if mem[k] == -1:
mem[k] = f(*args)
return mem[k]
return g
return deco
Well, things that were already mentioned, the default recursion limit is a bit large. Python is just slower than c++, mostly because its code does much more than c++. It has this dynamism that makes it so powerful but also slower. In an i5 computer, it takes around 10 seconds, while the goal is 3 seconds in TC's servers... Another large issue was the memory usage. Even with the clever decorator that makes all of the dp table contents exist within a single list, we would need around 768 MB to make all fit in memory.
During the match, I began to code a solution to the problem anyway. Because of the python challenge, I couldn't use c++. I still wanted to solve it because it was fun and also, if the python solution works in small inputs, it would mean I at least understood the problem, which would be helpful later and it would be a moral victory :). So I tried to do it, but I had bugs. Story of my life, I couldn't really finish the code until after I spent a couple of days working in the rest of the editorial..
My first code (once fixed) was actually more compact and slow than the one above:
import sys
sys.setrecursionlimit(10**6)
class ThreeLLogo:
def countWays(self, grid):
n = len(grid)
m = len(grid[0])
@MemoizedFunction
def f(x,y, need, arms, horz):
if x == n:
# base case
return 1 if ( (arms == () ) and (need == 0) ) else 0
elif y == m:
return 0 if (horz == 2) else f(x + 1,0, need, arms, 0)
elif y in arms:
if (horz == 2) or (grid[x][y] == '#'):
#must continue the left "L" shape, but also must continue the above one
return 0
else:
# 1) Finish the L shape above.
narms = tuple( z for z in arms if z != y )
res = f(x,y+1, need, narms, 2)
# 2) Continue the L shape vertically
res += f(x,y+1, need, arms, 0)
return res
elif horz == 2:
return 0 if (grid[x][y] == '#') else f(x,y+1, need, arms, 1)
else:
# 1) Do nothing
res = f(x,y+1, need, arms, 0)
# 2) Do something
if (grid[x][y] == '.'):
# 2.1) Create a new L shape
if need > 0:
narms = tuple( sorted(arms + (y,)) )
res += f(x,y+1, need - 1, narms, 0)
# 2.2) Continue the left L shape:
if horz == 1:
res += f(x,y+1, need, arms, 1)
return res
return f(0,0, 3, (), 0)
However, this helped me discover something cool. After writing this code, it was easy to optimize it and later translate to c++. Behaving as a human python-c++ compiler. When the python challenge ends, I might try this more often. Code a prototype in python making sure the logic works, then translate to c++ :).
The other ones
Then I wrote the editorial. Besides of the div1 hard that appears to be impossible in python, the remaining problems work just fine.
A notable example: This 3-liner solution for div2 500 which could be made into a one-liner.
class ColorfulCoinsEasy:
def isPossible(self, values):
limits = sorted([ (values[i+1]/values[i]) for i in range(len(values) -1) ]) ## get list of values[i+1] / values[i], sort it
condition = all(i+1 < limi for (i,limi) in enumerate(limits)) ## Required: for each i: i + 1 < limits[i].
return "Possible" if condition else "Impossible"
No comments :
Post a Comment