Practice on Toph

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

Easy Peasy, Lemon Squeezy

By moshiur_cse15 · Limits 2s, 256 MB

Let’s consider an array $A$ which is initially empty. We’ll perform two types of operation on that array:

  1. Add an element $X$ at the end of the array.
  2. Remove the last element of the array.

Let’s define $beauty \, \, value$ of the array $A$ as the summation of the maximum and the minimum elements of the array. For example, let’s assume at any instance the array $A$ is [3, 2, 4]. The maximum element is: $4$, and the minimum element is: $2$. So the beauty value of the array at that instance is $2 + 4 = 6$.

At any point, if the array $A$ becomes empty, the value of the maximum and minimum is $0$ i.e. the beauty value is $0$ then. At any point, if you are asked to perform the second operation (removing the last element of the array) while the array $A$ is empty, you have to ignore that operation.

There will be multiple testcases in this problem. In each case, you have to process $N$ operations. In each operation, you’ll be given the type of the operation. If the type of the operation is of first kind, then you’ll be given another integer $X$, you have to add $X$ at the end of the array. If the type of the operation is of second kind, you have to remove the last element of the array. After each operation, you have to find the $beauty \, \, value$ of the array $A$. So, you will have $N$ $beauty \, \, values$. You have to find the $XOR$ (Exclusive OR) of all the $beauty \, \, values$.

Note: $XOR$ is a bitwise logical operation that outputs true only when inputs differ (one is true, the other is false). The truth table for all combinations of bits has given below:
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

Input

Input starts with an integer $T$, the number of testcases.

The first line of each testcase will contain an integer $N$, the number of operations. Instead of description of $N$ operations, the next line will contain 4 integers, $a$, $b$, $c$ and $m$. You have to use following formula to generate some integers $ V_i$, which is necessary to find the type of ith operation and the value to insert if the operation is of type 1.

$\displaystyle V_i = a \times V_{i-1} + c \pmod m $, where, $ V_0 = b$

If $ V_i$ is odd, then you have to add $V_i$ at the end of the array, i.e. $ X = V_i$.
If $ V_i$ is even, then the operation is of type 2, you have to erase the last element of the array.

Constraints

$1 \leq T \leq 10$
$1 \leq a, b, c, m \leq 10^8$

Subtask 1 (5 points)

$1 \leq N \leq 10^3$

Subtask 2 (15 points)

$1 \leq N \leq 10^6$

Subtask 3 (80 points)

$1 \leq N \leq 10^7$

Output

For each testcase, print the $XOR$ of the $beauty \, \, values$ of the array after performing each operation.

Sample

InputOutput
1
9
1 2 3 7
12

Explanation of the testcase 1:
Initially, V0 = 2. By using equation Vi = a ✕ Vi - 1 + c (mod m),
V1 = 5, It’s odd, 5 is added at the back of the array, hence the array, A = [5], the beauty value of the array is = 5 + 5 = 10
V2 = 1, It’s odd too, 1 is added at the back of the array, hence the array, A = [5, 1], the beauty value of the array is = 1 + 5 = 6
V3 = 4, It’s even, the last element of the array has removed, hence the array, A = [5], the beauty value of the array is = 5 + 5 = 10
V4 = 0, It’s even too, the last element of the array has removed, hence the array, A = [], i.e empty, the beauty value of the array is = 0 + 0 = 0
V5 = 3, It’s odd, 3 is added at the back of the array, hence the array, A = [3], the beauty value of the array is = 3 + 3 = 6
V6 = 6, It’s even, the last element of the array has removed, hence the array, A = [], i.e empty, the beauty value of the array is = 0 + 0 = 0
V7 = 2, It’s even too, the array is empty, hence skipped the operation, the beauty value of the array is = 0 + 0 = 0.
V8 = 5, It’s odd, 5 is added at the back of the array, hence the array, A = [5], the beauty value of the array is = 5 + 5 = 10
V9 = 1, It’s odd too, 1 is added at the back of the array, hence the array, A = [5, 1], the beauty value of the array is = 1 + 5 = 6
XOR of all the beauty values of the array after performing each operation is = 10 ⊕ 6 ⊕ 10 ⊕ 0 ⊕ 6 ⊕ 0 ⊕ 0 ⊕ 10 ⊕ 6 = 12.
Hence, the answer of testcase 1 is 12.

Discussion

Statistics


55% Solution Ratio

Samin_SieyamEarliest, 1M ago

iamSadeeFastest, 0.9s

YouKnowWhoLightest, 78 MB

NirjhorShortest, 594B

Submit

Login to submit