EASYP - Editorial

NOTE:

This editorial belongs to a closed contest held for Kendriya Vidyalaya, Aurangabad school. Also, for the domain of students participating, the problems were kept simple. So, you can safely skip this editorial.

PROBLEM LINK:

Practice
Contest

Author: Abhinav Kaushlya
Tester: Abhinav Kaushlya
Editorialist: Abhinav Kaushlya

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

The problem is to find the the largest amount of items that sums to a number <= a given value.

QUICK EXPLANATION:

We can do this by simply constructing a sum array and then finding out the value to which the problem answers to by using a bonary search algorithm.

EXPLANATION:

First we will construct the sum array. Hence for the ith element in the sum array, the s[i] will be sum of previous two elements. Further we will use a binary search algorithm to find the upper_bound with the given query. This will be efficient enough to pass all the tests in given time.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS: