Xsquare's blog

By Xsquare, 10 years ago, In English

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!

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

this code can get TL, but I hope the main idea is clear.