Блог пользователя bluemmb

Training Private Ryan ( LA 5976 )
Автор bluemmb, 8 лет назад, По-английски

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

Thanks in advance.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить