A2SV AAiT and ASTU G5 — Contest #8 Editorial
Difference between en4 and en5, changed 0 character(s)
[Here](https://mirror.codeforces.com/contestInvitation/24ff18dc1c19331812846db87b5acbcfe9cae2b9) is the mashup link (the problems are from Codeforces' problem set).↵
#### [A. Nanati's Special number](https://mirror.codeforces.com/gym/504562/problem/A)↵

<spoiler summary = "Solution">↵
To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $O(n)$.↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
    n = int(input())↵
    s = input()↵
    ma = 0↵
    for ch in s:↵
        ma = max(ma, ord(ch))↵
    print(ma - 96)↵
  ↵
```↵
</spoiler>↵


#### [B. Monochromatic Striped Pattern](https://mirror.codeforces.com/gym/504562/problem/B)↵

<spoiler summary = "Hint">↵
What if we use a fixed size sliding window?↵
</spoiler>↵


<spoiler summary = "Solution">↵
To obtain a segment of $k$ cells with black color, ↵
we must paint all the white cells within that segment black. ↵
We then consider all segments of length $k$ (there are only $n - k$ such segments) ↵
and choose the one with the fewest white cells on it. ↵
Implementing this involves using a sliding window of size $k$. ↵
Since we have only two colors, we can simplify our implementation ↵
by only using two pointers.↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
t = int(input())↵
for _ in range(t):↵
    n, k = map(int, input().split())↵
    s = input()↵


    recolored = n↵
    black_count = 0↵
    left = 0↵
   ↵
    for right, color in enumerate(s):↵
        black_count += (color == 'B')↵


        if right - left + 1 == k:↵
            recolored = min(recolored, k - black_count)↵
            black_count -= (s[left] == 'B')↵
            left += 1↵


    print(recolored)↵
```↵
</spoiler>↵

#### [C. Polycarp and the Divine Tongue](https://mirror.codeforces.com/gym/504562/problem/C)↵

<spoiler summary = "Solution">↵
<p>↵
Underline every letter $w$, so that it can't be mistaken with $vv$. The string splits into segments of letters $v$. Out of each pair of consecutive letters $v$ at least one should be underlined. So for the minimum amount you can underline either all the odd positions of the segment or all the even ones. Thus, if the length of the segment is $len$↵
, then $⌊len/2⌋$ underlined letters is enough.↵

</p>↵
</spoiler>↵

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

t = int(input())↵
for _ in range(t):↵
    s = input()↵

    left = 0↵
    underline = 0↵

    for right in range(len(s)):↵
        if s[right] == 'w':↵
            if s[left] == 'w':↵
                underline += 1↵
                ↵
            else:↵
                underline += 1 + (right - left)//2↵

            left = right + 1↵
        ↵
    if left < len(s):↵
        underline += (len(s) - left)//2↵
    ↵
    print(underline)↵
```↵
</spoiler>↵

#### [D. Distinctive Components](https://mirror.codeforces.com/gym/504562/problem/D)↵

<spoiler summary = "Hint 1">↵
Because the constraints are small, brute forcing it is possible. So, check if every number inside your array can be expressed as a subarray sum.↵
</spoiler>↵

<spoiler summary = "Hint 2">↵
Use two pointers technique to efficiently find subarrays with sums equal to the current element.↵
</spoiler>↵


<spoiler summary = "Solution">↵
<p>We're given an array of numbers and we're trying to find out how many special numbers are there in the array. A special number is one that can be expressed as the sum of two or more consecutive numbers in the array. To solve this, we'll go through each number in the array one by one and check if it satisfies the condition of being special. We'll do this by considering it as a potential sum of consecutive numbers starting from the beginning of the array. We'll keep track of the sum of these consecutive numbers as we move through the array.↵
</p>↵
<p>Here's how it works: Imagine we're at a certain number in the array. We start considering it as the sum of consecutive numbers starting from the first number in the array. As we move forward, we add each number to our running sum. If at any point our running sum equals the current number, and we've considered at least two numbers in the subarray (because a single number by itself doesn't count as a sum of consecutive numbers), then we've found a special number. We'll count this and move on to the next number in the array.↵
</p>↵
<p>By repeating this process for each number in the array, we'll be able to count all the special numbers. This approach allows us to efficiently find special numbers without needing to store all the possible consecutive sums separately. It's a straightforward method that checks each number individually to determine if it's special.↵
</p>↵
</spoiler>↵


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

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


    count = 0↵
    for num in a:↵
        left = 0↵
        run_sum = 0↵
        for right in range(n):↵
            run_sum += a[right]↵
            while run_sum > num:↵
                run_sum -= a[left]↵
                left += 1           ↵
            if run_sum == num and left < right:↵
                count += 1↵
                break↵
   ↵
    print(count)↵

```↵
</spoiler>↵

#### [E. Neighboring sets](https://mirror.codeforces.com/gym/504562/problem/E)↵

<spoiler summary = "Hint 1">↵
<p>Consider sorting the array.</p>↵
</spoiler>↵


<spoiler summary = "Hint 2">↵
<p>A sliding window where the right most number minus the left most number is $<= 2$ could tell us a lot of information.</p>↵
</spoiler>↵

<spoiler summary = "Solution">↵
<p>↵
For a window size $m$, where $m >= 3$, if the right most number minus the left most number is $<= 2$, how many triples can we form if we take the current right element as the maximum value? ↵

Lets label the numbers in the window as $w_{1}, w_{2}, w_{3}, ..., w_{m - 2}, w_{m - 1}, w_{m}$. Now if we fix the maximum value to be $w_{m}$:↵
<br/>↵
<ul>↵
<li>For $w_{m - 1}$ as the middle value, we can take the remaining $m - 2$ numbers, $w_{1}, w_{2}, w_{3}, ..., w_{m - 2}$, to be the minimum number.</li>↵
<li>For $w_{m - 2}$ as the middle value, we can take the remaining $m - 3$ numbers, $w_{1}, w_{2}, w_{3}, ..., w_{m - 3}$,  to be the minimum number.</li>↵
<br/>↵
.<br/>↵
.<br/>↵
.↵
</li>↵
<li>For $w_{2}$ as the middle value, we can take the remaining number $w_{1}$ to be the minimum number.</li>↵
</ul>↵

<p>From the above possible middle values, in total, we can form $(m - 2) + (m - 3) + ... + 1$ triples.</p>↵
<p>Hence, with the current right value we can form $(m - 2)*(m - 1)/2$ triples.</p>↵


</p>↵
</spoiler>↵

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

t = int(input())↵
for _ in range(t):↵
    n = int(input())↵
    a = sorted(map(int, input().split()))↵

    left = 0↵
    triples = 0↵

    for right in range(n):↵
        num = a[right]↵
        while num - a[left] > 2:↵
            left += 1↵

        win_size = right - left + 1            ↵
        if win_size >= 3:↵
            triples += (win_size - 2)*(win_size - 1)//2↵

    print(triples)↵
```↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English A2SV_Group5 2024-02-14 11:22:23 0 (published)
en4 English A2SV_Group5 2024-02-14 11:15:21 96
en3 English A2SV_Group5 2024-02-13 16:25:28 25
en2 English A2SV_Group5 2024-02-13 14:57:30 14
en1 English A2SV_Group5 2024-02-13 14:52:15 7366 Initial revision (saved to drafts)