A COCI Programming Competition Puzzle

Hi everyone,

I wrote Algorithmic Thinking to teach data structures and algorithms motivated by competitive programming examples. To begin each chapter, we meet a new problem that requires us to learn new data structures or algorithmic techniques. We then use what we learned to solve the remaining problems in the chapter.

One skill that’s hard to practice in this format is identifying how to solve a problem in the first place. After all, if a problem is in the hash tables chapter, then you already know that hash tables are going to solve it!

Here, I thought it would be fun to choose a competitive programming problem but not give away the approach for solving it. You can use the hints and cues from the book to decide which chapter material is most relevant, and then try solving the problem accordingly.

Sometimes a problem is made considerably easier once you know the approach that should be used. For example, as soon as someone tells you, “hey, this is a dynamic programming problem”, already you’re able to prune away other techniques without considering them any further. You can just focus on how to adapt dynamic programming for the problem. But what if no one tells you which approach to use? You’ll have to find it! That’s what I’m hoping you’ll practice with this problem.

The problem I’ll pose is from COCI, the Croatian Open Competition in Informatics. Side note: the COCI website is a fantastic competitive programming resource. They run several contests per year, so there’s a lot of practice to be had. More than that, they offer brief editorials on almost all of the problems, in case you get stuck and need a hint. (Resist: try not to look up this problem!)

The Problem

There are $m$ people traveling to a programming competition, and they are currently waiting in a queue to check in to the airport. There are $n$ check-in desks available.

Here’s what makes this problem interesting: the workers at the check-in desks can work at different speeds, and thereby check people in at different rates. For example, the worker at one desk might take 20 seconds to check someone in, and the worker at another desk might take 30 seconds to check someone in.

To begin, all desks are free and there are only these $m$ people in the queue.

The $m$ people are in a queue, which means they must leave the queue (and thereby access a check-in desk) in the same order that they entered it. The person at the front of the queue can access a desk as soon as it’s free… or they can wait for a different desk to be free and then access that one.

What is the minimum amount of time needed to check in all $m$ people?

Input

The first line of input contains two integers: the number $n$ of check-in desks and the number $m$ of people. $n$ is between 1 and 100000; $m$ is between 1 and 1000000000.

Each of the next $n$ lines gives the number of seconds taken by the worker at a check-in desk to check someone in; these numbers are between 1 and 1000000000.

Output

Output the minimum amount of time needed to check in all $m$ people.

An Example

Here’s a test case:

2 4
4
7

Here we have two check-in desks and four people. The first check-in desk takes 4 seconds to check someone in; the second takes 7 seconds to check someone in.

How quickly can we check in all 4 people?

• We start at time 0.
• At time 0, person 1 immediately goes to the first check-in desk. Because that desk takes 4 seconds to check someone in, person 1 will finish checking in at time 4.
• At time 0, person 2 immediately goes to the second check-in desk. Because that desk takes 7 seconds to check someone in, person 2 will finish checking in at time 7.
• At time 0, there are now no free desks, so person 3 has to wait. At time 4, the first check-in desk becomes free, so person 3 can check in there… and they finish checking in at time 8.
• What should person 4 do? Well, at time 7, the second desk becomes free, so they could go to the second desk. If they did that, they’d be checked in at time 14. But that would be a bad move! Instead, they could wait until time 8 – seemingly wasting an extra second in line. But that isn’t a waste at all, because at time 8 the first desk becomes free. That first desk gets them checked in by time 12!

The correct answer for this test case is therefore 12.

Go For It!

That’s all I’ll say here. Give it a try! And feel free to check back on October 14 for my discussion of the solution. If you’d like to contact me, or you’d like me to occasionally contact you with updates, please see my Contact and Newsletter page. Thanks!