Solving topcoder srm407 with python

CorporationSalary

You can find the problem description here. Because the problem is little simple, so here change "If an employee has any subordinates, then his salary is equal to the sum of the salaries of his direct subordinates." as "If an employee has any subordinates, then his salary is equal to the sum of the salaries of his subordinates.".

In my first thinkint, I think this problem should be solved with graph algorithm.

The problem can be split into follow algorithm problems:

• Digraph Reachability and Transitive Closure (有向图的可达性及传递闭包)

To get one employee's all subordinates through the "employee graph".

• Topological Sorting (拓扑排序)

Because manager's salary is equal to the sum of his direct subordinates. So should compute subordinate's salary, then compute manager's salary.

If you want to learn above two alogrithms. You can read java algorithm, you can download it here.

Code for Digraph Reachability and Transitive Closure:

relations = ['NNYN','NNYN','NNNN','NYYN']
reachabilityArr = [['N' for a in range(len(relations[0]))] for b in range(len(relations))]
for i in range(len(relations)):
    for j in range(len(relations)):
        reachabilityArr[i][j] = relations[i][j]
for i in range(len(relations)):
    for j in range(len(relations)):
        for k in range(len(relations)):
            if relations[i][k]=='Y' and relations[k][j]=='Y':
                reachabilityArr[i][j] = 'Y'
print reachabilityArr

<style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style>

Code for Sorting

Because topological sorting algorithm is some complex, so here I use general sorting algorithm first, maybe I'll add topological sorting algorithm's implement later.

empArr = [a for a in range(len(relations))]
def my_cmp(x,y):
    if reachabilityArr[x][y] == 'Y':
        return 1
    else:
        return -1
empArr.sort(my_cmp)
print empArr

Code for calculating sum

retArr = [1 for a in range(len(relations))]
for n in empArr:
    ret = 0;
    for i in range(len(reachabilityArr)):
        if reachabilityArr[n][i] == 'Y':
            ret += retArr[i]
    retArr[n] = ret if ret>0 else 1
print retArr
sum = 0
for n in retArr:
    sum += n
print sum

CheapestRoute

You can find the problem description here.  My solution is similar to the analysis(see reference). There are some comments in the source code.

class Vertex:
    # current vertex's cell number
    cellNum = -1
    # number of telports I've used
    telportNum = -1
    def __init__(self,cellNum,telportNum):
        self.cellNum = cellNum
        self.telportNum = telportNum
class Weight:
    # total cost used to reach current "Vertex"
    cost = 0
    # number of moves used to reach current "Vertex"
    times = 0
    def __init__(self,cost,times):
        self.cost = cost
        self.times = times
def makeNewV(wArr,curW,cellPrice,stack,cellNum,telportNum,telportFlag,teleportPrice):
    newW = Weight(curW.cost+(telportNum-1+teleportPrice if telportFlag else cellPrice[cellNum]),curW.times+1)
    newV = Vertex(cellNum,telportNum)
    flag = False
    for i in range(newV.telportNum+1):        
        if wArr[newV.cellNum][i] and lessThan(wArr[newV.cellNum][i],newW):
            flag = True
            break
    if not flag:
        #print newV.cellNum, newV.telportNum
        stack.append(newV)
        wArr[newV.cellNum][newV.telportNum] = newW
    
def lessThan(left, right):
    return left.cost<=right.cost or (left.cost==right.cost and left.times<=right.times)
def my_cmp(left,right):
    if not left:
        return 1
    if not right:
        return -1
    if left.cost<right.cost or (left.cost==right.cost and left.times<right.times):
        return -1
    elif left.cost==right.cost and left.times==right.times:
        return 0
    else:
        return 1
def routePrice(cellPrice,enterCell,exitCell,teleportPrice):
    # wArr is an two dimension array which element is instance of Weight
    wArr = [[None for a in range(len(cellPrice))] for b in range(len(cellPrice))]
    wArr[0][0] = Weight(0,0)
    # stack contains Vertex info
    stack = []
    stack.append(Vertex(0,0))
    ind = 0
    # while there is vertex in stack, popup one vertex, scan adjacent cells to determine
    # which cell can be moved in. When find a cell that can be moved in, make an vertex for the cell,
    # calculate the weight for the vertex, push the vertex into stack.
    # At last, no new vertex will be pushed into the stack. All possibilities's weight information
    # will be stored into wArr. Then you can easily to find the minimum weight used to reach the last cell.
    while stack:
        v = stack.pop()        
        curW = wArr[v.cellNum][v.telportNum]
        if v.cellNum+1 < len(cellPrice) and cellPrice[v.cellNum+1]!=-1:
            makeNewV(wArr,curW,cellPrice,stack,v.cellNum+1,v.telportNum,False,teleportPrice)
        if v.cellNum-1 >= 0 and cellPrice[v.cellNum-1] !=-1:
            makeNewV(wArr,curW,cellPrice,stack,v.cellNum-1, v.telportNum,False,teleportPrice)
        for i in range(len(enterCell)):
            if enterCell[i]==v.cellNum:
                makeNewV(wArr,curW,cellPrice,stack,exitCell[i],v.telportNum+1,True,teleportPrice)
    wArr[len(cellPrice)-1].sort(my_cmp)
    ret = [0,0]
    ret[0] = wArr[len(cellPrice)-1][0].cost
    ret[1] = wArr[len(cellPrice)-1][0].times
    return ret
if __name__=="__main__":
    cellPrice = [1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1]
    enterCell = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46]
    exitCell = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48]
    teleportPrice = 1000
    print routePrice(cellPrice,enterCell,exitCell,teleportPrice)

<style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style>

 

Reference

Topcoder Analysis

Java Algorithm Graph shortest path algorithm

<style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style>