PROBLEM LINK:
Author: ???
Tester: Kevin Atienza, Jingbo Shang
Editorialist: Kevin Atienza
PREREQUISITES:
Greedy algorithm
PROBLEM:
There are n people in a row, and m topics. The n th person knows all m topics, while all the other ones don’t. Every hour, a person can either teach or learn a topic from a neighbor, but not both. What is the minimum number of hours for all n people to learn all m topics?
QUICK EXPLANATION:
- If n = 1, the answer is 0.
- If n = 2, the answer is m.
- If n > 2, the answer is 2m+n-3. (Each person immediately teaches every lesson he/she learns.)
EXPLANATION:
This is the second easiest problem, though this is a bit trickier. Many submissions missed the cases n = 1 and n = 2! When you’re getting a WA, it always helps to think of edge cases as a possible reason. It might help you reduce your penalty time. (Actually, just think of edge cases all the time in the first place.)
For n = 1, the answer is simply 0, because everyone (i.e. the only one) already knows all topics. For n = 2, the answer is m, because only person 1 need to learn. If person 2 teaches person 1 every hour, then this will take m hours. It’s also clear that it’s impossible to do it in fewer than m hours, because one needs m hours to teach all m topics.
Now, let’s assume n > 2. This is trickier because person n-1 cannot teach and learn at the same time, yet he (let’s assume person n-1 is a “he”, because person n is already a she :D) also needs to teach person n-2. In fact, this already gives us a lower bound of 2m seconds: the time it takes for person n-1 to teach and learn all topics.
The first thought is to be greedy: what if every person teaches every lesson he/she learns in the next hour? Let’s look at the times which person n-1 learns each topic (numbered 1 to m):
- He learns topic 1 on hour 1 (then teaches it on hour 2).
- He learns topic 2 on hour 3 (then teaches it on hour 4).
- He learns topic 3 on hour 5 (then teaches it on hour 6).
- He learns topic 4 on hour 7 (then teaches it on hour 8).
- …
- He learns topic m on hour 2m-1 (then teaches it on hour 2m).
We can also view this from the perspective of the topics: Once a given topic is learned by person n-1, the next hour person n-2 will learn it, and then n-3, and so on. So, the moment a topic is taught for the first time, after n-2 hours all people would have learned it. This means that:
- All people will learn topic 1 at time (n-2)+1.
- All people will learn topic 2 at time (n-2)+3.
- All people will learn topic 3 at time (n-2)+5.
- All people will learn topic 4 at time (n-2)+7.
- …
- All people will learn topic m at time (n-2)+(2m-1).
The latest one among all these is (n-2)+(2m-1). Thus, using this method, all people will learn all topics in (n-2)+(2m-1) = 2m+n-3 hours.
Okay, good. But can we do better? The answer is no. To show it, we need to look at the earliest time all m topics can be taught by person n-1. Clearly he can do it within 2m hours, but not less (because he needs m hours to learn and m hours to teach). Now, the $2m$th hour must definitely be used for teaching, otherwise at that hour he would have already taught m topics but only learned m-1, which is impossible. Thus, the latest time he teaches a topic is at hour 2m, and this topic needs (n-3) more hours to reach person 1. Thus, we need at least 2m+(n-3) hours, thus showing that this is the best we can do.
Time Complexity:
O(1)
AUTHOR’S AND TESTER’S SOLUTIONS:
[setter][333]
[tester][444]
[editorialist][555]
[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.