A) Restore the Sequence
Use two pointers
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 ...
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()
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 — 1" coins for each positive integer "ai" to reduce it to 1 and spend at least "-1 — 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.
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)
C) Swap sequence
Try to think of a sorting algorithm where you can track the swapped elements
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 — O(N^2)
- Space-Complexity — O(N)
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)
D) Complex Bracket Sequence
Use Two pointers 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)
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()
What shall we do in order to keep the top view same as the original?
What shall we do in order to keep the right side view the same as the original?
- 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)
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()
Auto comment: topic has been updated by a2sv (previous revision, new revision, compare).