Paying Up : Practice question Wrong Answer..(Help please)

general
1

Hi

I have the following python code snippet to solve the Paying Up problem .

The tests pass as expected on my computer based on the sample input provided but when I upload the
same I get a WA .

Please see the code below

from sys import stdin 

T=int(stdin.readline())

for t in xrange(T):

	notes,demand=map(int,stdin.readline().split())
	sum=0
	wallet=list()
	filter_wallet=list()
	
	for n in xrange(notes):
		i=int(stdin.readline())
		wallet.append(i)
		
	wallet.sort(reverse=True)
	filter_wallet=filter(lambda x: x <=demand ,wallet)
		
	for c in filter_wallet:
			
		if (sum + c )<= demand:
			sum=sum + c
			
	
	
	print "Yes" if sum == demand else  "No"

Am I making any mistake …?

2

if i understand correctly, your algorithm seems wrong.

you’re starting from the highest note value under the demand, and adding them as long as the sum does not exceed the demand. but it could fail.

let’s take this example :

1
3 10
9
5
5

your program says ‘No’, although it’s possible with 5+5.

adding 9 from the very beginning prevents any future combination.

you should look for another reliable algorithm to do that (with dynamic programming for example here).

am i wrong somewhere ?

3

My bad …

It was working for the sample inputs provided .

But I missed an obvious Test . Thanks cyberax for pointing this out.

4

you’re welcome ! good luck