tag:blogger.com,1999:blog-29632375.post3570551695139866061..comments2015-07-26T10:48:18.008-07:00Comments on vexorian's blog: SRM 603: uncertaintyUnknownnoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-29632375.post-6440630556752401972014-01-07T10:41:29.558-08:002014-01-07T10:41:29.558-08:00Sorry, I forgot to mention. I was talking about Di...Sorry, I forgot to mention. I was talking about Div1(250)Sainoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-42142528626116402002014-01-07T10:38:48.732-08:002014-01-07T10:38:48.732-08:00Hi vexorian,
I was just trying to solve the proble...Hi vexorian,<br />I was just trying to solve the problem after the contest has ended and I was wondering why 5 is returned in the last case(4th) instead of 3, since if both players play optimally the {3,2,5} will become {3,5}(edge between 3,2 is removed) and in the 2nd turn becomes {3} since player 2 wants to minimize the result he selects the edge between and 5 and 3 and removes 5, so shouldn't 3 be returned?<br />Thanks.Sainoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-13522552078548104522014-01-06T12:13:12.269-08:002014-01-06T12:13:12.269-08:00Thanks got the mistakeThanks got the mistakedvdreddynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-68366897557309999732014-01-06T12:11:31.269-08:002014-01-06T12:11:31.269-08:00costs contain the same number of elements as the t...costs contain the same number of elements as the tree right? and hence n is costs.size()dvdreddynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-68714694437334351312014-01-06T12:10:11.265-08:002014-01-06T12:10:11.265-08:00I think n=costs.size() is ok, It passed sample te...I think n=costs.size() is ok, It passed sample tests for me by changing the edges loop to loop over n-1 edges instead of n.JOmegaCVnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-34541869123775211442014-01-06T12:05:16.755-08:002014-01-06T12:05:16.755-08:00n is equal to costs.size() + 1, not just costs.siz...n is equal to costs.size() + 1, not just costs.size()vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-24347085892895032402014-01-06T12:01:05.883-08:002014-01-06T12:01:05.883-08:00Hi vexorian, my code for Div 1 250has the same log...Hi vexorian, my code for Div 1 250has the same logic as yours and code is also very similar but mine failed system tests<br />can you please suggest where it is wrong<br /><br />http://community.topcoder.com/stat?c=problem_solution&rm=320049&rd=15836&pm=12946&cr=22889193<br /><br />Thank youdvdreddynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-90825533617392943832014-01-06T10:50:31.687-08:002014-01-06T10:50:31.687-08:00I thought of it this way: Player 1 knows that if h...I thought of it this way: Player 1 knows that if he wants to guarantee a score greater than the max leaf, he has to remove all leaves as ending options for player 2. So the the proof I assumed was: it is impossible to remove a single edge in a tree, keep one subtree, and not have an original leaf exist in the subtree. Not sure how useful that fact would be in the future.<br /><br />Also, for a tree with two nodes, is it correct to say they are both leaves?JOmegaCVnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-76904273640078468522014-01-06T10:44:56.066-08:002014-01-06T10:44:56.066-08:00This is useful because I have to write the editori...This is useful because I have to write the editorial and thus prove this.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-51084520371540522532014-01-06T09:48:25.923-08:002014-01-06T09:48:25.923-08:00I don't whether the way I proved my 250 is cor...I don't whether the way I proved my 250 is correct or not but here it is. The 2nd player always has the option to cut one of the leaves with the minimum cost and choose to continue with it which ends the game. Since the two players are playing optimally so if the 2nd player knows that somehow the 1st player can make a profit larger than one of the leaves then he can end the came in his turn. So the upper bound of the cost the first player can have is the largest cost of all leaves .So the 1st player ends the game in the first turn cutting the edge connecting the leaf with the maximum cost.Muhammad Bassemnoreply@blogger.com