Exam Plan

See the original problem on HackerRank.

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 exame 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.

comments powered by Disqus