If we have n elements in an array and we have to choose various combinations starting from any element and ending at any element but it must include all elements of array and then we have to determine which combination will give the min value of all combinations possible based on a logic or condition…then how can we use dp …
I want to solve this type of problem in o(nlongn ) complexity or less than that …
Plz provide the code as well…
Elements may be unique or.may not be …
hi @S19LPPP0202 can you elaborate your problem i did not fully understand what you are trying to do.
suppose i have an array
10 20 30 40 200 50
now i can choose any element as my starting element and any element as my ending element
but the combination must include all elements of array…
i am trying to solve a minimum output problem where i have to perform some operation on each element (each operation has a cost)and then choose another element and perform operation on it as well…in this way i have to perform operation on all elements of array and have to output the minimum total cost …
how can i use dp in this case ??
You have initial power x and have n enemies from 1 to n with power equal to array[i]…
You can kill only 1 enemy in one day and if your power is less than enemy power…enemy power fill again be restored to original power …but your power after every blow to a enemy will double…you can only give a single blow to your any one enemy every day
However after killing that enemy your power will become 2wice that of enemy power and next day this will be your starting power…
Output the min no of days to kill all enemies…
Eg n=6. X=7
10 20 30 50 200 40
Output expected:8 days
Explanation: you can decide to kill first enemy having power 10…
It will take you 2 days to kill him as first day you can give a blow of 7 and next day since your power doubles … therefore you can strike your enemy.(whose power will become original if he is not killed properly) with blow of 14 which will kill him as his new power was 10 …now your power will be 20 for next day as you have killed him…
Then you can directly kill enemy with power 20 in 1 day…as you have power 20…
Then you can strike the partner with power 40 in 1 day as your power will be 40 …after killing your power will be doubled to 80 …
You can killl then 200 peer enemy in 3 moves and then you can target 50 and 30 power enemies …in one days each respectively…
Therefore total days will be 8 days…and this will be min ans …
Note :Many other configurations of killing might give the same result…fir example if you start by trying to kill 20 power enemy right at the start …
array may contain duplicates as well…
@S19LPPP0202 do you have any link? It seems very similar to a question from Codechef’s july long contest, which is an ongoing contest. Doctor Chef to be precise.
oh yes i didnt correlate this question with that …
thanks i will clarify this question after the contest on codechef ends…
i also have a doubt regarding egg drop problem on which ta has stopped responding plz reply to that as well.
also tell me a good source from where i can practice graph problems as hackerrank is too difficult along with hackerearth
how to explore development side plz tell bw webd and app and machine where to learn and explore??
@S19LPPP0202 the TA has already responded to your many doubts on that thread…if you still have doubts left you can open another doubt telling exactly what you are confused about so the TAs can help you better.
Students generally find graph problems difficult so dont give up keep trying…
but they are too hard problems i want to start from medium leevel atleast
@S19LPPP0202 practice the problems/challenges given in the course and get your basics clear. Other than that you can refer to geekforgeeks they have articles on almost every topic and cover a lot of common questions.
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.