CodeChef invites you to participate in the September Lunchtime 2014 at http://www.codechef.com/LTIME16. This is an IOI style contest. This means that the problems will be partially graded. You will get score for passing certain test data.

Time: 29th September 2014, 1100 hrs to 1400 hrs. (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/LTIME16/

Registration: Just need to have a CodeChef user id to participate. New users please register here

- Problem Setter : Roman Furko
- Problem Tester: Gedi Zheng
- Editorialist:Devendra Agarwal
- Russian Translator: Sergey Kulik
- Mandarin Translator: Gedi Zheng & Minako Kojima

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef User ID, in order to participate.

I have some unsolved problem. There is some description of it.

You are given set of points with size N. You should build polygon with minimal square without intersections that contain every point such a vertex of polygon.

It will be great if you attach your code :)

Please give me any hints about it. I need optimal algorithm as such as possible.

Thanks.

313A - Ilya and Bank Account

This problem is the easiest one. You need to use only div and mod functions. If n>0, then answer is n, else you need to delete one of two digits.

For better understanding you can look at solution.

313B - Ilya and Queries

Precalculate some array A_i, that A_i = 1, if s_i = s_i + 1, else A_i = 0. Now for any query (l, r), you need to find sum of A_i, that (l ≤ i < r). It is standart problem. For solving this problem you can precalcutate some another array Sum, where Sum_i = A₁ + A₂ + ... + A_i. Then sum of interval (l, r) is Sum_r — Sum_{l-1}.

For better understanding you can look at solution.

313C - Ilya and Matrix

At the start sort array. Let C_i — number of times of entering the number in A_і optimal placement. Answer is sum of A_i * C_i for all i (1 ≤ i ≤ 4ⁿ). If we look at the array C, we can see that for maximal element C = n + 1 (for array with size 4ⁿ), then for second, third and fourth maximum elements C = n. On this basis we can see, that for array with non-increasing order answer calculate like Sum(1, 1) + Sum(1, 4) + Sum(1, 16) + ... + Sum(1, 4ⁿ). So, for solve this problem you have to know only sort.

For better understanding you can look at solution

313D - Ilya and Roads

To solve this problem you need to use dynamic programming. Let Full_i, j — minimal cost of covering interval (i, j). Fix left border and move right. You can solve this subtask with complexity O(nm) or O(nmlogn). Now we need to solve the standart problem of dynamic programming. Cover K points with intervals that have not intersect. This problem with square dynamic. dp_i, j — minimal cost of covering j-points, if you look some prefix length i. Answer for all problem is minimal integer from dp_i, j, (k ≤ j ≤ n).
To solve second part:

1) dp_{i + 1, j} = min(dp_{i + 1, j}, dp_i, j) — skip point with number i + 1

2) dp_{k, j + len} = min(dp_{k, j + len}, dp_i, j + Cost); Cost — cost of interval with length len, that ending at point k. We precalculate Cost at first part of solution.

For better understanding you can look at solution

313E - Ilya and Two Numbers

Author solution is harder than that which is offered by MrDindows. It is solution of MrDindows.

1) Get the number of our sequences in sorted by frequencies. Thus from the first sequence (hereinafter — the first type) — in a direct order from the second — to the contrary.

2) These numbers are put on the stack, where if, recording onto the stack of the second type, we find the number at the top of the first type, then this pair of extract and add to the answer.

3) At the end, obviously the stack we can find a number of properties of the second type and the first bottom — on. Then their grouping in response pairs with the start and end.

For better understanding you can look at solution.

Sorry for waiting.

Hello everyone!

Codeforces Round #186 (Div. 2) will take place on Thursday, May 30th at 19:30 MSK. This is my first Codeforces Round and I hope that everyone will enjoy this round.

I would like to thank Gerald for helping me prepare this round. Special thanks to Delinur for translation of all problem statements into English.

Problems point values today is: 500-1000-1500-2500-2500

Good luck & have fun! :)