dmkz's blog

Dynamic programming problem
By dmkz, history, 6 years ago, translation, In English

Hello, codeforces! I do not know how to solve this DP problem, so I really want to know how. I will explain the condition of this problem briefly. Link on original pdf with examples.

On our way we will meet several groups of bandits (from 1 to 20). Each group has two parameters:

  1. size[i] — number of bandits (from 1 to 1000)
  2. cost[i] — cost we have to pay them if we do not want to have problems (from 1 to 1000)

We can:

  1. Pay them cost[i] to pass them

  2. Pay them 2 * cost[i] to hire them

  3. Fight them. In this case we will lose size[i] hired soldiers. The first to die are those who had been hired earlier. The hired mercenaries leave our squad after participating in three battles.

You need to go all the way, having spent the least amount of money. Answer — this amount. At the initial time in our squad there are no soldiers.

The input file contains from 1 to 50 tests. On each input file, time limit — 3 sec, memory limit — 256 MB. Therefore, for one test — 0.06 sec. Tests can be different, numbers cost[i] and size[i] can be different.

I tried to apply two-dimensional dynamic programming:

  1. k — Number of passed groups.

  2. sum — The amount of money spent

The cell dp[k][sum] contains the best triple of the mercenaries (n1, n2, n3), who can fight in one battle, two and three battles. But I can not understand how to choose the best triple among all the transitions.

If we use sum of components, triple (1000, 0, 0) will be better, then (0, 0, 999), but after battle with size[i] = 1 we get (0, 0, 0) from first and (0, 998, 0) from second triple and second will be better.

If we use lexicographic order, triple (0, 0, 1) will be better, then (1000, 0, 0), but first triple can not win in battle with size[i] = 1000 bandits.

I ask you to help finish this problem to the end and, if possible, provide links to similar problems.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by dmkz (original revision, translated revision, compare)

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

Auto comment: topic has been updated by dmkz (previous revision, new revision, compare).

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

struct orcState {

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

    Can you describe the algorithm with the orcs (bandits) states in details for evaluate complexity of solution? Naive with states for each groups get TLE because 320 = 3486784401 is very large number of states.

    → Reply
»
6 years ago, # |
← Rev. 31   Vote: I like it -10 Vote: I do not like it

The following Solution seems to have a reasonable execution time.

Starting with a set of candidate partial solutions that contains a null initial state and an INT_MAX upper bound for the minimum cost, the required solution is the value of the upper bound when the set of partial solutions is empty. The iterative progress through the groups adds a new partial solution to the set only if its present cost is less than the present upper bound.

Hope that this helps.

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

    Beautiful code style! But this is not full solution.

    WRONG ANSWER: This counter-test — WA is 7, but true answer is 6:

    1. hire. state = (0, 0, 2), amount = 2.
    2. hire. state = (0, 0, 4), amount = 4.
    3. pass. state = (0, 0, 4), amount = 5.
    4. pass. state = (0, 0, 4), amount = 6.
    5. battle. state = (0, 3, 0), amount = 6.
    6. battle. state = (2, 0, 0), amount = 6.
    7. battle. state = (0, 0, 0), amount = 6.

    TIME LIMIT EXCEEDED: This counter-test takes greater then one minute (65.959 sec) — TLE. In this test, each of the 50 sets of input data is different.

    This problem from coding interview in Samsung company.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      I don't know how to solve it normal, but wrote the same brute O(3n). It isn't TLing for 50 random testcases you provided, also works on samples. I believe, that this solution may works quite good on random testcases, but can be hacked with some special situations.

      https://ideone.com/qAsgd6

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

        Thanks! This is simple TLE test. We get TLE when we can fight with each group from each state.

        Maybe normal solution is recursion with memoization or partial memoization or dynamic programming over subsets. Maybe there are very few very worst tests, and we can make a preliminary calculation.

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

          edited!

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

            Nice! This is not O(3n), because in the sequence of actions, a word "fight" can not be contained more than three times in a row.

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

            1.340.895.616 in worst case if we not hire last group, not fight with first group and not fight more than 3 times in row

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

              Comment below. It's will works bad (O(3n)), when solution is hire all, but fight last.

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

                On test

                1
4
1 1
1 1
1 1
3 1000

                your code gives incorrect answer 1003 (because you modify variables orc1, orc2, orc3 when you choose "fight" option, but you then use new values instead of old in other options). After fixing this bug, your code works >2s on my computer on this single test:

                1
20
1 1
1 1
...
1 1
19 1000

                And shuffling transition order won't help, because answer is 38 and it is impossible to spend more than 38 coins on first 19 operations no matter what you do, so you never actually cut any useless branches.

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

                3.46 sec and 1 327 729 094 calls on this single test after fix bug

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

      Thanks for the kind words.

      For the first counter-test, replacing set< state_t > in line 48 with multiset< state_t > generated the expected output.

      The second counter-test with TLE result requires further checking.

      → Reply