Today, at http://www.timeanddate.com/worldclock/fixedtime.html?&day=09&month=07&year=2012&hour=07&min=00&sec=0&p1=179 will take place SRM 549. I suggest to discuss tasks in this post after contest finishes.

Good luck everybody!

Rating changes for last rounds are temporarily rolled back. They will be returned soon.
×

# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

7 | adamant | 162 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 154 |

Today, at http://www.timeanddate.com/worldclock/fixedtime.html?&day=09&month=07&year=2012&hour=07&min=00&sec=0&p1=179 will take place SRM 549. I suggest to discuss tasks in this post after contest finishes.

Good luck everybody!

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/01/2023 05:51:27 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Its the first time(I have logged in hundreds of times) I am getting this error :"Unable to launch the application" when I click on the downloaded applet file..Can anyone tell me why is this so and how to get away from it

UPD: More specifically I am getting this error: Unsigned application requesting unrestricted access to system

Solution found after some googling and searching topcoder forums :

Sol->Run "javaws -viewer" and delete all instances of the TC arena there. Then open de jnlp file again and it should redownload the TC arena after which everything should work

Yep, I had the same problem two days ago and I solved it in the same way.

Another solution is to go to java settings in control panel (on Windows) and remove temporary internet files.

output for this should be? (input in edit)

36

My greedy algo. gives 33. So, the following greedy is wrong, right?:

take the bottom with biggest radius and smallest slope (h/r). and try to match it with largest radius top(>radius of bottom) and with smallest slope (>slope of bottom).

Yes, greedy approach is incorrect.

The correct solution is the following. Let's assume when we can make magic hat with

topH,topR,bottomH,bottomR. Obviously,topR<bottomR, otherwise we either can not put hat on the top or make bottom hat visible.Also,

topH·bottomR>topR·bottomHmust be held ( this can be deduced from similarity of triangles).So, we can check if

top_{i}andbottom_{j}can be combined. Imagine bipartite graph, first part is top, second is bottom. There is an edge fromtop_{i}tobottom_{j}if and only if they can be combined. The answer is the size of maximum matching (http://en.wikipedia.org/wiki/Matching_(graph_theory)) in this graph.Yes. But isn't that a overkill? I thought a greedy algo. of some sort might solve it. ?

No. Because it is standart problem, where you should find maximal matching in graph.

Not necessarily. This problem can be reduced to bipartite maximal matching, but not vice versa. Maybe the matching can be done more efficiently on graph of such special form. Kuhn's algorithm seems like an overkill to me too, but I couldn't find a better solution right away.

See Petr's solution. As far as I understood, after sorting edges from earlier vertexes is subset od edges from vertexes with greater numbers. In that case gready works.

A greedy algorithm that works is: 1) sort the top hats by increasing h/r. 2) sort the bottom hats by increasing r, then by h/r if two rs are equal. 3) go through the bottom hats in order and match each with the first unmatched top hat possible.