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()
B)uniproduct sequence
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)
E)Block Sequence
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()