A2SV G5 — Contest 2 Editorial
Разница между en6 и en7, 0 символ(ов) изменены
[Here](https://codeforces.net/contestInvitation/da039344b0dc2ce9e75d667164b7b6a98caba345) is the mashup link (the problems are from Codeforces' problem set).↵

#### [A. Anti-codeforces](https://codeforces.net/gym/491508/problem/A)↵

<spoiler summary = "Solution">↵
<p>Given that the length of the provided string is 10, the approach involves iterating through the string and comparing each character at position i with the corresponding character at position i in "codeforces."</p>↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
t = int(input())↵
c = "codeforces"↵
for _ in range(t):↵
    s = input()↵
    res = 0↵
    for i in range(10):↵
        if s[i] != c[i]:↵
             res += 1↵
    print(res) ↵
```↵
</spoiler>↵

#### [B. Alice and Bob Again] (https://codeforces.net/gym/491508/problem/B)↵

<spoiler summary = "Hint">↵
<p>↵
Consider the first character in each pair.↵
</p>↵
</spoiler>↵


<spoiler summary = "Solution">↵
<p>↵
Take every other character starting from the first one. ↵
Since the last character can not be a starting letter for a pair, add it to 'a' last.↵
</p>↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
    b = input()↵


    a = [] # Storing the characters in a list and appending gives a better time complexity compared to string concatenation↵
    for index in range(0, len(b), 2):↵
        a.append(b[index])↵
   ↵
    a.append(b[-1])↵
    a = "".join(a)↵
    print(a)↵
```↵
</spoiler>↵

#### [C. Palindrome-emordnilaP](https://codeforces.net/gym/491508/problem/C)↵

<spoiler summary = "Hint">↵
Any palindrome subsequence with **length &ge; 3** also contains a palindrome with **length = 3** as its subsequence.↵
</spoiler>↵


<spoiler summary = "Solution">↵
The first observation is that we can always try to find the palindrome of length **3** (otherwise, we can remove some numbers from the middle until its length becomes **3**).↵

The second observation is that the palindrome of length **3** is two equal numbers and some other (maybe, the same) number between them. For each number, we only need to consider its left and right occurrences (if there is any number between them).↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
t = int(input())↵

for _ in range(t):↵
    N = int(input())↵
    nums = list(map(int, input().split()))↵

    left_occurrence = {}↵
    found = False↵
    ↵
    for i, n in enumerate(nums):↵
        if n in left_occurrence:↵
            if i - left_occurrence[n] >= 2:↵
                found = True↵
                break                ↵
        else:↵
            left_occurrence[n] = i↵
    ↵
    if found:↵
        print("YES")↵
    else:↵
        print("NO")↵
```↵
</spoiler>↵

#### [D. Counting Equal Differences] (https://codeforces.net/gym/491508/problem/D)↵

<spoiler summary = "Hint">↵
<p>↵
Can you rewrite the formula?↵
</p>↵
</spoiler>↵


<spoiler summary = "Solution">↵
<p>↵

The equation $a_j - a_i = j - i$ can be transformed into $a_j - j = a_i - i$, and let $b_i = a_i - i$. Then we need to count the number of pairs $(i, j)$ where $b_i = b_j$. We can use a dictionary(hash map) to count occurrences of each difference $(b_i)$.↵
</p>↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
T = int(input())↵
for _ in range(T):↵
    N = int(input())↵
    a = list(map(int,input().split()))↵
    difference_count = {}↵
    pair_count = 0  ↵

    for i in range(N):↵
        difference = a[i] - i↵
        pair_count += difference_count.get(difference, 0)↵
        difference_count[difference] = difference_count.get(difference, 0) + 1↵
    print(pair_count)↵
```↵
</spoiler>↵

#### [E. Pivot Sorting] (https://codeforces.net/gym/491508/problem/E)↵

<spoiler summary = "Solution">↵
<p>↵

What does it mean for an array $a_1, a_2, \ldots, a_n$ to be sorted? It means $a_1 \leq a_2$ and $a_2 \leq a_3$, and so on. For each pair of adjacent elements, let's deduce which values of $x$ put them in the correct order. Any value of $x$ that satisfies all pairs will be the answer.↵
</p>↵
<p>↵
Consider any $a_i$ and $a_{i+1}$ and solve the inequality $|a_i - x| \leq |a_{i+1} - x|$. If $a_i = a_{i+1}$, then any value of $x$ works. Let $a_i$ be smaller than $a_{i+1}$. If $x$ is smaller than or equal to $a_i$, then the inequality becomes $a_i - x \leq a_{i+1} - x$ implies $a_i \leq a_{i+1}$. Thus, they don't change their order, and any $x \leq a_i$ works.↵
</p>↵
<p>↵
If $a_i > a_{i+1}$ and we want to change their order, $x$ should be $\geq \lceil \frac{a_i + a_{i+1}}{2} \rceil$. For this pair, we want $x$ to be the minimum, which is $\lceil \frac{a_i + a_{i+1}}{2} \rceil$. This number doesn't have to change the pairs that are already in the correct order. For all pairs $i$ and $i+1$ where $a_i > a_{i+1}$, to satisfy all pairs, we have to take the maximum. To check if that maximum number satisfies all the conditions, we can construct the array using this number and check if it's non-decreasing. If it is, then it's valid; otherwise, return -1.↵
</p>↵
</spoiler>↵

<spoiler summary="Code">↵
```python3↵
from math import ceil↵
t = int(input())↵
for _ in range(t):↵
    n = int(input())↵
    nums = list(map(int, input().split()))↵
    maximum = 0↵
    for i in range(n - 1):↵
        if nums[i] > nums[i + 1]:↵
            maximum = max(maximum, ceil((nums[i] + nums[i + 1]) / 2))    ↵
    for i, num in enumerate(nums):↵
        nums[i] = abs(num - maximum)↵
    flag = True↵
    for i in range(1, len(nums)):↵
        if nums[i] < nums[i - 1]:↵
            flag = False↵
            break↵
    if flag:↵
        print(maximum)↵
    else:↵
        print(-1)↵
```↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский A2SV_Group5 2023-12-11 11:59:24 0 (published)
en6 Английский A2SV_Group5 2023-12-11 11:58:48 163
en5 Английский A2SV_Group5 2023-12-09 09:12:36 98
en4 Английский A2SV_Group5 2023-12-08 08:51:00 2006
en3 Английский A2SV_Group5 2023-12-07 23:51:40 1534 Tiny change: ' &ge; 3** contains ' -> ' &ge; 3** also contains '
en2 Английский A2SV_Group5 2023-12-07 21:55:57 748
en1 Английский A2SV_Group5 2023-12-07 20:12:07 1495 Initial revision (saved to drafts)