SRM 814, D1, 250-Pointer (StepLeapSurviveTraps)

James S. Plank

• Problem Statement.
• A main() with the examples compiled in. Use "-" to enter the parameters on standard input.
• A skeleton that compiles with main.cpp.
• tests.sh
• answers.txt

• Problem Given in Topcoder: September, 2021
• Competitors who opened the problem: 72
• Competitors who submitted a solution: 70
• Number of correct solutions: 64
• Accuracy (percentage correct vs those who opened): 88.89
• Average Correct Time: 19 minutes, 48 seconds.

In case topcoder's servers are down

• You are given numbers N, J, seed and M.
• 1 ≤ N ≤ 500,000.
• 1 ≤ J ≤ 500,000.
• 1 ≤ seed ≤ 2^<31
• 1 ≤ M ≤ 10^<9
• You are given code to generate a vector of ints, T, whose size is N+1.
• You are playing a game on T:
  • You start at T[0] and want to end at T[N].
  • If you are at position T[i], you may jump to any T[j] such that j-i ≤ J.
  • Your score is the sum of all the T[i] that you land on (including T[N]).
• What is the minimum score that you can achieve?

  T.push_back(0);
  state = seed;                    // state is declared as a long long
  while (T.size() <= N) {
    state *= 1103515245LL;
    state += 12345LL;
    state &= 0x7fffffff;
    T.push_back((state % M) + 1);
  }

Examples:

i                0   2   4   5   6
T[i]             0   6   2   1   8
running score    0   6   8   9  17

Testing yourself

Hints - Why Dijkstra's Algorithm Isn't Likely To Work

The first solution that came to mind for me was a graph-based solution. Each T[i] is a node on a graph. You have an edge from each T[i] to T[j] such that (j-i) ≤ J. That edge's weight is T[j]. Then, you solve the problem by finding the shortest path through the graph, using Dijkstra's Algorithm. O(E log V).

The graph is directed and acyclic, BTW. So you can use Topological Sort, too: O(E)

The problem is that J can be as big as N, so the graph can have O(N²) edges. With N being as big as 500,000, that won't do, for both Topological Sort and Dijkstra's algorithm. I tried to think of ways to reduce the number of edges, but nothing good came to mind.

Hints - How we can use a multimap to our advantage

• You're going to iterate through T from i=0 to i=N, and while you do so, you'll create the vector B, such that B[i] is the cheapest path to node i.
• While you do this, you are going to maintain a multimap whose (key,val) pairs are (B[i],i).
• When you are looking at T[i], you look at the first element on the multimap -- that's the cheapest element to go to.
• If this element is too far away from you, delete it from the multimap.
• Keep doing this until the first element on the multimap is one that is within J spots of you. Let that element's index be e. The cheapest path to i will be from e.
• Set B[i] to be T[i] + B[e], and now you can add (B[i],i) to the multimap.
• The answer will be B[N].

When we're done, the answer is B[8], which is 17.

Running Time Analysis

Another Two Interview Questions

To answer this, think about the operations that you're doing on the multimap.

Scroll down for the answer.

• Insert.
• Look at the minimum element.
• Delete the minimum element.

• Insert: O(log n)
• Look at the minimum element: O(1)
• Delete the minimum elementr: O(log n)

More examples to help you

UNIX> echo 15 7 92559 49386490 | ./a.out -
17007267
UNIX> 

UNIX> echo 20 5 92559 46386490 | ./a.out -
17007267
UNIX> 

UNIX> echo 50 10 559 46386495 | ./a.out -
17007267
UNIX>