http://codeforces.net/gym/100494/attachments
Here is the link of the contest problems, I want to discuss problem F here. People have made very few submissions for this problem, may be just because its difficult to catch the greedy part here.
Anyways, never mind. I gave it a try like everyone else did and thought of a backtrack solution. http://ideone.com/8h8X4v (This is the link for my code).
I dont know how to mantain a state here.
The only state I can think of is F(t,mask,vector spent) where t denotes time elapsed till now, mask denotes which all bugs have been fixed (set bits for the fixed bugs) and vector spent would denote an array which would keep the count as in how much time, we have wasted on ith problem.
But, seems the problem can be solved by keeping a different state. Instead of vector spent, they say, you can just keep an overall time elapsed on fixing all the unfixed bugs, why is it so!
this code can get TL, but I hope the main idea is clear.
Thanks for your reply Alias, Main idea is crystal clear to me, but seems even your implementation causes runtime error.
I guess, we need a better implementation of the algorithm you implemented. :)
dp[1 << B][T]; -> dp[1 << B][T * B];
O(T^2 * B * 2^B) code
Thanks a lot Alias, you were a great Help. GOT AC! :) This is my code.(Link below) http://codeforces.net/gym/100494/submission/8234513
"You are not allowed to view the requested page"
My Bad! http://ideone.com/S15DiP (You can have a look here, Alias)
what is cnt? try to submit this code