Cant we use greedy approach in this?

#1

Like we can add m and y,this will give us the total no. of coupons available and divide it by x…result will be the total no. of students who can get the scholarship?

#2

Hey Anshul,
This problem is not a greedy approach , answer for this problem can be found using monotony search. As far as your approach , lets examine this test case
3 5 5 6
(N M X Y) respectively.
here,

->Student 1 =5 coupons

now we don’t have any more left
Student 2 doesn’t have any, so

->Student 2= X

now comes student 3, we will take 6 coupons from him so total coupon will be 6
now student 2 will be grant scholarship but not student 3.
So ,

->Student 2=5 coupons
->Student 3=1 coupon.
Moreover, why not greedy approach . The answer for this problem will lie in between [0,n] and it might be possible that addition of m and y, and then divide it by x can be greater then n, which is not acceptable.
Thank you.

#3

Can u give any example where greedy fails?

#4

Yes sure,
N M X Y
4 7 2 3
as per your greedy approach (7+3)/2 which gives you 5
but the total number of students are 4.
Hope this will help you.

#5

but i can put the condition that it should be less than n

#6

It will be hard code @garganshul151, else i won’t recommend you using it :smile:

#7

how will it be hard…its just line or two ?

#8

That’s why it’s hardcode cause it will fail in dynamic test cases as discussed above :smile:

#9

how it can be…give example to me its just a line with o(1) TC

#10

I have provided you with sanple test cases also. So there’s no need of repeating the same question @garganshul151 :smile:
I’ll suggest you to try and submit your code with the logic you have applied, if it gets accepted then it’s good else you can see the video provided for this problem in your course.

#11

first of all dont talk to me likethis u r not my boss…ek question pucha h nhi pta answer to mna krdo saaf saaf time kyu khrab krrhe ho mera

#12

time…or dhang se baat kra karo tehzib se

#13

I’ll appreciate that :smile:

#14

you should learn before becoming TA

#15

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.