Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Relocation Game

By Labib666 · Limits 3s, 512 MB

Tourist ( Gennady Korotkevich ) is a famous competitive programmer. He has won two ACM ICPC World Finals. Thanks to his sublime performance in contests, he has become very popular all over the world!

One day Tourist came across an interesting problem. It goes like this:

You are given an array A of N integers named A0 , A1 , ... , AN-1. The array elements are in the range [0,N-1]. You have to rearrange the elements in a non-decreasing order. Let Pi denote the location of the value Ai after the rearrangement is done. The cost of this rearrangement is the sum of | Pi - i | for all 0 ≤ i ≤ N-1. Here, |x| denotes the absolute value of x. You have to find the minimum cost of such a rearrangement.

These days Tourist is too busy playing the new arcade game, Forthright on his dearest gaming PC. So he asks you, his favorite underling, to solve this problem.

Input

The first line of input contains an integer T, the number of test cases for the problem. Each of the following T lines describe a test case.

For each test case, you are given four integers in the following order: N (the number of elements in array A), A0 (the first element of array A), B and C. Ai for 1 ≤ i ≤ N-1 is calculated using the formula Ai = ( ( Ai-1 * B ) + C ) % N.

Constraints:

1 ≤ T ≤ 104
1 ≤ N ≤ 104
0 ≤ Ai < N for all 0 ≤ i < N
0 ≤ B, C ≤ 109

Notice that both the initial array and the array after rearrangement have 0-based indexing.

Output

For each test case, output the minimum cost of rearrangement for that case in a separate line.
Please take a look at the sample input/output to get a better understanding of the format.

Sample

InputOutput
2
4 3 5 3
4 0 1 1
8
0

Explanation

Case 01:
Before rearrangement, A = [ 3, 2, 1, 0 ]
After rearrangement, A = [ 0, 1, 2, 3]
P = [ 3, 2, 1, 0 ]. Hence, cost = | 3 – 0 | + | 2 – 1 | + | 1 – 2 | + | 0 – 3 | = 8.

Case 02:
Before rearrangement, A = [ 0, 1, 2, 3 ]
After rearrangement, A = [ 0, 1, 2, 3]
P = [ 0, 1, 2, 3 ]. Hence, cost = | 0 – 0 | + | 1 – 1 | + | 2 – 2 | + | 3 – 3 | = 0.

Discussion

Statistics


52% Solution Ratio

PsychoKillerEarliest, Jul '18

ovis96Fastest, 1380672.9s

ovis96Lightest, 262 kB

MistiiShortest, 610B

Submit

Login to submit

Editorial

We need to sort the given array elements. In order to reduce the cost, we must do an &quot;in place&...

Toph uses cookies. By continuing you agree to our Cookie Policy.