Tuesday, March 1, 2022

Magnet Sort

 There is an array 

A with N elements. Each element of A has a fixed polarity: either north or south.

Chef is allowed to perform some (possibly zero) operations on the array A. In one operation, Chef can:

  • Pick some subarray of array A, such that, the first and last elements of the subarray have different polarities, and, rearrange the elements in this subarray any way he wants.

Note that the polarity of each element remains unchanged after an operation.

Find the minimum number of operations required to sort the array in non-decreasing order, or state that it is impossible.

A subarray of A is obtained by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input Format

  • The first line contains an integer T, denoting the number of test cases. The T test cases then follow.
  • The first line of each test case contains a single integer N.
  • The second line of each test case contains N space-separated integers A1,A2,,AN.
  • The third line of each test case contains a string of length N, the ith character of which is either N or S, representing that the ith element of A has north or south polarity, respectively.

Output Format

For each test case, if it impossible to sort the array, output 1. Otherwise, output a single integer: the minimum number of operations required to sort the array.

Constraints

  • 1T105
  • 1N2105
  • 1Ai109
  • The sum of N across all test cases doesn't exceed 2105.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1 

6
5
1 3 2 3 7
NNSNS
2
2 1
SS
3
1 8 12
SNS
3
3 2 1
NSN
5
1 2 3 5 4
NSNSN
5
1 1 2 2 1
SNSNN

Sample Output 1 

1
-1
0
2
1
1

Explanation

Let's represent elements with a polarity of north in red, and elements with a polarity of south in blue. The polarity of each element is also labelled above it.

  • In the first test case, we can sort the array in a single operation as follows.

    • Rearrange the subarray [A1,A2,A3][1N,3N,2S,3N,7S][1N,2S,3N,3N,7S].
  • In the second test case, the array [2S,1S] cannot be sorted, since no operations can be performed.

  • In the third test case, the array is already sorted, so the answer is 0.

  • In the fourth test case, we can sort the array in two operations as follows.

    • Rearrange the subarray [A2,A3][3N,2S,1N][3N,1N,2S].
    • Rearrange the subarray [A1,A2,A3][3N,1N,2S][1N,2S,3N].

No comments:

Post a Comment

मुझे दिल में बसाना आसान नहीं....

पता है Recently i realised की मुझे दिल में बसाना आसान नहीं है बात-बात पे चिढ़ जाती हूं मैं दिल लगा लूं एक बार तो फिर ज़िद पे अड़...