Let's discuss problems.

How to solve F?

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

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | antontrygubO_o | 165 |

4 | Vovuh | 165 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 156 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

Let's discuss problems.

How to solve F?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/21/2019 14:11:07 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I solved it with DP, where the state is (number of saucers removed from queue, machine that is empty, time after which the other machine will become empty) and the value is the minimum time to get to that state. The important observation that allows this solution to fit in the limits is that the third parameter can be bounded by MAXH*MAXS, because if the free machine can process one saucer before the other machine will become empty it is always optimal to do so.

Thank you for perfect explanation! Actually, this is the author's solution =)

Interesting, does anybody solved it in another way?

I did slightly differently- Dijkstra with the same state. TBH I am not sure how to do it in DP way, because I had cycle in DP state: at a state instead of taking for one machine, that machine would give up its chance for the other machine, so I had to do it in Dijkstra fashion.

What's the idea behind problem H solution?

Author's solution is offline: sort queries by time -> solve problem -> sort queries by id -> output. Main idea is to move

T_{i}instead ofS_{i}. You need to store list of validity time intervalsS_{i}..S_{i + 1}(S_{n}..∞ for the last one) for typed numbers (only if 1 ≤B_{i}≤N). For each interval you can use lower_bound/upper_bound (with delta depending onT_{i}of current question) to find first query to increase and decrease counter of correct answers and put such events to priority queue (or just sorted array). The last step is to process all requests one by one using +1/-1 events from priority queue.Online solution exists too, but we decided to make simple and fun contest for our on-site participants :)

This solution is based on the fact that no two questions have the same answer.

Now I got it, thanks.

How to solve B?

We've approached it like this. Let's construct convex hull. After that you calculate answers for all segments of convex hull with two pointers.

Given one segment you want to find the farthest segment (in terms of index in convex hull array) such that you can remove all points between these two segments. You want the rays constructed from the segments (you connect

i-th and (i+ 1)-th points for one ray and (j+ 1)-th andj-th for another, I mean different directions) to intersect. This can be interpreted as "the angle between the rays is strictly less than π", this can be checked with cross product of their vectors.Several points on the same line don't make difference because you will always have the better answer when you take the earliest clockwise of them. We only solved the case with the whole convex hull being on one line with separate if.

Hope the image tells it clearer. :D

Which tool did you use to generate the image ?

Geometry widget from csacademy and paint lines over it :D

Thank you for the answer. Author’s solution is the same. I just want to add a comment to make your explanation more clear.

Several points on the same line don’t affect the described algorithm, but you should take into account all the points lying on the boundary of the convex hull to select a right pair of edges and to get correct answer.

Thank you!