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