I suspect I got a lot of bad karma this day (I'm the evil mind behind "Crocodile" and "Elephant".) Congratulations to the winners! See here for final results.
- Player 1 moves on the nodes of the graph, starting at the designated start node, and aiming to reach a target node. In each turn, she can traverse any edge out of her current node [except the blocked edge / see below], incurring a cost equal to the weight of the edge.
- Player 2 can block one edge at every turn. When an edge is blocked, Player 1 cannot traverse it in the next turn. An edge can be blocked multiple times, and any past edge is "unblocked" when a new edge is blocked.
Find the minimum budget B such that Player 1 can reach a target node with cost ≤ B, regardless of what Play 2 does. Running time: O~(n+m).
Problem Elephants. You have n elephants on the line at given coordinates. The elephants make n moves: in each unit of time, some elephant moves to another position. You have cameras that can photograph any interval of length L of the line. After each move, output the minimum number of cameras needed to phtograph all elephants in the current configuration.
Running time: subquadratic in n.
Problem Parrots. You are given a message of M bytes (0..255) to transmit over a weird channel. The channel can carry elements between 1 and R, but elements don't arrive in order (they are permuted adversarially). Send the message, minimizing the number L of elements sent across the channel.
Running time: polynomial. (Yes, this is an easy problem for a trained theorist.)
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
10 comments:
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.
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.
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.pdf
Crocodile: Yes.
Parrot: Yes. Basically you need (R choose L) > 256^M.
Then you can use dynamic programming to compute a bijection between the 2 types of messages.
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 :)
Hi Mihai,
I haven't coded out the solution because I couldn't find the test data.
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.
Thanks in advance for your comments. Nice problems indeed.
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.
@goodwind89: I think you have the basic idea but you're missing a few crucial details to make it work...
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.
will this algorithm work for the first subtask of task crocodile ?
dynamic programming
f(node n){
if(n is a leave)
return 0
for every node k such that k is child of n
find p_k = length_of_edge_connecting n and k + f(k)
dp[node] = the secod smallest element among all p_k
}
answer B = dp[0]
That's funny, I thought you were the one behind parrots...
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]
f(node n){
if(n is leave)
return 0
for every node k such that k is child of n
find p_k = f(k) + length_of_edge_connecting n and k
f returns the second smallest element among all p_k
}
answer B = f(0)
Post a Comment