TopCoder SRM 567 - Div I Lvl 1

The Square Root Dilemma
-----------------------------------
=> (A*B) is the a perfect square

For a given value of (A), we try to find all possible values of B which make A*B a perfect square.

A = OA * EA,  where EA is the perfect square factor of A and OA is the other factor

So, (A*B) is perfect square when B can be factored as OA*(a perfect square).


def srm567(a,b):
    ctr = 0
    for i in range(1,a+1):
        j = 2
        s = 1
        while (j*j)<= i:
            if i%(j*j) == 0:
                s = j*j
            j += 1

        r = i/s
        #print "i,s:",i,s
        y = 1
        while (y*y*r)<=b:
            ctr+= 1
            y += 1
    return ctr

TopCoder SRM 569 - Div I Lvl 1

We need to be able to find the Operation of each bit, i.e. whether it is OR, AND , XOR.

If you see the truth table for these operations:

A	B	OR	AND	XOR
0	0	0	0	0
0	1	1	0	1
1	0	1	0	1
1	1	1	1	0

You see that the first combination where both bits A/B are '0' all the results are zero, so this combination of bits doesn't help us identify the operation. => If we have bits 0,1,1 available to be inputted at a bit position we can identify the operation.

So, now the problem reduces to finding the no. of plates to be added so that there is a combination of 011 bits available at each position.


 def srm569(plates):
    more_plates_needed = 0
    M = len(plates[0])
    for i in range(0,M):
        bits_needed = ['0','1','1']
        for j in range(0,len(plates)):
            if plates[j][i] in bits_needed:
                bits_needed.remove(plates[j][i])
        more_plates_needed = max(more_plates_needed,len(bits_needed))
    return more_plates_needed


Examples:
=======

srm569(["01010101",
 "10101010"])
Out[34]: 1

srm569(["10010101011",
 "00010101001",
 "00100010111",
 "00101010101",
 "01010111101"])
Out[35]: 1

srm569(["1101001011010",
 "0010000010101",
 "1010101011110",
 "1101010100111",
 "1011111110111"])
Out[36]: 0

TopCoder SRM 571 - Div I Lvl 1

http://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491
The following code prints the first 50 lexicographically sorted values of the records names:


class Test:
def __init__(self):
self.res = []
def f(self,n,x):
if x >n:
return
if len(self.res) < 50:
self.res.append(x)
#print x
else:
return

self.f(n,x*10)
rem = x%10
if rem != 9:
self.f(n,x+1)
def getRes(self,n,x):
self.f(n,x)
print self.res

Sample values printed from the program:
Test().getRes(1010,1)


1
10
100
1000
10000<
1001
10010<
1002
1003
:
1009
101
1010

TopCoder SRM 572 - Div I Lvl 1

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15492


def myfunc(s,k):
    res = 0
    incr = len(s)-k
    for i in range(0,incr):
        # find the first set of alphabets which don't match
        j = i
        t = {}
        ctr = 0
        #print "i:",str(i)
        while j<len(s):
            #print "j:",str(j)
            if s[j] in t:
                t[s[j]] += 1
            else:
                t[s[j]] = 1
            j += incr
            ctr += 1
        mx = max(t.values())
        res += ctr - mx
   
    return res

TopCoder SRM 573 - Div I Lvl 1

Div II Lvl 2 problem: easier version solution
http://community.topcoder.com/stat?c=problem_statement&pm=12471&rd=15493


def myfunc(s):
    our_strength = sum(s[0:3])- min(s[0:3])
    rst = s[3:]
    #print our_strength
    if len(rst) == 0:
        return 1
    # find the rank of our team, start with rank 1 and increment it as you find better ranks
    res = 1
    rst.sort()
    #print rst
    found = True
    while found == True:
        # get the max element
        max = rst[-1]
        rst.remove(max)
        # find the min element which is greater than our_rank
        found = False
        for i in rst:
            if i+max > our_strength:
                rst.remove(i)
                found = True
                res += 1
                break
    return res

http://apps.topcoder.com/wiki/display/tc/SRM+573

TopCoder SRM 575 - DIV 1 Level 1

http://community.topcoder.com/stat?c=problem_statement&pm=12496&rd=15495

The solution for the smaller problem:


def myfunc(n):
    f = [0] *(n+1)
    for i in range(2,n+1):
        for j in range(2,i):
            if(i%j==0 and f[i-j]==0):
                f[i] =1
    print [ (i,f[i]) for i in range(0,len(f))]

The solution for the bigger problem involves getting a pattern from the above solution.
http://apps.topcoder.com/wiki/display/tc/SRM+575