A2SV G4 — Weekly Contest #6
Difference between en8 and en9, changed 2 character(s)
### [A) Restore the Sequence](https://codeforces.com/gym/425425/problem/A)↵

<spoiler summary="Hint">↵
Use two pointers↵
</spoiler>↵

<spoiler summary="Approach">↵
In this problem, you can implement an algorithm opposite to that given in the condition. Let's maintain **two pointers to the left-most and right-most unhandled element.** Then, restoring the original array, you:↵

- put the left-most unhandled item in the first position↵
- put the right-most unhandled item in the second position↵
- put the left-most unhandled item in the third position↵
- put the right-most unhandled item in the fourth position↵
...↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
def solve():↵
length_of_sequence = int(input())↵
sequence = list(map(int, input().split()))↵
↵
left = 0↵
right = length_of_sequence - 1↵
write_left = True↵
↵
while left <= right:↵
↵
if write_left:↵
print(sequence[left], end = ' ')↵
left += 1↵
↵
else:↵
print(sequence[right], end = ' ')↵
right -= 1↵
↵
write_left = not write_left↵
↵
print()↵

def main():↵
num_tests = int(input())↵
for i in range(num_tests):↵
solve()↵

main()↵
~~~~~↵

</spoiler>↵

### [B)uniproduct sequence](https://codeforces.com/gym/425425/problem/B)↵

<spoiler summary="Approach">↵
The product of multiple integers can only **equal 1 if each of the integers are either 1 or -1, with an even number of -1s**. To make this happen, we need to spend at least **"ai &mdash; 1" coins for each positive integer "ai" to reduce it to 1** and **spend at least "-1 &mdash; ai" coins for each negative integer "ai" to increase it to -1.** **If there are 0s among the numbers, we will need to spend at least "k" coins to replace each zero with either 1 or -1.** If there are no zeros and the product is not equal to 1, it will require an additional 2 coins to change some 1s to -1s or some -1s to 1s.↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
length = int(input())↵

neg_cnt = 0↵
zero_cnt = 0↵
ans = 0↵

nums = list(map(int, input().split()))↵

for i in range(length):↵
if nums[i] == 0:↵
ans += 1↵
zero_cnt += 1↵
elif nums[i] < 0:↵
ans += (-1 - nums[i])↵
neg_cnt += 1↵
else:↵
ans += nums[i] - 1↵

if neg_cnt % 2 == 1 and zero_cnt == 0:↵
ans += 2↵

print(ans)↵
~~~~~↵

</spoiler>↵

### [C) Swap sequence](https://codeforces.com/gym/425425/problem/C)↵

<spoiler summary="Hint">↵
Try to think of a sorting algorithm where you can track the swapped elements↵
</spoiler>↵

<spoiler summary="Approach">↵
Use **Selection sort** to sort out the elements and when you do the swaps add the indices of both elements. ↵

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list↵

- **Time-Complexity &mdash; O(N^2)**↵
- **Space-Complexity &mdash; O(N)**↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
n = int(input())↵
arr = list(map(int, input().split()))↵
pairs = []↵

for i in range(len(arr)):↵
min_idx = i↵
for j in range(i + 1, len(arr)):↵
↵
if arr[min_idx] > arr[j]:↵
min_idx = j↵
↵
↵
if min_idx != i:↵
pairs.append((i, min_idx))↵
arr[min_idx], arr[i] = arr[i], arr[min_idx]↵

print(len(pairs))↵
for res in pairs:↵
print(*res)↵

~~~~~↵

</spoiler>↵

### [D) Complex Bracket Sequence](https://codeforces.com/gym/425425/problem/D)↵

<spoiler summary="Hint">↵
Use Two pointers approach↵
</spoiler>↵

