Codeforces: A. Rock-Paper-Scissors

The problem is from codeforces: http://www.codeforces.com/problemset/problem/173/A

This is the first problem that I submited in codeforces. It is a math problem that computes how many games for two players to win. This is a famous game that I guess it is not difficult to play. The R beats S, the S beats P etc. The sequences for two players to play are pre known. However, if you don’t optimise the algorithm and just use brute-force, it will result in a Time Limit Exceed (TLE), because the input n is very big (the number of game rounds). Instead of checking the game win or loss one by one, we might have to speed up the checking process by multiplication of as many game rounds as possible.

First, let’s take a look at the un-optimised algorithm will will exceed the time limit at the 11th test.

n = long(raw_input());

a = 0
b = 0

aa = raw_input();
bb = raw_input();

laa = len(aa)
lbb = len(bb)

i = 0
while i < n:
    j = i % laa
    k = i % lbb
    if (aa[j] == bb[k]):
        pass
    elif (aa[j] == 'R'):
        if (bb[k] == 'P'):
            a += 1
        else:
            b += 1
    elif (aa[j] == 'P'):
        if (bb[k] == 'R'):
            b += 1
        else:
            a += 1
    else: # S
        if (bb[k] == 'R'):
            a += 1
        else:
            b += 1
    i += 1

print a, " ", b

The above is the brute-force, that will take a long time to compute if the n is big, for example, the 11th is 554858576

The accepted python solution is given below which is not fully optimised yet, I believe.

n = int(raw_input());

aa = raw_input();
bb = raw_input();

laa = len(aa)
lbb = len(bb)

def gcd(x, y):
    if (y == 0):
        return x
    else:
        return gcd(y, x % y)

def lcm(x, y):
    return x / gcd(x, y) * y

m = lcm(laa, lbb)

def work(mm):
    i = 0
    a = 0
    b = 0
    while i < mm:
        j = i % laa
        k = i % lbb
        if (aa[j] == bb[k]):
            pass
        elif (aa[j] == 'R'):
            if (bb[k] == 'P'):
                a += 1
            else:
                b += 1
        elif (aa[j] == 'P'):
            if (bb[k] == 'R'):
                b += 1
            else:
                a += 1
        else: # S
            if (bb[k] == 'R'):
                a += 1
            else:
                b += 1
        i += 1
    return [a, b]

la = 0
lb = 0

mm = work(m)
a = mm[0]
b = mm[1]

aaa = 0
bbb = 0
k = n % m
if (k == 0):
    la = a * n / m
    lb = b * n / m
elif (n > m):
    mm = work(k)
    aaa = mm[0]
    bbb = mm[1]
    la = a * (n / m) + aaa
    lb = b * (n / m) + bbb
else:
    mm = work(n)
    aaa = mm[0]
    bbb = mm[1]
    la = aaa
    lb = bbb

print la, " ", lb

The GCD and LCM are computed for the lengths of the sequences for these two players. The function work takes one parameter which specifies the maximum common length for two sequences to check. This is the most time-consuming part of the algorithm, and therefore, the parameter passing in should be as small as possible. The goal is to minimise the brute-force check (work method). For example, if the total number of game rounds is a multiple of the LCD of these two sequences, we can multiple the result by the division of these two numbers.

The check method returns a list [a, b] which represents the number of games each player wins. The second case is that if the total number of game rounds cannot be perfectly divided by the LCD, we compute the remainder by brute-force, which calls the check method, and both parts are acceptable in a reasonable time scale because the parameters to give are not big.

If the n is smaller than the LCD, the n is can’t be big enough, because both m and k are smaller than 1000.

–EOF (The Ultimate Computing & Technology Blog) —