Codeforces Round #123 - hmmm

A. Let's Watch Football

http://www.codeforces.com/contest/195/problem/A

You are downloading a streaming video from the internet. Because your internet connection is kind of slow the video may stop. To avoid this problem you decided to pause the video for certain amount of time and let it load. Your task is to return the minimum amount of time required to watch the video without pauses.

I found this problem really interesting, because, I been dealing with this kind of issues really often... Let's first define the variables given to us:

\(a\) denotes the size of data needed to watch one second of the video.

\(b\) denotes the size of data you can download from the network per second. 

\(c\) denotes the video's length in seconds.

We can further define the total size in units of the video as \(a \cdot c\). For each second waiting we subtract from the total size the amount of data we download after \(t\) seconds \(t \cdot b\). For the remaining data \((a \cdot c) - (t \cdot b)\) we check if it can be downloaded in less or equal  than \(c \cdot b\) seconds.

B. After Training

http://www.codeforces.com/contest/195/problem/B

You are given \(n\) balls and \(m\) baskets. You need to put the \(n\) balls into the \(m\) baskets with the following constraints:

(1) Each new ball in the basket with the least number of balls.

(2) If we got several basket with the same number of balls, we choose the basket which stands closer to the middle.

This problem has two main approaches:

1) Sorting.

2) Generate the sequence following certain pattern rules.

I took the second one. Let's first consider the example when \(n = 4\) and \(m =3\), the following graphic illustrate the final configuration after arranged all the balls in the baskets:

Is easy to see that when m is odd we start to move from the center in a zigzag motion from left to right. At Each step we try to put the next ball as near as possible from the center without violating the least number of ball constraint. Note that in the odd case the second move (if is possible) is always to the left. In the even case is necessary to first visit the another center and then continue in zigzag fashion.

To implement this idea I used two pointers that represent the movements to the left and the right. The overall time complexity of this solution is \(O(n)\).