> Any good test case to understand the question properly?
¿what part you don't understand?
let's say that the A sequence is sorted in non-decreasing order A_j <= A_{j+1}
suppose that you bang a coconut A_N times, it will break.
suppose that you bang all the coconuts A_1 times, one of them will break
so there you have two strategies, the first one cost you A_N hits, the second one N * A_1, ¿which is better?
now say that you hit each coconut A_42 times, ¿how many coconuts do you need to hit in order for one to break?
@abo... I know how the answer of the third test case is 2.. but if Z is greater than one, I can't do it the same way by calculating minimum hits for 1 coconut then updating power of other coconuts, resorting the array and then again calculating the ans in the same way. time wont exceed but it'll give WA.
for example:
z = 2, n = 4
array = {4,5,5,100}.
ans = 15.
I'll hit 3 coconuts 5 times each and at least 2 of them will break.
and only this approach also gives WA. so might be something else I guess.
@ne555 the logic you mentioned above works only for Z=1 when all elements of array are UNIQUE. Any suggestion on how to proceed for arrays having duplicacy also?
> I'll hit 3 coconuts 5 times each and at least 2 of them will break.
but you only need to break 1, ¿why are you breaking 2?
@amitsrivaastava647: this would be easier if instead of coconuts they were apples.
the strategy works fine with duplicates, ¿what was your answer to this?
now say that you hit each coconut A_42 times, ¿how many coconuts do you need to hit in order for one to break?
@ne555 ..sorry, I wanted to break 2 coconuts there.
now another example where I want to break 3 coconuts out of 5 with powers = {3,9,10,11,24};
first, if I hit 4 coconuts 9 times each then at least 1 of them will break. hits = 9*4=36;
updated powers = {3,0,1,2,15};
now I hit 4 coconuts 1 time each then one will break. hits = 36+4=40;
updated powes={2,0,0,1,14};
now I hit 3 coconuts 1 time each such that 1 will break. hits = 40+3=43.
with the previous method, I won't get min ans by hitting 4 coconuts 11 times each such that atleast 3 of them will break then hits=11*4=44 so direct logic will not work here I guess.
@abo... yeah this is better. I don't think there can be a generalized pattern to find the number of hits then if we want to break more than 1 coconuts. what can possibly be done then?
> with the previous method, I won't get min ans by hitting 4 coconuts 11 times each
¿? you only need to hit 2 coconuts 11 times so one breaks
¿what's the previous method?
{3,9,10,11,24};
compute the cost
{15, 36, 30, 22, 24}
¿why do you chose the one with cost 36 (the biggest) instead of the one with 15 (the smallest)?
you may break 3 with only 38 hits.
> I can't do it the same way by calculating minimum hits for 1 coconut then updating power of other coconuts
¿how do you calculate the cost?
¿how do you update?
it indeed works for the {4,5,5,100} case
> I'll hit 3 coconuts 5 times each and at least 2 of them will break.
that's the answer that will give you, ¿are you saying that you may do it in less than 15 hits?
> ¿what's the previous method?
>> I'll hit 3 coconuts 5 times each and at least 2 of them will break.
>that's the answer that will give you, ¿are you saying that you may do it in less than 15 hits?
min of for(i=0;i<n;i++)power[i]*(n-i+z-1)
this gives perfect ans for this {4,5,5,100},z=2 but not for {3,9,10,11,24},z=3;
>you may break 3 with only 38 hits.
how to do this?
>¿how do you calculate the cost?
the same way you're calculating costs like {15,36,30,22,24}. and hitting minimum number of times (15 in that case).
>¿how do you update?
since 5 coconuts hit 3 times each so updated powers are {0,6,7,8,21}. updated costs {0,24,21,16,21}. now hit 2 coconuts 8 times each (min hits = 16). updated powers {0,6,7,0,13} updated costs {0,18,14,0,13}. hit a coconut 13 times and it'll break. toatal hits = 15+16+13 = 44.
but as @abo suggested there's a solution with 42 hits and you're suggesting a solution with 38 hits.
notice that in the third stage {0, 6, 7, 0, 13} the last one already received 11 hits, so you know it can't be the one that dies with 6 or 7
then, if you hit the second or third coconut 7 times, it will break.