Unlock the Padlock Round B 2022 - Kick Start 2022

Unlock the Padlock Round B 2022 - Kick Start 2022

Problem

Imagine you have a padlock, which is a combination lock consisting of N$N$ dials, set initially to a random combination. The dials of the padlock are of size D$D$, which means that they can have values between 0$0$ and D−1$\mathbf{D}-1$, inclusive, and can be rotated upwards or downwards. They are also ordered from left to right, with the leftmost and rightmost dials at positions 1$1$ and N$N$, respectively. The padlock can be unlocked by setting the values of all its dials to 0$0$.

You can perform zero or more operations of this kind:

• Pick any range [l,r]$[l,r]$ such that 1≤l≤r≤N$1\le l\le r\le \mathbf{N}$ and rotate all the dials in [l,r]$[l,r]$ together, upwards or downwards. Rotating up increases the value of each dial in the range [l,r]$[l,r]$ by 1$1$, and rotating down decreases its value by 1$1$. Note that a dial with value D−1$\mathbf{D}-1$ becomes 0$0$ when increased (rotated up) and a dial with value 0$0$ becomes D−1$\mathbf{D}-1$ when decreased (rotated down).

The series of operations must satisfy the following condition:

• The range [li−1,ri−1]$[l_{i-1},r_{i-1}]$ chosen in the (i−1)$(i-1)$-th operation needs to be completely contained within the range [li,ri]$[l_i,r_i]$ chosen in the i$i$-th operation; that is, li≤li−1≤ri−1≤ri$l_i\le l_{i-1}\le r_{i-1}\le r_i$. The initial range ([l1,r1]$[l_1,r_1]$) can be chosen arbitrarily.

Example of a valid sequence of operations to unlock a padlock with initial combination [1,1,2,2,3,3]$[1,1,2,2,3,3]$:

1. Rotate range [5,6]$[5,6]$ downwards.
2. Rotate range [3,6]$[3,6]$ downwards.
3. Rotate range [1,6]$[1,6]$ downwards.

Pancake Deque Solution Round 1B 2022 - Code Jam 2022

ASeDatAb Solution Round 1B 2022 - Code Jam 2022

Controlled Inflation Solution Round 1B 2022 - Code Jam 2022

The following are some operations that cannot be performed:

1. Rotating range [1,4]$[1,4]$ after [6,9]$[6,9]$, because [6,9]$[6,9]$ is not completely contained in [1,4]$[1,4]$ (does not satisfy ri−1≤ri$r_{i-1}\le r_i$ where ri−1=9$r_{i-1}=9$ and ri=4$r_i=4$).
2. Rotating range [3,6]$[3,6]$ after [2,7]$[2,7]$.

The goal for you is to output the minimum number of valid operations needed to make all dials in the padlock set to 0$0$.

Input

The first line of the input contains the number of test cases, T$T$. T$T$ test cases follow.

Each test case consists of two lines.

The first line of each test case contains two integers N$N$ and D$D$, representing the number of dials in the padlock and the size of the dials, respectively.

The second line of each test case contains N$N$ integers V1,V2,…,VN${\mathbf{V}}_{\mathbf{1}},{\mathbf{V}}_{\mathbf{2}},\dots ,{\mathbf{V}}_{\mathbf{N}}$, where the i$i$-th integer represents the value of the i$i$-th dial in the initial combination of the padlock.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1$1$) and y$y$ is the minimum number of operations needed to unlock the padlock as described in the statement.

Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
0≤Vi≤D−1$0\le {\mathbf{V}}_{\mathbf{i}}\le \mathbf{D}-1$, for all i$i$.

Test Set 1

1≤N≤40$1\le \mathbf{N}\le 40$.
D=2$\mathbf{D}=2$.

Test Set 2

1≤N≤40$1\le \mathbf{N}\le 40$.
2≤D≤10$2\le \mathbf{D}\le 10$.

Infinity Area Solution Round B 2022 - Kick Start 2022

Palindromic Factors Round B 2022 - Kick Start 2022

Hamiltonian Tour Round B 2022 - Kick Start 2022

Test Set 3

1≤N≤400$1\le \mathbf{N}\le 400$.
2≤D≤109$2\le \mathbf{D}\le {10}^9$.

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input

2
6 2
1 1 0 1 0 1
6 2
0 1 0 0 1 1

Sample Output

Case #1: 3
Case #2: 2

In Sample Case #1, the minimum number of operations needed to unlock the padlock is 3$3$. We can unlock it using the following operations:

1. Rotate range [4,4]$[4,4]$ downwards.
2. Rotate range [3,5]$[3,5]$ downwards.
3. Rotate range [1,6]$[1,6]$ downwards.

In Sample Case #2, the minimum number of operations needed to unlock the padlock is 2$2$. We can unlock it using the following operations:

1. Rotate range [3,4]$[3,4]$ upwards.
2. Rotate range [2,6]$[2,6]$ downwards.

Solution Click Below:-

Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input

2
6 10
1 1 2 2 3 3
6 10
1 1 9 9 1 1

Sample Output

Case #1: 3
Case #2: 3

In Sample Case #1, the minimum number of operations needed to unlock the padlock is 3$3$. We can unlock it using the following operations:

1. Rotate range [5,6]$[5,6]$ downwards.
2. Rotate range [3,6]$[3,6]$ downwards.
3. Rotate range [1,6]$[1,6]$ downwards.

In Sample Case #2, the minimum number of operations needed to unlock the padlock is 3$3$. We can unlock it using the following operations:

1. Rotate range [3,4]$[3,4]$ upwards.
2. Rotate range [3,4]$[3,4]$ upwards.
3. Rotate range [1,6]$[1,6]$ downwards.

Join Now for Solution:-