efficient coding
You should get 90 points just for reading that pointless pile of garbage.
codechef sucks and teaches nothing.
codechef sucks and teaches nothing.
> 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?
¿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?
that is pure awesome. ^^^
Typical CC guy deleted the post, but I don't even care if it matched the original problem or not. You made my day either way.
Typical CC guy deleted the post, but I don't even care if it matched the original problem or not. You made my day either way.
I will give somw test cases which will help you out.
Z=1
N=3
Array = {40,55,60}
Ans is 60
Z=1
N=2
Array = {40,100}
Ans = 80
Z = 1
N = 6
Array = { 1, 1, 1, 1, 1, 1, 9}
Ans = 2.
The third case is most important to understand. If u get it , then u will get AC 100
Z=1
N=3
Array = {40,55,60}
Ans is 60
Z=1
N=2
Array = {40,100}
Ans = 80
Z = 1
N = 6
Array = { 1, 1, 1, 1, 1, 1, 9}
Ans = 2.
The third case is most important to understand. If u get it , then u will get AC 100
Last edited on
@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.
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.
Last edited on
@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?
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? |
You should get 90 points just for reading that pointless pile of garbage.
codechef sucks and teaches nothing.
Ah didn't know writing garbage yeilds members writing rancid code.
I solute you dear sir.
codechef sucks and teaches nothing.
Ah didn't know writing garbage yeilds members writing rancid code.
I solute you dear sir.
@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.
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.
I have a better solution
What if u hit 4 different coconut 10 times each,
In worst case u will have them placed as 24,11,10,9,3
So 10+10+10(third one breaks)+9(fourth one also breaks ) = 39
Updated Power : 14,1,0,0,3
Then we hit remaining 3 coconuts 1 time each and so we will break the required coconuts to be broken i.e 3 coconuts.
This would require 1+1+1 = 3 hits
Updated Power : 13,0,0,0,2
So we require 3+39 = 42 hits
What if u hit 4 different coconut 10 times each,
In worst case u will have them placed as 24,11,10,9,3
So 10+10+10(third one breaks)+9(fourth one also breaks ) = 39
Updated Power : 14,1,0,0,3
Then we hit remaining 3 coconuts 1 time each and so we will break the required coconuts to be broken i.e 3 coconuts.
This would require 1+1+1 = 3 hits
Updated Power : 13,0,0,0,2
So we require 3+39 = 42 hits
Last edited on
@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?
¿? 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?
Last edited on
> ¿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?
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.
>> 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.
Yeah we can do it in 38 now. I got another approach.
24 , 11, 10, 9 ,3
Hit each coconut 3 times
21, 8 , 7, 6, 0
Total hits = 15
Now hit each coconut 8 times
13, 0 , 0, 6 ,0
Total hits=(15)+(8+8+7) = 38
24 , 11, 10, 9 ,3
Hit each coconut 3 times
21, 8 , 7, 6, 0
Total hits = 15
Now hit each coconut 8 times
13, 0 , 0, 6 ,0
Total hits=(15)+(8+8+7) = 38
you are messing up the update part.
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.
index= 0 1 2 3 4 value= 3 9 10 11 24 number= 5 4 3 2 1 cost= 15 36 30 22 24 hits= 0 0 0 0 0 chose A[0], cost = 15 index= 0 1 2 3 4 value= 0 6 7 8 21 number= 0 4 3 2 1 cost= 0 24 21 16 21 hits= 3 3 3 3 3 chose A[3], cost = 15+16 = 31 index= 0 1 2 3 4 value= 0 6 7 0 13 number= 0 2 1 0 1 cost= 0 12 7 0 13 hits= 3 3 3 11 11 chose A[2], cost = 15+16+7 = 38 index= 0 1 2 3 4 value= 0 6 0 0 13 number= 0 1 0 0 1 cost= 0 6 0 0 13 hits= 3 3 10 11 11 chose A[1], cost = 15+16+7+6 = 44 index= 0 1 2 3 4 value= 0 0 0 0 13 number= 0 0 0 0 1 cost= 0 0 0 0 13 hits= 3 9 10 11 11 chose A[4], cost = 15+16+7+6+13 = 57 |
then, if you hit the second or third coconut 7 times, it will break.
Topic archived. No new replies allowed.