Here is the mashup link (the problems are from Codeforces' problem set).
A. The Lone Element Quest
To identify the unique element, this solution counts the occurrences of each number in the array. Then, it locates its index in the array.
from collections import Counter
t = int(input())
for _ in range(t):
n = int(input())
nums = list(map(int, input().split()))
count = Counter(nums)
for key in count:
if count[key] == 1:
mynum = key
for i in range(len(nums)):
if nums[i] == mynum:
print(i + 1)
break
B. YetnotherrokenKeoard
To solve the problem quickly, we can maintain two stacks: one for uppercase letters and one for lowercase letters. When deleting, we need to mark that the character at a specific position should be skipped. Alternatively, we can reverse the original string and skip characters instead of deleting them.
tc = int(input())
for _ in range(tc):
word = input()
res = []
cap_pos = []
sm_pos = []
for i in word:
if i == "B":
if cap_pos:
res[cap_pos.pop()] = ""
elif i == 'b':
if sm_pos:
res[sm_pos.pop()] = ""
else:
if i.islower():
sm_pos.append(len(res))
else:
cap_pos.append(len(res))
res.append(i)
print("".join(res[:-1]))
C. African Crossword
Initialize $$$(rows)$$$ and $$$(cols)$$$ dictionaries to track the frequency of each element in the matrix rowwise and columnwise.
For each element $$$a_{ij}$$$, update the counts of these elements in the corresponding $$$(rows)$$$ and $$$(cols)$$$ dictionaries for that row and column.
Check if the count of the current element in both the $$$(rows)$$$ dictionary of its row and the $$$(cols)$$$ dictionaries of its column is equal to $$$(1)$$$. If so, the element is considered unique and updates the $$$(result)$$$ list.
from collections import defaultdict
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(input()))
rows = [defaultdict(int) for i in range(n)]
cols = [defaultdict(int) for i in range(m)]
for i in range(n):
for j in range(m):
rows[i][grid[i][j]] += 1
cols[j][grid[i][j]] += 1
result = []
for i in range(n):
for j in range(m):
if rows[i][grid[i][j]] == 1 and cols[j][grid[i][j]] == 1:
result.append(grid[i][j])
print(''.join(result))
D. Zero Quantity Maximization
The equation $$$c_i = d \cdot a_i + b_i$$$ is given, and the objective is to maximize the number of zeros in the resulting array $$$c$$$. To achieve this goal, the strategy is to identify values of $$$d$$$ that satisfy the condition $$$0 = d \cdot a_i + b_i$$$, which leads to the expression $$$d = (-b_i) / a_i$$$.
The approach involves iterating through the elements in arrays $$$a_i$$$ and $$$b_i$$$ to track the frequency of occurrences of $$$((-b_i) / a_i)$$$ in a dictionary. To avoid potential inaccuracies stemming from floating-point precision problems when using decimal numbers as dictionary keys, the code represents these fractions in their simplest form. For instance, for values $$$a_i = 6$$$ and $$$b_i = 9$$$, simplification yields $$$(-9/6 => -3/2)$$$, and the simplified fraction $$$(-3, 2)$$$ is used as a key in the dictionary.
from collections import defaultdict
from fractions import Fraction
def main():
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = defaultdict(int)
d = 0
for i in range(n):
if b[i] == 0 and a[i] == 0:
d += 1
elif a[i]:
fraction = Fraction(-b[i], a[i])
c[fraction] += 1
d += max(c.values()) if c else 0
print(d)
if __name__ == '__main__':
main()
E. Equalize the Array
This problem can be solved using a dictionary to track the count of each number in the array. By iterating through the array and incrementing the count of each number in the dictionary, we calculate the current count (current_count
) for each number. Additionally, we utilize another dictionary (appearance_dict
) to monitor the total size of the numbers for each frequency count (calculated as frequency_count * frequency = the total size
). This calculation allows us to understand the array's total size if the frequency is set as C
.
After traversing through the array, we determine the maximum value in the appearance_dict
dictionary. This value signifies the maximum size capable of accommodating numbers. The key retrieved from the dictionary indicates the maximum frequency for each unique number, necessary to make the array beautiful. Our goal is to ensure each number appears either zero or C
times. Hence, we must eliminate all elements except those appearing C
times. Consequently, the number of elements to remove equals the total number of elements minus the maximum value found in the appearance_dict
dictionary.
from collections import defaultdict
test_cases = int(input())
for _ in range(test_cases):
array_length = int(input())
array = list(map(int, input().split()))
count_dict = defaultdict(int)
appearance_dict = defaultdict(int)
for element in array:
count_dict[element] += 1
current_count = count_dict[element]
appearance_dict[current_count] += current_count
max_appearance = max(appearance_dict.values())
print(array_length - max_appearance)