A2SV G5 ASTU - Contest #2 Editorial
Разница между en1 и en2, 4 символ(ов) изменены
[Here](https://codeforces.net/gym/495407) is the mashup link (the problems are from Codeforces' problem set).↵

#### [A. The Lone Element Quest](https://codeforces.net/gym/495407/problem/A)↵

<spoiler summary="Solution">↵

To identify the unique element, this solution counts the occurrences of each number in the array. Then, it locates its index in the array.↵

</spoiler>↵

<spoiler summary="Code">↵
```python↵
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↵
```↵
</spoiler>↵


#### [B. YetnotherrokenKeoard](https://codeforces.net/gym/495407/problem/B)↵

<spoiler summary="Solution">↵

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.↵

</spoiler>↵

<spoiler summary="Code">↵
```python3↵

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]))↵

```↵
</spoiler>↵

#### [C. African Crossword](https://codeforces.net/gym/495407/problem/C)↵

<spoiler summary = "Solution">↵
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.↵

</spoiler>↵


<spoiler summary="Code">↵
```python3↵
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))↵

```↵
</spoiler>↵




#### [D. Zero Quantity Maximization](https://codeforces.net/gym/495407/problem/D)↵

<spoiler summary = "Solution">↵

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.↵

</spoiler>↵


<spoiler summary="Code">↵
```python3↵
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()↵

```↵
</spoiler>↵




#### [E. Equalize the Array](https://codeforces.net/gym/495407/problem/E)↵

<spoiler summary="Solution">↵

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.↵

</spoiler>↵

<spoiler summary="Code">↵
```python↵
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)↵

```↵
</spoiler>↵






История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский A2SV_Group5 2024-01-03 13:50:40 4 (published)
en1 Английский A2SV_Group5 2024-01-03 13:48:39 6409 Initial revision (saved to drafts)