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, P1 and P2, from these numbers such that |sum(P1) – sum(P2)| is minimum, where sum(X) denotes the summation of all the numbers in partition X. A partition is defined to be a non-empty 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 P1 such that |sum(P1) – sum(P2)| 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

  • 1 ≤ T ≤ 1000
  • 2 ≤ N ≤ 109
  • N < B ≤ 109
  • 1 ≤ M ≤ 109
  • Output

    For each test case, first print the case number followed by the minimum absolute difference and the hash of the lexicographically smallest partition P1.

    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: 2021-03-15 08:50:26

    For the 4th case 5 10 1000000000
    With n = 5, I found P1 = {1, 2 , 5}, P2 = {3, 4}
    So the smallest lexicographically partition P1 is { 1, 2, 5}
    The hash will be:
    H0 = 0;
    H1 = (0 *10 + 1)%1000000000= 1
    H2 = (1 * 10 + 2)%1000000000 = 12
    H3 = (12 * 10 + 5)%1000000000 = 125
    So why the result in the example is 124
    Am I misunderstanding something?

    [NG]: For n=5, smallest P1 is {1, 2, 4}.

    Last edit: 2021-03-15 15:14:13
    :D: 2019-11-19 09:13:42

    Great problem. I really like how output is handled. It allowed for big N values and actually creates a sub-problem to solve.

    -> Thanks! Glad you liked it :D

    Last edit: 2019-11-23 20:45:43

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