PROBLEM LINK:
Author: Vaibhav Tulsyan
Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Most basic programming
PROBLEM:
There are N tasks numbered from 1 to N to perform. Two people, Xenny and Yana, have to complete all these tasks alternatingly. It means that either Xenny performs tasks with odd numbers and Yana with even numbers, or Xenny performs tasks with even numbers and Yana with odd numbers. These two ways are the only possibilities to fulfill the task. Moreover, we know that Xenny takes X_i seconds to complete the i-th task, while Yana takes Y_i to do that. The goal of the problem is to compute the minimum possible time in which Xenny and Yana can complete all the tasks.
QUICK EXPLANATION:
Calculate the time needed to complete the tasks for each of two distinct ways of doing that and return the minimum of these times.
EXPLANATION:
The main observation is that since all the tasks have to performed alternatingly by Xenny and Yana, then there are only two distinct ways of completing all the tasks:
- Xenny starts first, which means that Xenny performs tasks with odd numbers: 1, 3, \ldots, while Yana performs tasks with even numbers: 2, 4, \ldots
- Yana starts first, which means that Yana performs tasks with odd numbers: 1, 3, \ldots, while Xenny performs tasks with even numbers: 2, 4, \ldots
If we assume that for i = 1, 2, \ldots, N X[i] is the time for performing the i-th task by Xenny and Y[i] is the time for performing the i-th task by Yana, then we can solve the problem by the following pseudocode:
xenny_starts_first = 0 // time to perform all the tasks using the first method,
// i.e. when Xenny starts first
for i = 1 to N:
if i is odd:
xenny_starts_first = xenny_starts_first + X[i] // add time of completing
// the i-th task by Xenny
else:
xenny_starts_first = xenny_starts_first + Y[i] // add time of completing
// the i-th task by Yana
yana_starts_first = 0 // time to perform all the tasks using the second method,
// i.e. when Yana starts first
for i = 1 to N:
if i is odd:
yana_starts_first = yana_starts_first + Y[i] // add time of completing
// the i-th task by Yana
else:
yana_starts_first = yana_starts_first + X[i] // add time of completing
// the i-th task by Xenny
print minimum(xenny_starts_first, yana_starts_first)
Since in order to compute the time of completing the tasks for each of the two methods we need only to iterate once over all tasks, the overall time complexity of this solution is O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.
Editorialist’s solution can be found here.
