Exam Plan · Coding Gym

Solutions

Since we want to maximize the number of chapters, we just sort the array and pick the first chapters which sum is less than or equal to \( t \).

Here is a C++ implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int n, t; cin >> n >> t;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
sort(begin(v), end(v));
auto cnt = 0;
for (auto i=0; i<n; ++i)
{       
    if (t-v[i] < 0)
        break;
    t -= v[i];
    cnt++;
}
cout << cnt;

The solution is \( O(N \cdot logN) \).

Similarly, a valid solution consists in summing up the first exam values incrementally until the sum is less than or equal to t:

1
2
3
4
5
6
7
8
9


sort(begin(v), end(v));
auto psum = v.front();
auto cnt = 0;
for (auto i=1; i<n && psum <= t; ++i)
{       
    psum += v[i];
    cnt++;                    
}
cout << cnt;

This snippet leads to recognizing a few patterns:

prefix sum
take while a certain condition holds

We have the opportunity to express such patterns with C++ ranges:

1
2


action::sort(v);
cout << ranges::distance(view::partial_sum(v) | view::take_while([=](int i) { return i <= t; }));

Note: the execution of partial_sum is totally lazy (e.g. it does not run when the condition gets false).

We can even run the partial_sum on the whole array and do a binary search to quickly find the target:

1
2
3
4
5
6
7


sort(begin(v), begin(v));
partial_sum(begin(v), begin(v), begin(v));
auto lb = lower_bound(begin(v), begin(v), t);
if (lb == begin(v) || *lb > t)
    cout << distance(begin(v), lb);
else
    cout << distance(begin(v), next(lb));

Having fun with sorting

Our practice at Coding Gym includes experimenting and getting the most out of each challenge.

In the solutions above we have sorted the whole array before running the core algorithm.

Consider the observation:

we should sort only the first t elements of the exams array

In other words, knowing that each exam is at least 1, if t is less than n, we can avoid sorting the whole array but instead we can work only on the first t elements.

In the following snippets, we’ll ignore the patterns we can successfully apply on the core algorithm (discussed in the section above).

One possible solution consists in using partial_sort that might be better when t is way less than n:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


partial_sort(begin(v), begin(v)+min(t,n), end(v));
auto cnt = 0;
for (auto i=0; i<n; ++i)
{       
    if (t-v[i] >= 0)
    {
        t -= v[i];
        cnt++;            
    }
}
cout << cnt;

Another solution consists in getting the t-th position sorted and then sorting all the previous elements.

This can be done with the Quick Select algorithm that in C++ is implemented as nth_element:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


auto sortEnd = end(v);
if (t < n)
{
    nth_element(begin(v), begin(v)+t, end(v));
    sortEnd = begin(v)+t;
}
sort(begin(v), sortEnd);
auto cnt = 0;
for (auto i=0; t-v[i]>=0; ++i)
{       
    t -= v[i];
    cnt++;            
}
cout << cnt;

Only when \( t < n \), we apply nth_element which:

sets at the t-th position the element what would be there if the array was sorted
puts before the t-th position all elements less than v[t]
for the previous condition, we can just sort the first t elements (std::sort is fine here)

The scope here is to let our brain think, experiment with different tradeoffs and learn new patterns and concepts. For example, learning about Quick Select might be very interesting. This simple challenge led us to enter more advanced concepts on tiptoes.

What about heap?

Andrea Battistello found another awesome solution making use of heaps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


n, t = map(int, input().split())

ordered_list = []

total_sum = 0
for i in range(n):
    weight = int(input())
    
    if weight <= (t - total_sum):
        heapq.heappush(ordered_list, -weight)
        total_sum += weight
    elif ordered_list and weight <= -ordered_list[0]:
        w = heapq.heappop(ordered_list)
        heapq.heappush(ordered_list, -weight)
        total_sum += weight + w

print(len(ordered_list))

This solution works also online. Suppose we have the following input:

We read 4 and we push it into the heap. We can now read 6 hours of chapters (10-4).

Then we read 1 and we push it into the heap. We can now read 5 hours.

Then we read 5 and we push it into the heap. Now we have no more hours left.

Then we read 6 and we ignore it since it’s bigger than the top of the heap (aka: studying this chapter would not give any advantage).

When we read 2 and since it is smaller than the top of the heap (5), we push it into the heap and remove the top (5).

Now the heap contains:

1

4 2 1

And 3 hours left!

Then we read 1 and we push it into the heap. Now we have 2 hours left. Then we read 2 and we push it into the heap. Now we do not have any hours left.

The heap contains the following values:

1

4 2 2 1 1

Finally, we read 1 and we push it into the heap, popping 4 at the same time.

sort prefix sum priority queue