Problem Statement
One of the biggest challenges after marriage is deciding who will do which of the chores in the household. Our lucky bride and groom decided to settle each of these questions by playing a game.
They will play many different versions of the game. Each version of the game will start by looking at the same weighted tree. The tree has N vertices, numbered from 0 to N-1. When rooted at vertex 0, we will the parent of vertex i will be denoted parent[i] and the weight of the edge i-parent[i] will be denoted weight[i]. The tree can be generated using the following pseudocode:
def rnd():
state = (state * 1103515245 + 12345) modulo 2^31
return state
# generate the parents of vertices other than 0
for i = 1 to N-1:
parent[i] = max( 0, i - 1 - (rnd() % D) )
# prepare a bank of some edge weights that will appear frequently
bank = empty sequence
for i = 0 to B-1:
bank.append( rnd() % N )
# assign edge weights
for i = 1 to N-1:
if rnd() % 100 < P:
weight[i] = rnd() % N
else:
weight[i] = bank[ rnd() % B ]
Please make sure to generate the data in the given order: all parents, then bank, then all weights.
For each game the bride and groom will select four parameters: (U, V, hi, lo). The game will be played on the path from vertex U to vertex V in their tree. The players will be covering some of the edges of this path by tokens.
The players take alternating turns, starting with the bride. In each turn the current player must choose an edge on the path that has no token yet and place a token onto that edge.
During the game the players maintain a single value called X. At the beginning of the game X = hi. When a player chooses an edge, they must choose an edge whose weight is at most X. Once they place the token onto that edge, X becomes equal to the weight of that edge.
The player who cannot perform a valid move loses. Also, the player who is forced to make X strictly less than lo (by placing a token onto an edge with weight smaller than lo) loses the game.
You are given a sequence of queries. Each query has the form (U, V, hi). For each query q, compute answer[q] = the number of values lo in the range [0, hi] such that the groom will win the game if both the bride and the groom play optimally. Return the sum of answers to all the queries.
There are Q queries. Use the following pseudocode after you already generated all other data to generate them. (The order matters because each call to rnd() changes the state of the pseudorandom generator.)
for q = 0 to Q-1:
U = rnd() % N
V = rnd() % N
hi = rnd() % N
make a query (U, V, hi)
Definition
- Class:
- MarriageAndGamingChallenge
- Method:
- solve
- Parameters:
- int, int, int, int, int, int
- Returns:
- long
- Method signature:
- long solve(int N, int D, int state, int B, int P, int Q)
- (be sure your method is public)
Constraints
- N will be between 2 and 100,000, inclusive.
- D will be between 1 and N, inclusive.
- state will be between 0 and 2^31 - 1, inclusive.
- B will be between 1 and N, inclusive.
- P will be between 0 and 100, inclusive.
- Q will be between 1 and 200,000, inclusive.
Examples
7
2
47474747
2
50
9
Returns: 10
When generating the tree we will generate these arrays, in the given order: parent = {None, 0, 0, 2, 2, 4, 4} bank = {2, 6} weight = {None, 1, 6, 2, 6, 5, 6} The queries are: query 0: 5 3 4 query 1: 2 5 6 query 2: 4 3 0 query 3: 5 0 5 query 4: 2 5 2 query 5: 4 0 1 query 6: 3 1 3 query 7: 1 6 6 query 8: 0 0 0 The answers to the individual queries, in the given order, are as follows: 2, 0, 1, 0, 3, 2, 1, 0, 1. Query 0: If lo is in {0, 1, 2}, the bride places a token onto the edge 2-3 (weight 2) and the groom loses the game. If lo is in {3, 4} the bride has no valid move and loses the game. Hence, the groom wins for two choices of lo. Query 1: For any lo in [0,6] the bride wins. If lo=6 she places her first token onto the edge 2-4 (weight 6), in all other cases she places her first token onto the edge 4-5 (weight 5). In either case the groom loses immediately. Query 2: The value of lo must be 0. The bride has no valid move and thus she loses the game and the groom wins. Query 7: The edges on the path 1-6 have weights {1, 6, 6, 6}. The bride always wins. If lo is in [0,1] she places her token onto the edge 1-0 (weight 1) and the groom loses. If lo is in [2,6] the bride places her token on any one of the three edges of weight 6, the groom onto another, the bride then covers the third edge and then the groom loses the game. Helpful data for checking that you have the correct instance: The values weight[2] and weight[4] were chosen from the bank, all other were chosen at random. The function rnd() returned the following sequence of values: 81038168, 1862554801, 143404438, 831999255, 766706948, 1708690157, 2010484002, 1631167411, 81620336, ...
7
2
47474747
1
0
9
Returns: 23
This is the same tree but now every edge has weight 2. The individual answers are 4, 3, 1, 1, 6, 1, 2, 4, 1.
100000
1
47
10
10
100000
Returns: 13264051
5000
2
47
3
0
5000
Returns: 6462069
1000
10
47
5
1
3000
Returns: 800879
100000
10
47
10
10
200000
Returns: 142083211
100000
10000
47
1
100
200000
Returns: 1039136720
100000
100000
47
10
3
200000
Returns: 5173889603
97882
14
1948501517
32
3
197895
Returns: 270902177
99923
17540
539016619
12
3
199985
Returns: 4055913661
99234
1
907804592
13
1
195341
Returns: 2316868768
96150
2029
863925910
10
66
195725
Returns: 363108901
97479
6
1027003835
1
3
199442
Returns: 206822182
98954
62
1554617535
1
51
196014
Returns: 92230007
96390
25005
1344280466
10
48
198976
Returns: 2491865556
95759
2023
1036425125
20
20
199825
Returns: 866673747
98225
2
581846500
1
60
199774
Returns: 10783072
96016
53
1877567921
6
6
195362
Returns: 448587444
95051
55356
825599650
3880
1
196562
Returns: 2974038685
98418
15
1145921960
10
0
195935
Returns: 5121343718
99952
46727
1600605750
3
0
195895
Returns: 5083003229
95168
2
1646888126
2
7
198796
Returns: 65255994