bluemmb's blog

Training Private Ryan ( LA 5976 )
By bluemmb, 8 years ago, In English

Can you help me solve this problem ? ( original source )

Thanks in advance.

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

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have an idea to solve this problem but I"m not sure if it is right.

First we take the ranges and scores and decompose them into non-overlapping ranges with unique maximum scores. It is easy to see that we only care about these ranges.

Notice that an optimal part of the solution will always start at a time which is the same modulo L as a start of a range. Otherwise, we can shift this optimal part backwards by 1 and it will still have the same score.

Therefore we can use a straightforward DP, state is dp[node][modulo] and recurrence is either N^4 or N^3 (I think this is possible). Notice that there are only O(N) modulo's as proven above.

I'm not sure if this is correct but I'm 90% sure :P Unfortunately I don't have enough time to implement it.

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

    Thanks so much. Sorry I was too busy these days... now I am working on your solution. I will report the result.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    According to your approach we keep a dp which it's first dimension is for range number and second one is for module. Then sorry I can't get that where we store the remained bullets in dp?

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

      Hi bluemmb, it seems that I have misread the question! Sorry about that :) Now that I think about it I think you may be able to do some smart thing by going in decreasing score and taking either the full range or full range minus one (in order to fit with others). I am lost! Sorry.

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

        Hi gongy, I worked on your greedy approach in multiple ways but I stuck with this case :

        N = 2 ( bullets )
L = 3 ( reload time )

Range   Score
1..2    9
2..3    10
3..4    9

        As you said we will fill the second one because it has highest score but then we can't choose anything else, so we will get 10 scores.

        But we could shot at times 1,4 and got 18 scores.

        Am I missing something ? thanks again.

        → Reply