tag:blogger.com,1999:blog-1953325079793449971.post8899187886938726921..comments2024-06-12T05:08:36.036+02:00Comments on Algorithms Weekly by Petr Mitrichev: World Finals 2012: live coveragePetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger34125tag:blogger.com,1999:blog-1953325079793449971.post-37429159483629818082013-05-10T11:36:28.502+02:002013-05-10T11:36:28.502+02:00I think I got your idea now, just there are some c...I think I got your idea now, just there are some cases in your solution that are worth mentioning: for example how you treat separated components.Jacob Dlougachhttp://www.facebook.com/jacob.dlougachnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-78080558382912209772013-05-10T11:36:25.450+02:002013-05-10T11:36:25.450+02:00Hi!I m competing on TopCoder and I would like to i...Hi!I m competing on TopCoder and I would like to improve my performance.Could you please upload any training camp videos that you have conducted or attended on torrent?<br />That would be so helpful.<br />A collection of other materials would be great too.<br />Thank you:)Aravinnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-23854161131893825272013-05-10T11:36:24.469+02:002013-05-10T11:36:24.469+02:00Thanks! (Zhongshan was in the official scoreboard)...Thanks! (Zhongshan was in the official scoreboard). I will keep this in mind when posting future comments.Petrhttp://petr-mitrichev.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-81608175511131038542013-05-10T11:36:23.496+02:002013-05-10T11:36:23.496+02:00The problem here is that "cost" is not f...The problem here is that "cost" is not for using an edge, but for each unit of flow through the edge. So the cost of your flow will always be n.Petrhttp://petr-mitrichev.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-6937597773353343882013-05-10T11:36:22.464+02:002013-05-10T11:36:22.464+02:00I understand your solution, but I don't unders...I understand your solution, but I don't understand what's wrong with mine. Why can't I do a DP like I described that minimizes first the number of key disconnections, and then the number of ring disconnections?Petrhttp://petr-mitrichev.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-7967231076194701712013-05-10T11:36:22.208+02:002013-05-10T11:36:22.208+02:00I think you got F problem statement incorrectly. T...I think you got F problem statement incorrectly. The first priority was to minimize number of operations with keys, and the second was number of operations with rings. Thus the correct solution would rather look like this: let's choose 2 vertices where we'd put all detached red and blue keys respectively, then we'll notice that all rings will fall into 3 categories: 'red' rings, 'blue' rings and 'either red or blue'. Then the problem would be to determine minimal number of breaking links between rings so that no red and blue rings are in the same connectivity component. This can be done in different ways (including dynamic programming or min-cut).Jacob Dlougachhttp://www.facebook.com/jacob.dlougachnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-72062487167853760332013-05-10T11:36:20.435+02:002013-05-10T11:36:20.435+02:00Hi, abut the problem E, I know my approach is wron...Hi, abut the problem E, I know my approach is wrong, but I cant prove it, can anyone help me? Here it is:<br /><br />Build a bipartite graph, left side are the nodes 'out' and right side are the nodes 'in', so I link all the 'out' nodes to the 'in' nodes where the node on the left has a dominance over the one on the right. All the nodes on the left are linked to the source and all to the left are linked to the sink, and every node 'out' is linked to its 'in'. The link from the source to the 'out' nodes has infinity capacity and 1 cost. All other links has 1 capacity and 0 cost. The minimum answer would be the cost of the mcmf from source to sink.. that is probably wrong, but could anyone point out where?<br /><br />Thanks!Guestnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-74267270780952316152013-05-10T11:36:13.446+02:002013-05-10T11:36:13.446+02:00 I expected under 10. :( I expected under 10. :(Manishnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-85964187419457858952013-05-10T11:36:12.461+02:002013-05-10T11:36:12.461+02:00Is it Shilp Gupta?Is it Shilp Gupta?Mayanknoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-49960054681571565422013-05-10T11:36:11.445+02:002013-05-10T11:36:11.445+02:00 They stood 20th with 5 problems :) They stood 20th with 5 problems :)Sidharth Guptanoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-60498964461227395662013-05-10T11:36:10.433+02:002013-05-10T11:36:10.433+02:00IIT DELHI - #20 ! Great achivement.IIT DELHI - #20 ! Great achivement.Mayank!noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-26305756762212535892013-05-10T11:36:09.412+02:002013-05-10T11:36:09.412+02:00Hey! How did Indian Institute of Technology - Delh...Hey! How did Indian Institute of Technology - Delhi do? They are certainly the best performing Indian team to date!Shilpnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-70111410481360678762013-05-10T11:36:08.417+02:002013-05-10T11:36:08.417+02:00hi Petr can youo tell what was final rank of this ...hi Petr can youo tell what was final rank of this team Indian Institute of Technology - Delhi: rudradevbasak, naiveAlgorist, nikhil-garg Guestnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-60071708703200079032013-05-10T11:36:07.419+02:002013-05-10T11:36:07.419+02:00What is the cause of rejudge?What is the cause of rejudge?Alexander Mashrabovnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-36753428893667027562013-05-10T11:36:06.405+02:002013-05-10T11:36:06.405+02:00Unrated round? : )Unrated round? : )Fefer Ivannoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-86448347567796887472013-05-10T11:36:05.408+02:002013-05-10T11:36:05.408+02:00shit(shit(Kroknoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-8763668751157383372013-05-10T11:36:04.436+02:002013-05-10T11:36:04.436+02:00SPbSU?
NNSU?SPbSU?<br /><br />NNSU?Kroknoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-14910016575135780532013-05-10T11:36:03.432+02:002013-05-10T11:36:03.432+02:00And what about MIPT?And what about MIPT?Alexander Mashrabovnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-10962624858487175592013-05-10T11:36:02.423+02:002013-05-10T11:36:02.423+02:00MIPT submitsMIPT submitsGuestnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-19681720482154601162013-05-10T11:36:01.428+02:002013-05-10T11:36:01.428+02:00what about last Warsaw's submit?what about last Warsaw's submit?Guestnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-78299093303351708682013-05-10T11:36:00.403+02:002013-05-10T11:36:00.403+02:00I don't know what's happening to ITMO eith...I don't know what's happening to ITMO either, but I wouldn't worry if it stayed that way :)Onufrynoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-59635763177211988172013-05-10T11:35:59.396+02:002013-05-10T11:35:59.396+02:00who are the members of the team in the first place...who are the members of the team in the first place?Mohamed Gabernoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-17720432590699911572013-05-10T11:35:58.427+02:002013-05-10T11:35:58.427+02:00Doesn't work. E.g., in
11 6 6 6
9 9 9
your str...Doesn't work. E.g., in<br />11 6 6 6<br />9 9 9<br />your strategy says to beat (which leads to a loss); while merging wins.Onufrynoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-46449443151191250832013-05-10T11:35:57.420+02:002013-05-10T11:35:57.420+02:00Sorted in decreasing order of costs.Sorted in decreasing order of costs.Kshitijnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-31898558385192069052013-05-10T11:35:56.388+02:002013-05-10T11:35:56.388+02:00How about this? Sort the subsidiaries by their cos...How about this? Sort the subsidiaries by their cost. Now let's say company x has the current move(call the other company as y). Also, let's say the subsidiaries of x are x1, x2, x3, ... , xN and subsidiaries of y are y1, y2, y3, ... , yM (both sorted by costs). Now there are 2 cases :<br />Case 1 : x1 < y1 . x1 can't acquire y1, hence the only move that makes sense is x1 merging with x2.<br />Case 2 : x1 > y1<br /> sub-case 1 : x1 + x2 > y1 + y2. Merge x1 and x2. Whatever merge happen in y, or if y takes over some element of x, x1 + x2 will still be able to make a hostile acquisition<br /> sub-case 2 : x1 + x2 < y1 + y2. Take over y1 using x1. <br />I don't have a proof why this should work, but it seems okay. Any counterexamples?Kshitijnoreply@blogger.com