SRM 740, D1, 500-Pointer (DieDesign)

James S. Plank

Fri Oct 26 17:14:02 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: October, 2018
Competitors who opened the problem: 155
Competitors who submitted a solution: 128
Number of correct solutions: 78
Accuracy (percentage correct vs those who opened): 50.3%
Accuracy (percentage correct vs those who submitted): 60.9%
Average Correct Time: 22 minutes, 12 seconds.

In case Topcoder's servers are having issues, here is a summary of the problem:

You are given a vector of integers called pips.
Yves has a die, and the number of pips on the die are given by pips.
Zola is supposed to create a die with the same number of sides as Yves' die, and the same total number of pips.
Zola wants to design her die to maximize the probability that if she and Yves each throw their dice, her die has more pips showing that Zola's die.
Return a vector of its representing Zola's die. If there are multiple die that have the same maximum probability, then you can return any of them.

You can look at the main() for the examples. Here are correct answers:

Example 0: { 0, 0, 0, 7, 7, 7 }
Example 1: { 0, 0, 1, 1 }
Example 2: { 4, 4, 4, 4 }

This sure feels like it will be solved with Dynamic Programming. When I did this one, I had everything correct, except in an effort to reduce CPU time, I made my DP cache too big, which had the opposite effect. Drag.

The first observation to make is that the only number of pips that you should put on Zola's die are either zero, or one more than the pips on Yves' die. For example, on problem #2, Yves die has the pips { 1, 1, 13, 1 }. The only pips that Zola should consider for her die are { 0, 2 and 14 }. Why? Well, is there any benefit to having a side with 3 pips? It beats the same number of sides on Yves' die, and it's more "expensive."

So this is the first part of our solution -- let's just consider those values for Zola's die, and then when we're done, if there are any pips "leftover", we'll simply add the to an arbitrary die. Continuing with problem 2, it should be clear that the best solution with the pips { 0, 2 and 14 } is { 2, 2, 2, 2 }. There are 8 pips leftover, so we can arbitrarly add them to the first die, and give an answer of { 10, 2, 2, 2 }.

Now, each pip value has a number of sides of Yves' die that it beats. Let's store that. In fact, let's talk data structures -- let's have a vector ZP, of pips that Zola's die can have, and a second vector LT such that LT[i] contains the number of pips on Yves' die that ZP[i] beats. Here are the two vectors for the examples (I've put a difficult example into example 12):

UNIX> Example 0
ZP:    7    6    5    4    3    2
LT:    6    5    4    3    2    1
UNIX> Example 1
ZP:    3    1
LT:    4    3
UNIX> Example 2
ZP:   14    2
LT:    4    3
UNIX> Example 12
ZP: 4820 4783 4718 4702 4473 4221 4210 4180 3804 3357 3305 3069 3047 2908 2883 2760 2709 2518 2438 2308 2002 1753 1734 1449 1214 1121  238   71
LT:   28   27   26   25   24   23   22   21   20   19   18   17   16   15   14   13   12   11   10    9    8    7    6    5    4    3    2    1

The problem is now to choose N values from ZP such that their sum is less than or equal to the total number of pips on Yves die, and the sum of their LT values is maximized.

Dynamic programming

Time to play "spot the recursion." This is what I got wrong the first time. So, I'll help you out:

int DieDesign::fill_in(int index, int pipsleft, int makevec);

This returns the number of sides that Zola's die beats, starting at index index of the die, when she has pipsleft pips left to allocate to those sides. The parameter makevec is a boolean (I know -- I'm old and just use ints). If it's false, you just return the value. If it's true, you also set a vector to be the vector of pips).

You call it initially as fill_in(0, totalpips, 1). Then, you see how many pips are leftover, and add them to the first die. You only memoize when makevec is zero, and what that allows you to do is figure out what the best recursive call is to make, before you make that call with makevec equal to one, so that you get the answer. You memoize on the first two parameters -- 30 * (5000*30) = 4,500,000 -- this is pretty much just at the limit of what Topcoder can do. Use a two dimensional vector, and not a map.

Here are the calls and caches for examples 1, 2 and 0. I only print out cache entries that were set.

UNIX> a.out 1
ZP:    3    1
LT:    4    3
Final rv: 6

Here's the Cache
 index:  0   pipsleft:      2        RV:    6
 index:  1   pipsleft:      1        RV:    3

And here's the final answer:
1
1
0
0
UNIX> a.out 2
ZP:   14    2
LT:    4    3
Final rv: 12

Here's the Cache
 index:  1   pipsleft:      2        RV:    3
 index:  4   pipsleft:     16        RV:   12

And here's the final answer:
10
2
2
2
UNIX> a.out 0
ZP:    7    6    5    4    3    2
LT:    6    5    4    3    2    1
Final rv: 18

Here's the Cache
 index:  0   pipsleft:     21        RV:   18
 index:  1   pipsleft:     14        RV:   12
 index:  1   pipsleft:     15        RV:   12
 index:  1   pipsleft:     16        RV:   13
 index:  1   pipsleft:     17        RV:   14
 index:  2   pipsleft:      7        RV:    6
 index:  2   pipsleft:      8        RV:    6
 index:  2   pipsleft:      9        RV:    7
 index:  2   pipsleft:     10        RV:    8
 index:  2   pipsleft:     11        RV:    9
 index:  2   pipsleft:     12        RV:   10
 index:  2   pipsleft:     13        RV:   11
 index:  3   pipsleft:      1        RV:    0
 index:  3   pipsleft:      2        RV:    1
 index:  3   pipsleft:      3        RV:    2
 index:  3   pipsleft:      4        RV:    3
 index:  3   pipsleft:      5        RV:    4
 index:  3   pipsleft:      6        RV:    5
 index:  3   pipsleft:      7        RV:    6
 index:  3   pipsleft:      8        RV:    6
 index:  3   pipsleft:      9        RV:    7
 index:  4   pipsleft:      1        RV:    0
 index:  4   pipsleft:      2        RV:    1
 index:  4   pipsleft:      3        RV:    2
 index:  4   pipsleft:      4        RV:    3
 index:  4   pipsleft:      5        RV:    4
 index:  5   pipsleft:      1        RV:    0
 index:  5   pipsleft:      2        RV:    1

And here's the final answer:
7
7
7
0
0
0
UNIX>

One final thing -- if you're looking at ZV[i] and pipsleft/(N-index) ≥ ZV[i], then you can return instantly -- you don't need recursion. That observation might be necessary to have your program work fast enough.