设为首页 收藏本站
云服务器等爆品抢先购,低至4.2元/月
查看: 335|回复: 0

[经验分享] Solving topcoder srm407 with python

[复制链接]
发表于 2017-4-30 12:10:24 | 显示全部楼层 |阅读模式
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[j] = relations[j]
for i in range(len(relations)):
for j in range(len(relations)):
for k in range(len(relations)):
if relations[k]=='Y' and relations[k][j]=='Y':
reachabilityArr[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] == 'Y':
ret += retArr
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] and lessThan(wArr[newV.cellNum],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==v.cellNum:
makeNewV(wArr,curW,cellPrice,stack,exitCell,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>

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址:https://www.yunweiku.com/thread-371187-1-1.html 上篇帖子: python 快速排序 下篇帖子: Python之urllib使用
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群,最新一手资源尽在官方微信交流群!快快加入我们吧...

扫描微信二维码查看详情

客服E-mail:kefu@iyunv.com 客服QQ:1061981298


QQ群⑦:运维网交流群⑦ QQ群⑧:运维网交流群⑧ k8s群:运维网kubernetes交流群


提醒:禁止发布任何违反国家法律、法规的言论与图片等内容;本站内容均来自个人观点与网络等信息,非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来,其版权均归原作者及其网站所有,我们尊重他人的合法权益,如有内容侵犯您的合法权益,请及时与我们联系进行核实删除!



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表