I am sorry for seeming desperate.. but that's because I am.. I haven't been able to sleep because of this problem.. Any help is much appreciated.. This is regarding the problem D of CF Round 1044.. "Chicken Jockey".. I don't need you to validate my code.. just let me know why my approach would be wrong.. Please read the question before moving forward.. thank you..
Question
My Approach
So what I'm trying to do is take a baseline value of the answer and store it in the sum.. the baseline value is what we would get if we keep killing the bottommost mob.. Now the actual answer can only be less than this.. how you may ask?? by breaking off mobs from the middle.. So now I create a new array "val" which stores how much I'd benefit if i killed the mob at that index.. I store this in negative so that I may add it to my baseline answer and reduce it.. So now obviously it's better to take as many negatives as possible.. except in the case where we have continuous negative values.. in that case what I do is I find the minimum subsequence sum of alternating elements..(there's only two.. so whatever the minimum value among those is.. that's what my "fun()" function is for) and then add it up to sum.. That's it.. that's my approach...
I have analysed the solution in the editorial.. I have tried to connect it to my solution.. It should be correct but I don't know what's wrong... It doesn't make any sense.. This never happens with me.. I am losing my mind.. Please help me stop losing my mind.. I might go crazy soon.. It's been days like this. Thank you.
I have the same approach as yours until storing "val". I store it as positives;
Instead of finding minimum subsequence of sum, you should use DP to decide whether this node should be taken.
335369188
If you look at my DP,
DP[i][0] means we don't take the val from this index,
DP[i][1] means we take the val from this index.
with the exception DP[0] that cannot take the val (DP[0][1])
instead of val my array is named "benefit"
I haven't seen your code, if you have seen mine and still confused, explain your confusion and I will reply.
Of course your dp approach will work.. I have no doubt about that.. but why wont finding minimum subsequence work?? It's always good to take values that subtract from the answer and we cannot take two adjacent values... so from a list of continuous negatives.. it makes sense to find sum of alternating subsequences.. and then find the minimum of them.
the reason why your approach is failing:
1. taking high index doesn't always result in reduced answer
2. taking alternating is not always the best
suppose you have 3 1 1 3, based on your approach it would be 4, but the best is 6
No brother the best IS 4 in your example.. break off the 3rd one.. the last gets destroyed.. then all that remains is detroying the 1st one.. so 1 + 3.. that's 4.. If you say that taking alternating is not always the best.. then can you please explain to me logically why not?? Also I did not understand your first point.. where am I taking high index?.. could you elaborate a little more?
sorry,
i meant this is your negative array, not the original question
High index is just the mob at the top
so you say if my negative array has -3 -1 -1 -3, yes my function will return -4.. but where can you get -6 from??
why cant you get 6 ...,
just take the first and the last
OHHHHHHHHHH.... I'm so sorry my guy.. thank you so so so sooomuchh... It finally makes sense I was making such a rookie mistake
it's okay, you have grown as a person (at least in coding)
I will definetly help you whenever you need it.. I am extremely grateful for your effort.. Thank you again my friend.. You have saved me lots of headache.. It was so simple.. It was right under my nose.. You are a genius my friend.
that's a high praise, many people are better than me
Yea but you helped me so you are a genius for me now