# CHRL1 - Editorial

Contest

Practice

Author: Roman Furko

Tester: Sergey Kulik

Editorialist: Praveen Reddy Vaka

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.

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.

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

3 Likes

Very nicely writtenâ€¦really helpful for school kids or beginners !!!

2 Likes

I â€śsolvedâ€ť it on `Go`, but I got WAs, so I guess it wasnâ€™t solved after all
I was checking the solutions from others, and it looks to me that it shouldnâ€™t result in a WA, maybe Iâ€™m missing something.

Is it possible to keep testing, or to get the input/output files from the problem?

you can still submit and check in the practice link given at the top of the editorial. codechefâ€™s policy is not to make input/ouput data public so we canâ€™t give you the files.

http://www.codechef.com/wiki/tutorial-bitwise-operations. on clicking this link it shows :page does not exists

The . should not be there at the end of the link it was meant as a â€śfull stopâ€ť. I have made them proper hyper links so that they work as expected.

1 Like

Oh, thanks!
yeah, I understand, the files were only if it wasnâ€™t possible to keep practicing, but I missed your link at the top, thanks

Last time I attempted to solve something in the Go programming language I got quite some runtime errors where the same Java/C/C++ code got AC, so, maybe judgeâ€™s configurations for Go arent that good yet

I have something to â€śreportâ€ť when using GO
In this contest I used for example this (below), and it wasnâ€™t accepted.

``````fmt.Scanf("%d", &t)
``````

However when I changed that to this (below), my solution was accepted.

``````fmt.Scan(&t)
``````

I will inform the codechef team about this. It would be great if you can also drop an email to them at feedback@codechef.com

We are looking into this. Please wait for an announcement on this from us soon.

why this problem cannot be solved using the knapsack algorithm??..

@simranjot0069

consider the case:-

1

3 10

1 8

9 8

10 11

@simranjot0069

Thereâ€™s nothing wrong with the Knapsack algorithm, itâ€™s just that it will TLE when the value of K is near or is equal to 100000000, even I have tried the Knapsack algorithm and It TLEâ€™s in the last subtask.
The link to my solution - solution