Problem Link : link
code link : code
In the bfs part I am extracting nodes at a given level and then in help function I am greedily sorting the CT and TT by CT time in acsending order as we want the developer to finish the module code asap so that the tester can attend to it. Also I believe that it doesn't matter if we process level 1 first and then subsequent levels as I am adding the time of each level to my answer. Why is this code giving WA. Any help is appreciated.
P.S- No one was able to solve this problem in the contest and thus it seems an interesting problem.
Link for your code is private. Can you share it through ideone or pastebin?
I don't fully understand your explanation. By level you mean some depth (distance from the root)? We shouldn't group by that. The problem looks like bottom-up dp on tree.
If you don't know why your solution is wrong, write a brute force and compare them on random tests. More info: Asking for help FAQ.
Yes by level I mean depth.
Can you please tell if the code to solve the subproblem is correct or not.
Sub problem: given developer time array and tester time array find minimum time to completely develop and test all modules and tester can only test a module provided developer has coded it.
My approach : Sort both arrays according to developer time in increasing order because we want to develop modules asap so that the tester can test it asap. Can you provide a counter case where my approach fails . Here is the code I am taling about.
...
ll help(vector &v)
{
vector < pair <ll,ll> > a; rep(i,0,v.size()) a.push_back(vp[v[i]]); sort(a.begin(),a.end()); vector <ll> d(a.size()),t(a.size()); rep(i,0,a.size()) { d[i]=a[i].first; t[i]=a[i].second; } rep(i,1,a.size()) d[i]+=d[i-1]; ll s=0; s+=d[0]; rep(i,1,a.size()) { s+=t[i-1]; if(s<d[i]) s=d[i]; } s+=t.back(); return s;}
d array is for developer and t array is for tester and a array is just storing the pairs of developer tester time for facilitating sorting.
I told you to test it against a brute force...
It's incorrect. One item with develop=10, test=1, the other develop=11,test=10.
hello.......
I told you two times what to do. I'm not going to help you more before you do that.