Hi all,
I suggest another approach for solving problem D of round 2. My approach does
not need any dynamic programming, but I do use combinatorial methods instead.
And also I do still need to enumerate in order to find solutions to some linear
equation.
Unfortunately for me, I thought about it only after the round ended, so I did
not pass, but I did check this solution afterwards.
I have the same analysis as the GCJ analysis, up to the point of "Now we can
use dynamic programming to assign…".
Specifically we note that there are 5 types of rows:
Type O:
3...
3...
Type I.
2...
Type II.
122...
122...
Type III.
222112...
112222...
Type IV.
2212...
1212...
1222...
As noted in the analysis, type O alternates with types I, II, III, IV. Types
II, III, IV are valid only if C is divisible by 3, 6, 4 respectively.
After type I come two rows of 3, so this occupies 3 rows. In the same way Type
II occupies 4 rows, etc. We should only note that at the bottom/top there might
be 2 consecutive rows of 3, or not.
Therefore, we can find quickly the possibilities of HOW MANY appearances we
have of each of the types I, II, III, IV. It is easy to verify if a count is
valid by a simple linear equation (to which I found all solutions by simple
enumeration).
After we have a possibility of the count of each types, we then have to ORDER
the types – which is above which. This can be quickly computed by the
multinomial:
Multinomial(x+y+z+w, (x, y, z, w)) = (x+y+z+w)! / (x!)*(y!)*(z!)*(w!)
Finally, for each such solution we have to multiply it by the number of
possible PHASES between the rows.
Suppose we have only rows of type I (and obviously type O) - then all phases
look the same.
Suppose we have only rows of type II (and obviously type O, and maybe even I) -
then the number of different phases for type II rows are 3**(n-1) (** is
exponent, n is the number of rows of type II).
Suppose we have only rows of type III (and obviously type O, and maybe even I)
- then the number of different phases for type III rows are 6**(m-1) (** is
exponent, m is the number of rows of type III).
Suppose we have rows of types II and III (but not IV) – then the number of
different phases will be 3**(n-1) for type II, and 6**(m-1) for type III but
we also have to multiply it by 3 for the phase between the two types. So we get
as the number of possible phases 3 * 3**(n-1) * 6**(m-1)
Etc etc….
The code actually does not seem to be complicated, and it can be described more
shortly then the explanation above.
I attach my python code which seems to work. The only difference is that I
numbered types II, III, IV differently than the GCJ analysis, so the numbering
of the variables t2, t3, t4 is not consistent with the order of the types as
described above.
All counts are computed modulo 1000000007 as requested in the problem.
@memoize_it
def factorial (n):
s = 1
for i in range(1,n+1):
s *= i
return s
@memoize_it
def multinomial (*args):
s = 1
for i in args:
s *= factorial(i)
return factorial (sum(args)) // s
MODULO = 1000000007
def compute_result (R, C):
cnt = 0
range_t1 = list(range(35))
if C % 6 == 0:
range_t2 = list(range(35))
else:
range_t2 = [0]
if C % 4 == 0:
range_t3 = list(range(35))
else:
range_t3 = [0]
if C % 3 == 0:
range_t4 = list(range(35))
else:
range_t4 = [0]
for t1 in range_t1:
for t2 in range_t2:
for t3 in range_t3:
for t4 in range_t4:
# The case of rows of 3 at the top, no 3's at the bottom
if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R:
cnt += calc2 (t1, t2, t3, t4)
# The case of rows of 3 at the bottom, no 3's at the top
if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R: # I know it's
twice of the same above
cnt += calc2 (t1, t2, t3, t4)
# The case of rows of 3 at the top and at the bottom
if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R-2:
cnt += calc2 (t1, t2, t3, t4)
# The case of no 3's at the bottom row, neither at the top
row
if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R+2:
cnt += calc2 (t1, t2, t3, t4)
return cnt % MODULO
def calc2 (t1, t2, t3, t4):
res = multinomial (t1, t2, t3, t4)
res %= MODULO
if t2:
res *= pow(6, t2-1, MODULO)
res %= MODULO
if t3:
res *= pow(4, t3-1, MODULO)
res %= MODULO
if t4:
res *= pow(3, t4-1, MODULO)
res %= MODULO
if t2 and t4:
res *= 3
if t2 and t3:
res *= 2
return res % MODULO
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/af620140-c7a9-4dab-9313-ed45a59d26ba%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
