A-B-C Sort solution codeforces – You are given three arrays 𝑎a, 𝑏b and 𝑐c. Initially, array 𝑎a consists of 𝑛n elements, arrays 𝑏b and 𝑐c are empty.
[Solution] A-B-C Sort solution codeforces
You are performing the following algorithm that consists of two steps:
- Step 11: while 𝑎a is not empty, you take the last element from 𝑎a and move it in the middle of array 𝑏b. If 𝑏b currently has odd length, you can choose: place the element from 𝑎a to the left or to the right of the middle element of 𝑏b. As a result, 𝑎a becomes empty and 𝑏b consists of 𝑛n elements.
- Step 22: while 𝑏b is not empty, you take the middle element from 𝑏b and move it to the end of array 𝑐c. If 𝑏b currently has even length, you can choose which of two middle elements to take. As a result, 𝑏b becomes empty and 𝑐c now consists of 𝑛n elements.
Refer to the Note section for examples.Can you make array 𝑐c sorted in non-decreasing order?
[Solution] A-B-C Sort solution codeforces
The first line contains a single integer 𝑡t (1≤𝑡≤2⋅1041≤t≤2⋅104) — the number of test cases. Next 𝑡t cases follow.
The first line of each test case contains the single integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the length of array 𝑎a.
The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1061≤ai≤106) — the array 𝑎a itself.
It’s guaranteed that the sum of 𝑛n doesn’t exceed 2⋅1052⋅105.
For each test, print YES (case-insensitive), if you can make array 𝑐c sorted in non-decreasing order. Otherwise, print NO (case-insensitive).
[Solution] A-B-C Sort solution codeforces
3 4 3 1 5 3 3 3 2 1 1 7331
YES NO YES
In the first test case, we can do the following for 𝑎=[3,1,5,3]a=[3,1,5,3]:
Step 11:
𝑎a | [3,1,5,3][3,1,5,3] | ⇒⇒ | [3,1,5][3,1,5] | ⇒⇒ | [3,1][3,1] | ⇒⇒ | [3][3] | ⇒⇒ | [][] |
𝑏b | [][] | [3⎯⎯][3_] | [3,5⎯⎯][3,5_] | [3,1⎯⎯,5][3,1_,5] | [3,3⎯⎯,1,5][3,3_,1,5] |
A-B-C Sort solution codeforces
Step 22:
𝑏b | [3,3,1⎯⎯,5][3,3,1_,5] | ⇒⇒ | [3,3⎯⎯,5][3,3_,5] | ⇒⇒ | [3⎯⎯,5][3_,5] | ⇒⇒ | [5⎯⎯][5_] | ⇒⇒ | [][] |
𝑐c | [][] | [1][1] | [1,3][1,3] | [1,3,3][1,3,3] | [1,3,3,5][1,3,3,5] |
As a result, array 𝑐=[1,3,3,5]c=[1,3,3,5] and it’s sorted.