PubTrivia
SRM 395 · 2008-03-26 · by connect4
Problem Statement
You and your friends have gotten together for a Trivia night at the local pub. There are N questions asked during the night. Each question is worth a number of points; the i-th element of the points array corresponds to the score received if you correctly answer the i-th question, but you lose that many points if you answer it incorrectly. The questions are given in the order specified, and you must answer each question before the next is asked.
In addition, after each correct answer you will receive a token. If you then have tokensNeeded tokens, the pub will immediately take all of your tokens and award you additional bonus points. However, if you get the question wrong, the pub will take away all of your tokens without giving you any bonuses. The bonuses change after each question; element i of the bonuses array corresponds to the bonus you receive if you win the bonus on question i. Note that it is possible to receive multiple bonuses during the game.
To generate the arrays points and bonuses described above, you should use the following pseudo-code on the arrays p and b, respectively.
Input array: X Output array: P (size N) k := 0 M := size of X For i=0 to N-1 P[i] := X[k] s := (k+1)%M X[k] := ( ( X[k] ^ X[s] ) + 13 ) % G k := s
In the above code, use the value 1001 for G when generating points, and 10001 when generating bonus; this guarantees that all questions will be worth between 0 and 1000 points, inclusive, and that all bonuses will be worth between 0 and 10,000 points, inclusive. In the above code, % represents the modulo operator, and ^ is the binary XOR operator (see the Notes section for the implementation in your language).
You know the answer to all the questions and want to maximize the number of points that you receive. Return the maximum points that you can receive if you correctly choose which questions to answer.
Notes
- The input is only coded for convenience. The intended solution does not rely on any property of the number generation; it just generates both arrays and works on them.
- If x and y are ints, (x^y) represents the bitwise XOR operation on them in C++, Java, and C#. In VB.net, (x BitXor y) does it.
Constraints
- N will be between 1 and 500,000, inclusive.
- tokensNeeded will be between 1 and 500,000, inclusive.
- p and b will each contain between 1 and 50 elements, inclusive.
- Each element of p will be between 0 and 1000, inclusive.
- Each element of b will be between 0 and 10000, inclusive.
5
5
{1, 2, 3, 4, 5}
{0, 0, 0, 2, 5}
Returns: 20
The best strategy here is to answer all five questions correctly. You score 15 points for the questions, and a 5 point bonus for answering five questions in a row.
5
3
{1, 2, 3, 4, 5}
{0, 0, 0, 2, 5}
Returns: 16
This time, it is best to answer all of the questions correctly except for the second question. You then receive the bonus on the final question for answering three in a row.
5
3
{1, 2, 3}
{7, 0}
Returns: 98
Here the question values are {1, 2, 3, 16, 14}, and the bonuses are {7, 0, 20, 33, 66}.
500000
12
{1, 34, 643, 293}
{2938, 398, 103}
Returns: 477926801
Large test case, runs in 0.27 secs
4
4
{998, 1}
{9998, 1}
Returns: 1056
1
2
{0, 323, 35, 239, 358, 3}
{0, 238, 23}
Returns: 0
Minimal return
500000
1
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,
1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,
1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,
1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,
1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}
Returns: 2277323685
Long required return value
500000
1
{1000,999,1000,998,1000,997,1000,999,1000,998,
1000,999,1000,998,1000,997,1000,999,1000,998,
1000,999,1000,998,1000,997,1000,999,1000,998,
1000,999,1000,998,1000,997,1000,999,1000,998,
1000,999,1000,998,1000,997,1000,999,1000,998}
{10000,9999,10000,9998,10000,9997,10000,9999,10000,9997,
10000,9999,10000,9998,10000,9997,10000,9999,10000,9997,
10000,9999,10000,9998,10000,9997,10000,9999,10000,9997,
10000,9999,10000,9998,10000,9997,10000,9999,10000,9997,
10000,9999,10000,9998,10000,9997,10000,9999,10000,9997}
Returns: 2290771387
Long required return value
Submissions are judged against all 89 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PubTrivia with a public method long long maximumScore(int N, int tokensNeeded, vector<int> p, vector<int> b) · 89 test cases · 2 s / 256 MB per case