shibly's blog

uva : 11913 - Tape Recording
By shibly, 14 years ago, In English

How I will be able to solve the problem ?

Here is the link:

11913 - Tape Recording

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

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This seems similar to Job Scheduling Problem with cost. As n is quite small, ( < 100 ) an O(n^3) solution should work.
The only thing which makes it a bit complicated is the fact that there are two tape recorders...
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This is my main Problem. Thanks rufferzool.
→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it
A dynamic programming solution should word here. For example calculate f(current, first, second) where current is the current time and first is the earliest time which the first VCR is available, and the same is for second. It can be easily computed.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Can you explain the recurrence relation ? 
    Thanks havaliza.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      ask_1171's implementation is what I tried to say.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        but can u please clear me the range of start time and end time ? may be this is the reason i am not getting accepted. 
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    A day of TV broadcasting starts at 6 am. All TV programmes listed in the input are on the same day, and none will encompass 6 am."

    can u please explain what does this line say ?? shud the time not be the range between 0600-2399 to be in the same day ??  or there can be something like 2300-0250 ??

    any way i did the dp as u said but still cannot manage ac. :(..

    any way my relation was like..

    dp(item,tape1,tape2)
    {
        if(item==n)
        return 0;
       
      // items (tv programs )are sorted in ascending order of starting time;
      // tape1 contains the earliest positioned item it can record so as tape2
      // next array contains the next compatible item for a tape..if present item is taken
      
      if(item>=tape1)
           a=dp(item+1;next[item],tape2)+weight of item
        if(item>=tape2)
            b=dp(item+1;tape1,next[item])+weight of item
           c= dp(item+1,tape1,tape2);

          return max of a,b,c;

    }
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks ask_1171.
      I have got AC.

      I substract 360 minutes from every time.
      If it become negative then I add extra 1440 minutes to it.

      If time is  HH:MM.
                t=HH*60+MM-360;
                if(t<0)t+=1440;

      Again thanks havaliza.

      May Allah help you.

       


      → Reply