CHRL1 - Editorial

PROBLEM LINKS

Contest

Practice

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

3 Likes

I “solved” it on Go, but I got WAs, so I guess it wasn’t solved after all :frowning:
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?

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

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)

What could be done so we could warn other users about this in the future?

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

1 Like

@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

1 Like

Very nicely written…really helpful for school kids or beginners !!!

2 Likes

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.

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

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

The problem can be solved using knapsack algorithm. But the key is you should go for recursive solution and not for the iterative one. The recursive solution will save you from running the unnecessary loop from 0 to k.

Here is my python code - CodeChef: Practical coding for everyone. Did it in .21 seconds.

1 Like