tag:blogger.com,1999:blog-786333285568106173.post2792259972627707404..comments2017-05-04T06:01:24.829-04:00Comments on WebDiarios de Motocicleta: International Olympiad, Day 2Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-786333285568106173.post-55521795220142317812011-07-29T08:20:24.761-04:002011-07-29T08:20:24.761-04:00Will the following algorithm work for Crocodile su...Will the following algorithm work for Crocodile subtask 1 [graph is tree , leaves are exit nodes , every other node has at least 3 neighbouring nodes]<br /><br />f(node n){<br /> if(n is leave)<br /> return 0<br /> for every node k such that k is child of n<br /> find p_k = f(k) + length_of_edge_connecting n and k<br /><br />f returns the second smallest element among all p_k <br />}<br />answer B = f(0)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-85048218179263588572011-07-29T07:07:04.355-04:002011-07-29T07:07:04.355-04:00That's funny, I thought you were the one behin...That's funny, I thought you were the one behind parrots...Abelhttp://www.cs.uwaterloo.ca/~amolinap/noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-34475194774902031882011-07-29T02:57:09.678-04:002011-07-29T02:57:09.678-04:00will this algorithm work for the first subtask of ...will this algorithm work for the first subtask of task crocodile ? <br /><br />dynamic programming<br /><br />f(node n){<br /> if(n is a leave)<br /> return 0<br /> <br />for every node k such that k is child of n<br />find p_k = length_of_edge_connecting n and k + f(k)<br /><br />dp[node] = the secod smallest element among all p_k<br />}<br />answer B = dp[0]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-2483083805138788272011-07-29T01:58:19.243-04:002011-07-29T01:58:19.243-04:00Wouldn't the elephants step on the cameras? Y...Wouldn't the elephants step on the cameras? You should have to replace them after an elephant-crossing, and minimize the total number of cameras used.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-85601913973002326842011-07-29T00:05:37.501-04:002011-07-29T00:05:37.501-04:00@goodwind89: I think you have the basic idea but y...@goodwind89: I think you have the basic idea but you're missing a few crucial details to make it work...Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-13376220403074494522011-07-29T00:05:31.996-04:002011-07-29T00:05:31.996-04:00For Parrot, theoretically speaking, we don't h...For Parrot, theoretically speaking, we don't have to send different messages, so there would be more than (R choose L) choices. But of course in that case it would be harder to do DP to get the bijection.goodwind89http://goodwind89.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-57049249393829202492011-07-29T00:00:06.918-04:002011-07-29T00:00:06.918-04:00Hi Mihai,
I haven't coded out the solution be...Hi Mihai,<br /><br />I haven't coded out the solution because I couldn't find the test data.<br /><br />Elephants: The O(N) solution is to keep a sorted list of elephant position, then go from left to right to assign camera men. To reduce this to O(sqrt(N)), for each node in the linked list, we keep a pointer that forwards to sqrt(N) elements. Each time an element is updated, O(sqrt(N)) pointers are edited, so it should work in O(sqrt(N)) per query. The linked list is maintained by some balanced BST.<br /><br />Thanks in advance for your comments. Nice problems indeed.goodwind89http://goodwind89.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-13082096347437512862011-07-28T17:17:51.256-04:002011-07-28T17:17:51.256-04:00Believe it or not, I originally submitted Elephant...Believe it or not, I originally submitted Elephants with a flea story, but the host wanted elephants. If you host the IOI (which is a big investment), you at least get to use your local animal :)Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-47552838168138206632011-07-28T17:15:56.966-04:002011-07-28T17:15:56.966-04:00Crocodile: Yes.
Parrot: Yes. Basically you need (...Crocodile: Yes.<br /><br />Parrot: Yes. Basically you need (R choose L) > 256^M. <br /><br />Then you can use dynamic programming to compute a bijection between the 2 types of messages.Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-89967644888551380082011-07-28T16:13:45.688-04:002011-07-28T16:13:45.688-04:00Crocodile: looks like you can contract the k nodes...Crocodile: looks like you can contract the k nodes, then run a shortest path like algorithm that figures out for each other node in the graph which is the smallest budget one would need to reach the destination node.<br /><br />Parrot: it seems you can dp on the number of increasing sequences of fixed length so that you can find the smallest L which works.<br /><br />Need to think about Elephants. Why aren't they fleas like in the IMO 2000 problem http://olympiads.win.tue.nl/imo/imo2000/imo2000-problems.pdfloser2007http://www.blogger.com/profile/11530937349997805374noreply@blogger.com