<spoiler summary="Approach">↵
We claim that the answer is always 0 or 1. First, note we can't apply any operations if and only if each ')' symbol is left from each '(' symbol, so that the string looks as ')))(((((('.↵

The basic idea of the solution is to match '(' with ')' on the right side of it. We can use two pointers to do that.↵

- **Time complexity: O(n)**↵
- **space Complexity: O(1)**↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
def main():↵
brackets = input()↵
↵
length = len (brackets)↵
left = 0↵
right = length - 1↵
ans = []↵
↵
↵
while (left < right):↵
while (left < right and brackets[left] == ')'):↵
left += 1↵
↵
↵
while (left < right and brackets[right] == '('):↵
right -= 1↵
↵
↵
if (left < right):↵
ans.append(left + 1)↵
ans.append(right + 1)↵
↵
left += 1↵
right -= 1↵
↵
↵
ans.sort()↵
↵
if (len(ans) > 0):↵
print(1)↵
print(len(ans))↵
print(*ans)↵
else:↵
print(0)↵
↵
main()↵
~~~~~↵

</spoiler>↵

### [E)Block Sequence](https://codeforces.com/gym/425418/problem/E)↵

<spoiler summary="Hint 1">↵
What shall we do in order to keep the top view same as the original?↵
</spoiler>↵

<spoiler summary="Hint 2">↵
What shall we do in order to keep the right side view the same as the original?↵
</spoiler>↵

<spoiler summary="Approach">↵
- If we assume the stack of blocks as a matrix:↵
- -  rows are represented the height of blocks at each index that is a[i].↵
- - Columns are represented by the indices↵
↵
- In order for the top and right side view to be the same two things should be fulfilled↵
- - - In order to maintain the same top view from the original view, ↵
all columns containing blocks should leave **at least one block remaining** when the rest are removed. This way, the top view will remain unchanged.↵
- - - To maintain **the right side view** of the stack of blocks, it is necessary to keep **at least one block in each row**, starting from **Row =1 up to the maximum height of the stack**.↵

- To make the right side views of blocks the same would be to use blocks which have **minimum heights in order to cover up rows with minimum values.** While doing this we have to **make sure there is at least on block that is left in each column.**↵
- **Example:**↵
a = [2, 3, 1, 4, 4]↵
In order to make the right side view of the blocks identical to the original, all stacks of blocks with a height ranging from 1 to 4 must be present in each row between rows 1 and 4.↵

- The first block should be placed at index 2, to cover the row of 1. The second block should be placed at index 0 and will cover a row of 2. The third block should be placed at index 1 and will cover a value of 3. Finally, the fourth block can either be placed at index 3. Since we have to make sure that one block should be left at each index we can leave one block at index 4 and remove the rest.↵
######Time Complexity: **O(n.log n)**↵
</spoiler>↵

<spoiler summary = "Code">↵

~~~~~↵
def main():↵
num_stacks, height_of_exhibit = map(int, input().split())↵
heights = list(map(int, input().split()))↵
↵
height_to_build = 1↵
max_height = max(heights)↵
↵
heights.sort()↵
ans = 0↵
↵
for i in range(num_stacks):↵
#we leave one block in each column and remove the rest↵
ans += (heights[i] - 1)↵
↵
#if the current height is built move to the next↵
if heights[i] >= height_to_build:↵
height_to_build += 1↵
↵
↵
#subtract number of unbuilt heights from answer↵
ans -= (max_height - height_to_build + 1)↵
print(ans)↵

main()↵
~~~~~↵

↵
</spoiler>↵

#### History

Revisions Rev. Lang. By When Δ Comment
en9 a2sv 2023-02-07 13:23:28 2 (published)
en8 a2sv 2023-02-05 01:10:32 1306
en7 a2sv 2023-02-05 01:05:16 1118 Tiny change: 'ler>\n### ### [E)Blo' -> 'ler>\n### [E)Blo'
en6 a2sv 2023-02-05 00:08:46 6 Tiny change: 'om **Row = 0 up to the' -> 'om **Row =1 up to the'
en5 a2sv 2023-02-05 00:07:58 1164
en4 a2sv 2023-02-04 16:38:47 9
en3 a2sv 2023-02-04 16:37:18 1273 Tiny change: '[### A) Restore' -> '### [A) Restore'
en2 a2sv 2023-02-04 16:22:35 28
en1 a2sv 2023-02-04 16:14:50 2672 Initial revision (saved to drafts)