MciprianM's blog

Please give a hint at a problem.
By MciprianM, 14 years ago, In English
At ACM ICPC SEERC 2009 was this problem:
   Problem E.
I need a hint to solve it. My instinct tells me that some sort of dynamic programming would do. But I can't figure it out.
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
The idea suggested by MBabin (check the comments in Russian) looks correct: let d[i][j] be the time needed to finish the last i procedures of application 1 and the last j procedures of application 2. The transition is O(N) with two pointers: suppose you have chosen to run application 1 first. Then you either wait until its procedure finishes or run application 2 simultaneously.
However, the time limit is tough and some optimizations are needed.
Here is the code that got accepted on this online judge.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    It doesn't look like an optimized one but the original solution with memoized recursion times out despite being essentially the same as this one. There are a lot of tests there.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Oau!! Thanks a lot! I learnt lots of things from your comment. I didn't know this problems were on an online judge(I've got solutions for the first four, now all I need is to send it). This will save me a lot of time. Also I didn't know I have to check both codeforces sites(.com and .ru) so I didn't see MBabin's comment. Also last night I thought of a solution so I will try to implement it before I read your solutions. Thanks a lot. You speak romanian don't you. (Sad girls?)
→ Reply