PROBLEM LINKS
Author: Roman Furko
Tester: Sergey Kulik
Editorialist: Praveen Reddy Vaka
DIFFICULTY:
cakewalk
PREREQUISITES:
Basic Combinatorics, Enumerating/Iterating over combinations
Hint: Consider all possible combinations of choosing oranges and see what you can do with them.
EXPLANATION
subtask1: The weight for each orange is given to be 1.
To pick the oranges such that we get a maximum weight purchase is the same as picking the most number of oranges. This can solved by a simple greedy approach. Just sort the array of costs in increasing order. Traverse the array from left to right and see how many oranges can you buy using the k rubles that you have. The answer will be the number of oranges that you can get.
subtask2: n = 5
Given five oranges you can choose your oranges from one of the following 31 ways (Consider a string of “abcde” of length 5, each character can be 0 or 1. If ith character is 1 we take ith orange otherwise we don’t.)
C(5, 1) = 5 possible combinations of choosing exactly one orange.
[“00001”, “00010”, “00100”, “01000”, “10000”]
C(5, 2) = 10 possible combinations of choosing exactly two oranges.
[“00011”, “00101”, “00110”, “01001”, “01010”, “01100”, “10001”, “10010”, “10100”, “11000”]
C(5, 3) = 10 possible combinations of choosing exactly three oranges.
[“00111”, “01011”, “01101”, “01110”, “10011”, “10101”, “10110”, “11001”, “11010”, “11100”]
C(5, 4) = 10 possible combinations of choosing exactly four oranges.
[“01111”, “10111”, “11011”, “11101”, “11110”]
C(5, 5) = 10 possible combinations of choosing exactly five oranges.
[“11111”]
Just go through all possible combinations and among the combinations which have a cost less than equal to k rubles pick the one yielding the maximum weight. You can hardcode the previous combinations but computing them by hand may be very tedious so it is not recommended unless you get it is more clever way like copying them from some other source on the internet. We will now see a way of doing this using code. Consider the following code.
for (i = 1; i <= 5; i++) {
//take ith orange
for (j = i+1; j <= 5; j++) {
//take ith, jth orange
}
}
In the outer for loop you can select exactly one of the oranges 1,2,3,4 and 5. In the inner for loop you can select all possible ways of choosing 2 oranges (1, 2), (1, 3), (1, 4), (1,5), (2, 3), (2,4), (2,5), (3,4), (3,5),(5,5). Using more for loops you can get a way to select all possible ways of 3 oranges, 4 oranges, 5 oranges. Every time you select a subset of oranges just see if they don’t cost more than k rubles and among all such possible subsets pick the one with the maximum weight. Refer to editorialist’s solution for an implementation of this.
subtask3: (solves subtask2 and subtask1 as well)
We will select all possible combinations of choosing from the n oranges and among whichever combinations cost us no more than k rubles we pick the one with the maximum weight. The number of different ways of choosing oranges from the given oranges is same as the number of subsets of a set which is 2^n (this includes a way of selecting no orange as well). Since n is at max 10 we are looking at a maximum of 2^10 = 1024 combinations, so the problem is easily solvable this way. You can solve this in multiple ways.
Method 1:
You can iterate through all the subsets of the n oranges by using simple bit level operations. Read through the tutorials at http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation and http://www.codechef.com/wiki/tutorial-bitwise-operations. You can see the tester’s code for an implementation of this mechanism. This is the usual expected and recommended way of doing this kind of a thing in contests.
Method 2:
You could precompute all possible subsets in the following way. We will use string representation used in subtask2. We use a string S of length n to represent a subset, if ith position is 1 we select ith orange otherwise we don’t.
Have a two dimensional array combinations11 (Since n <= 10)
combinations[i][j] holds a list of all strings denoting the ways of selecting j oranges from a total of i oranges. (j can’t be greater than i)
We will initialize combinations[0][0] with a list having just the empty string.
We will initialize combinations[i][0] with a list having just a string of length i made up of all 0’s.
We can compute combinations[i][j] recursively as follows.
We want to generate all i length strings having exactly j bits set to 1. We can set 1st bit to either 1 or 0. In the first case we can add 1 in front of the list of all strings of combinations[i-1][j-1]. In the second case we can add 0 in front of all the strings of combinations[i-1][j] (only if i-1 >= j otherwise this would lead to absurdity). These are the only possible strings of length i and having j bits set. So we can add all these strings to a new list and set them to combinations[i][j].
We can compute the whole combinations array either recursively or iteratively. Refer to editorialist’s solution to look at a way of generating this iteratively.
Once we have this generated for a given n . We look at all the strings in the lists combinations[n][1], combinations[n][2], ……, combinations[n][n] and for each string we see the oranges that are to be selected and compute our maximum weight needed.
Method 3:
Since n can be at max 10 we can simply use 10 for loops just like the 5 for loops used in subtask2. Given the nature of for loops conditions if there is anything to be selected it will be executed otherwise the for loop condition fails in the initial check it self, so the previous method just works seamlessly in this case. Refer to the method subtask3_forloops in editorialist’s solution. This is a bit ugly solution and has a chance of some typos getting in when dealing with so many loop variables. If you are a beginner this might seem the simplest of all three solutions but on greater practice you will realize that the method 1 is in fact the simplest solution to implement in this case.
If you are using a language like python which has in built functions to generate combinations your task becomes very easy. See the editorials python solution. Note that currently python is not a supported language in either IOI or ICPC, but it is supported on all major online judges.
Note: This problem looks like a standard knapsack but the DP solution for knapsack for this problem would get a Time Limit Exceeded or Memory Limit Exceeded message because of cost being as big as 10^8.
SOLUTIONS
Setter’s Solution: CHRL1.cpp
Tester’s Solution: CHRL1.cpp
Editorialist’s Solution: CHRL1.java CHRL1.py
