Hello Frends ,
This problem is from the last hack contest on hackerrank. Here is the link
Problem Statement
HackerRank is conducting a teamed programming contest. The rules of the contest are a bit different than usual:
A team consists of exactly N members. Problemset contains exactly N problems and each team member must solve exactly 1 problem. Only one member from the team is allowed to read the problem statements before the contest start time. Note that not everyone have read the problems at first. So, to solve problems a member needs to know the statements from some teammate who already knows them. After knowing problems once, a member is eligible to explain them to other teammates ( one teammate at a time ). You can assume that the explaining ( 1 or N problems ) will always take D minutes. During explaining, none of the two involved members will be able to do anything else.
Problems are of different difficulty levels. You can assume that it will take Ti minutes to solve the ith problem, regardless of which member solves it.
Given a team's data, what is the minimum possible time in which they can solve all problems?
Input Format
The first line will contain T, the number of test cases. The first line of each test case will contain space-separated integers N and D. The second line will contain N space-separated integers, where the ith integer denotes Ti.
Constraints
1≤T≤20
1≤N≤3×10^3
1≤Ti,D≤10^9
Output Format
For each test case, output the minimum possible time in which the given team will be able to solve all problems in a separate line.
Sample Input
1
2 100
1 2 Sample Output
102
Explanation
Member 1 is allowed to know problems before start time. He starts explaing problems to member 2 when contest starts. Explaining ends at the 100th minute. Then both of them immidiately starts solving problems parallely. Member 1 solved 1st problem at the 101th minute and member 2 solved 2nd problem at the 102th minute.
I have also copied problem statement along with the problem link. I am just unable to solution mentioned in the editorial. Also it is mentioned this problem can be solved with better complexity :). I am interested in learning both approaches. If anyone of you can help me :).
Idea behind solution with better complexity: use binary search. For me this one sounds even easier and more natural than intended N^2 solution.
When you have fixed deadline inside binary search, for every team member you have obvious strategy — he should explain statement to his teammates as long as he will have enough time to solve a problem by himself after that (and while there are still some teammates who don't know problem statement). You can simulate this process in linear time. Everything is OK if every team member have enough time to solve his problem, otherwise you need to set higher deadline.
Sounds Cool :)
Yeah i got the idea behind and yes it is easier than intended solution. But still i want to learn that Dynamic Programming Technique used to solve this problem. Can you help me on this ? Meanwhile i am coding binary_search solution and get back to you in a while :)
check out my comment here :)
Hello I_love_Tanya_Romanova ,
Can i have a look at your implementation for this problem ? My implementation took O(Nlog^2(N)) time as i am using multiset container inorder to get the time for a contestant ( minimum time when he come to know about statement ) .
Sorry for the inconvenience. At the point where i was using multiset a simple queue is enough which boils down complexity of this problem to O(N*log(N)).