BPM2  Bipartite Permutation (Hard)
Given a positive integer N, consider any permutation of all the numbers from 1 to N. It is required to create two partitions, P_{1} and P_{2}, from these numbers such that sum(P_{1}) – sum(P_{2}) is minimum, where sum(X) denotes the summation of all the numbers in partition X. A partition is defined to be a nonempty subset of the permutation. In other words, find the minimum absolute difference between the summation of all the numbers in each partition. Note that you cannot leave out any number, every number from 1 to N must be part of exactly one partition.
To add a little bit more of spice, also find the lexicographically smallest partition P_{1} such that sum(P_{1}) – sum(P_{2}) is minimum. To make your life easier, you don’t need to output the entire sequence, only the hash of the sequence as computed by the function below would suffice.
1 ≤ T ≤ 1000
2 ≤ N ≤ 10^{9}
N < B ≤ 10^{9}
1 ≤ M ≤ 10^{9}
Bipartite Permutation
To add a little bit more of spice, also find the lexicographically smallest partition P_{1} such that sum(P_{1}) – sum(P_{2}) is minimum. To make your life easier, you don’t need to output the entire sequence, only the hash of the sequence as computed by the function below would suffice.
def sequence_hash(sequence, B, M): result = 0 for number in sequence: result = (result * B + number) % M return result
Input
The first line contains an integer T, denoting the number of test cases. Each of the next subsequent T lines contain three positive integers, N, B and M.Constraints
Output
For each test case, first print the case number followed by the minimum absolute difference and the hash of the lexicographically smallest partition P_{1}.Sample Input
12 2 10 1000000000 3 10 1000000000 4 10 1000000000 5 10 1000000000 6 10 1000000000 7 10 1000000000 8 10 1000000000 9 10 1000000000 1000 1000000000 1000000 1000000 1003001 998244353 123456789 987654321 666666667 444444444 666666666 888888888
Sample Output
Case 1: 1 1 Case 2: 0 12 Case 3: 0 14 Case 4: 1 124 Case 5: 1 1234 Case 6: 0 1247 Case 7: 0 12348 Case 8: 1 123457 Case 9: 0 1000 Case 10: 0 553178755 Case 11: 1 214459309 Case 12: 0 557434257
Challenge
Don't like challenges? Try the easier version here:Bipartite Permutation
hide comments
khoaph:
20210315 08:50:26
For the 4th case 5 10 1000000000


:D:
20191119 09:13:42
Great problem. I really like how output is handled. It allowed for big N values and actually creates a subproblem to solve.

Added by:  sgtlaugh 
Date:  20191116 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem 