[Here](https://codeforces.net/contestInvitation/7dfb9ecd74f6fdab18822c70bdf1302f077031e9) is the link to the contest. All problems are from Codeforces' problemset.↵
↵
### [A. Nth Digit in Sequence](https://codeforces.net/gym/588468/problem/A)↵
↵
<spoiler summary="Solution">↵
The problem requires us to find the `n-th` digit in an infinite sequence formed by concatenating all positive integers starting from 1.↵
### Observations:↵
1. The sequence starts as: `123456789101112131415...`, and we need to determine the digit at position \(n\).↵
2. A simple way to construct the sequence is to append numbers as strings until we reach the required length.↵
### Approach:↵
- Initialize an empty string `sequence`.↵
- Iterate from `1` onwards, converting each number to a string and appending it to `sequence`.↵
- Stop when `sequence` reaches at least `n` characters.↵
- Print the `n-th` digit (adjusting for 0-based indexing).↵
### Complexity Analysis:↵
Since numbers grow in length, the loop runs approximately `O(sqrt{n})` times, making the approach efficient.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
n = int(input())↵
sequence = ""↵
for num in range(1, 1000):↵
sequence += str(num)↵
if len(sequence) >= n: # You can stop early when sequence is long enough↵
break↵
print(sequence[n - 1])↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [B. Anansi and Trip-Photographs](https://codeforces.net/gym/588468/problem/B)↵
↵
<spoiler summary="Problem Understanding">↵
Anansi needs to arrange **2n** A2SVians into two rows:↵
- **Front row:** Shorter individuals.↵
- **Back row:** Taller individuals.↵
↵
Each person in the back row must be at least **x** units taller than the corresponding person in the front row.↵
↵
We need to determine if this arrangement is possible for each test case.↵
</spoiler>↵
↵
<spoiler summary="Hints">↵
<details> ↵
<summary>Hint 1</summary> ↵
How can sorting help in organizing the two rows optimally? ↵
</details> ↵
↵
<details> ↵
<summary>Hint 2</summary> ↵
Try to place the smallest `n` people in the front row and the largest `n` people in the back row. ↵
</details> ↵
↵
<details> ↵
<summary>Hint 3</summary> ↵
After sorting, check if every person in the back row is at least `x` units taller than their corresponding person in the front row. ↵
</details> ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
### **Approach**↵
1. **Sorting for optimal arrangement** ↵
- To maximize our chances of meeting the height requirement, we sort the heights in **non-decreasing order**.↵
- Assign:↵
- **Front row:** First `n` elements.↵
- **Back row:** Last `n` elements.↵
↵
2. **Checking the Condition** ↵
- Ensure that for every `j`:↵
\[↵
\text{back}[j] — \text{front}[j] \geq x↵
\]↵
- If all pairs satisfy the condition, print `"YES"`, otherwise print `"NO"`.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
# Input handling↵
t = int(input()) # Number of test cases↵
for _ in range(t):↵
n, x = map(int, input().split()) # Read n and x↵
heights = list(map(int, input().split())) # Read 2n heights↵
↵
heights.sort() # Step 1: Sort the heights↵
front_row = heights[:n] # Step 2: First n people go to the front row↵
back_row = heights[n:] # Step 3: Last n people go to the back row↵
↵
# Step 4: Check if each person in the back row is at least x units taller↵
for j in range(n):↵
if back_row[j] - front_row[j] < x:↵
print("NO")↵
break↵
else:↵
print("YES")↵
```↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
### **Time Complexity**↵
1. **Sorting the array:** \(O(2n \log (2n)) = O(n \log n)\)↵
2. **Splitting into front and back rows:** \(O(n)\)↵
3. **Checking the height condition:** \(O(n)\)↵
↵
**Total Time Complexity:** ↵
\[↵
O(n \log n) + O(n) + O(n) = O(n \log n)↵
\]↵
which is efficient for \( n \leq 100 \).↵
↵
### **Space Complexity**↵
1. **Input storage:** \(O(2n)\) for storing heights.↵
2. **Two separate lists:** \(O(n)\) each for front and back row.↵
3. **Overall auxiliary space:** \(O(n)\)↵
↵
Since sorting is done in-place, **Total Space Complexity = O(n)**.↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [C. Minimal TV Subscriptions](https://codeforces.net/gym/588468/problem/C)↵
↵
<spoiler summary="Hint"> To solve this problem efficiently, consider how the shows are distributed over the days and how you can dynamically track the number of unique shows in each window of consecutive days. </spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> <p> The problem asks us to determine the minimum number of TV show subscriptions needed to ensure that we can watch at least <b>d</b> consecutive days without missing any episodes. The key is to use a sliding window approach to efficiently count the number of unique shows in each window of <b>d</b> consecutive days. <ul> <li><b>Sliding Window:</b> We first initialize a window with the first <b>d</b> shows and count how many unique shows are in that window using a hash table (Counter). Then, as the window slides forward by one day, we update the count of unique shows by adding the new day’s show and removing the show that is no longer in the window.</li> <li><b>Efficiency:</b> Instead of recalculating the number of unique shows for every possible window from scratch, we only adjust the window by removing one show and adding another, making the solution efficient.</li> </ul> <p> We start by counting the unique shows in the first <b>d</b> days. As the window slides through the entire schedule, we keep track of the minimum number of unique shows across all windows of length <b>d</b>. This minimum gives us the answer. </p> </p> </spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
from collections import Counter, defaultdict, deque↵
t = int(input()) # Number of test cases↵
for _ in range(t):↵
n, k, d = map(int, input().split()) # Read values for n, k, d↵
arr = list(map(int, input().split())) # Read the show schedule↵
window = Counter(arr[:d]) # Initialize window with first 'd' shows↵
ans = len(window) # Track minimum unique shows↵
↵
for i in range(d, n): # Slide the window through the array↵
window[arr[i]] += 1 # Add new show to window↵
window[arr[i - d]] -= 1 # Remove old show from window↵
↵
if window[arr[i - d]] == 0: # Remove show from counter if it no longer exists in window↵
del window[arr[i - d]]↵
↵
ans = min(ans, len(window)) # Update the minimum unique shows↵
↵
print(ans) # Output the result for the test case↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [D. Bernabas and the Harmonious Melody](https://codeforces.net/gym/588468/problem/D)↵
↵
<spoiler summary = "Solution">↵
<p>↵
Let’s initialize two pointers $l$ and $r$ at the beginning and at the end of the given string $s$. We will move $l$ to the right and $r$ to the left is $s[l]$ == $s[r]$. If $l$ and $r$ become equal or move past each other at some point, that means the given string is a palindrome and we don’t need to delete any character. Our answer in this case would be $0$.↵
</p>↵
↵
<p>↵
If that is not the case then $s[l]$ != $s[r]$ at some point. Since we are only allowed to delete one character, to make$s$ a palindrome, one of these characters must be deleted. We try deleting each character separately and we will take the alternative that requires minimum deletion. If it’s not possible to make $s$ a palindrome in both cases, we will print $-1). ↵
</p>↵
↵
<p>↵
So, the first time $s[l]$ becomes different from $s[r]$, let’s say deleting the character $c$ = $s[l]$ is our first option. We will have a variable $deleted$ to count the number of characters we will delete to try to make $s$ a palindrome. So every time $s[l]$ is not equal to $s[r]$, if either of them are equal to $c$, we can increment $deleted$ by one and move the pointer that’s pointing at a character that is equal to $c$. If $l$ becomes greater or equal to $r$, that means by deleting $deleted$ number of character $c$, we successfully made $s$ a palindrome. We do the same for the other case, $c$ = $s[r]$ as well, and print the option that requires minimum deletions. We have three cases↵
</p>↵
↵
<ul>↵
<li>↵
$case 1:$ if it is not possible to make $s$ a palindrome in both of our options, we print $-1$.↵
</li>↵
↵
<li>↵
$case 2:$ if it is not possible to make $s$ a palindrome in one of the options, and possible in the other by deleting $deleted$ number of characters, we print $deleted$.↵
</li>↵
<li>↵
$case 3:$ if it is possible to make $s$ a palindrome in both of our options, our answer will be the option that requires the minimum deletions.↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O( n)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(1)$↵
</li>↵
</ul>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
def count_deletions(c):↵
l, r = 0, n - 1↵
deleted = 0↵
while l < r:↵
if melodies[l] != melodies[r]:↵
if melodies[l] == c:↵
deleted += 1↵
l += 1↵
elif melodies[r] == c:↵
deleted += 1↵
r -= 1↵
else: # It's impossible to make 'melodies' a palindrome by deleting c↵
return float('inf')↵
else:↵
l += 1↵
r -= 1↵
↵
return deleted↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
melodies = input()↵
↵
is_palindrome = True↵
l, r = 0, n - 1↵
while l < r:↵
if melodies[l] != melodies[r]:↵
is_palindrome = False↵
break↵
l += 1↵
r -= 1↵
↵
if is_palindrome: #the given string is already a palindrome↵
print(0)↵
else:↵
deleted1 = count_deletions(melodies[l])↵
deleted2 = count_deletions(melodies[r])↵
↵
ans = min(deleted1, deleted2)↵
↵
print(ans if ans != float('inf') else -1)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [E. Equalizing Arrays](https://codeforces.net/gym/588468/problem/E)↵
↵
<spoiler summary = "Solution">↵
Let's prove that next greedy solution works: each step we will find prefixes of minimal length of arrays $A$ and $B$ such that its sums are equal and we will cut them forming next block. If we will get valid partition in result so it is an optimal solution, otherwise there is no solution. Since length of prefix proportional to its sum, so prefixes are minimal since its sums are↵
minimal.↵
↵
Let's prove this algorithm: let optimal solution have alternative partition. Since our solution cuts minimal possible prefixes, so (at some step) optimal solution cuts prefix with greater sum (and greater length). But this prefixes in optimal solutions contain smaller prefixes, found by greedy solution, so it can be divided on two parts — contradiction.↵
↵
So we can keep prefixes and increase one which have smaller sum.↵
↵
Time complexity: $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
n = int(sys.stdin.readline().strip())↵
a = list(map(int, sys.stdin.readline().strip().split()))↵
m = int(sys.stdin.readline().strip())↵
b = list(map(int, sys.stdin.readline().strip().split()))↵
↵
if sum(a) != sum(b):↵
print(-1)↵
exit()↵
↵
p1, p2 =0, 0↵
↵
cur_sum1, cur_sum2 = 0, 0↵
↵
ans = 0↵
↵
while p1 < n:↵
↵
cur_sum1 += a[p1]↵
cur_sum2 += b[p2]↵
p1 += 1↵
p2 += 1↵
↵
while cur_sum1 != cur_sum2:↵
if cur_sum1 < cur_sum2:↵
cur_sum1 += a[p1]↵
p1 += 1↵
else:↵
cur_sum2 += b[p2]↵
p2 += 1↵
ans += 1↵
print(ans)↵
```↵
</spoiler>↵
↵
### [F. Binary Substrings with Exactly k Ones](https://codeforces.net/gym/588468/problem/F) ↵
↵
<spoiler summary="Hint 1"> ↵
Consider how to count subarrays with at most \( k \) ones efficiently. Think about using a sliding window to maintain the number of ones. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Hint 2"> ↵
To find exactly \( k \) ones, calculate subarrays with at most \( k \) ones and subtract those with at most \( k-1 \) ones. ↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 1"> ↵
We need to find the number of subarrays containing exactly \( k \) ones. This can be done by calculating the number of subarrays with **at most** \( k \) ones and subtracting the number of subarrays with **at most** \( k-1 \) ones: ↵
\[↵
\text{Result} = \text{atmostk}(k) — \text{atmostk}(k-1)↵
\]↵
↵
The function `atmostk(k)` calculates the number of subarrays containing at most \( k \) ones using a sliding window approach:↵
- Two pointers (`left` and `right`) are used to maintain a window.↵
- Expand the window by moving `right`. If a '1' is encountered, increment the `count`.↵
- If `count` exceeds \( k \), move `left` until `count` is within the limit.↵
- For each position of `right`, add `right - left + 1` to the answer, as this is the number of subarrays ending at `right`.↵
↵
This approach works in \( O(n) \) time complexity because each pointer moves at most \( n \) times. ↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
```python3↵
k = int(input())↵
nums = input()↵
n = len(nums)↵
↵
def atmostk(k):↵
if k == -1:↵
return 0↵
↵
left = 0 ↵
count = 0↵
ans = 0↵
↵
# Expand window with right pointer↵
for right in range(n):↵
if nums[right] == "1":↵
count += 1 # Count the 1s in the window↵
↵
# If count exceeds k, shrink window from the left↵
while count > k:↵
if nums[left] == "1":↵
count -= 1 # Remove 1 from count↵
left += 1 ↵
↵
# Number of subarrays ending at right is (right - left + 1)↵
ans += right - left + 1↵
↵
return ans ↵
↵
# Subarrays with exactly k ones = atmostk(k) - atmostk(k-1)↵
print(atmostk(k) - atmostk(k-1)) ↵
``` ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3"> ↵
Try using prefix sums to keep track of the number of ones encountered so far. ↵
</spoiler>↵
↵
<spoiler summary="Hint 4"> ↵
Assume you are currently at the right end of a subarray. ↵
To find subarrays that sum to exactly \( k \), think about which prefix sum should be removed. ↵
The required prefix to remove is \( current\_sum — k \), since removing this would leave a subarray with a sum of \( k \). ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution 2"> ↵
Another approach is to use the **Subarray Sum Equals K** method, which utilizes prefix sums and a hash map to efficiently count subarrays with exactly \( k \) ones. ↵
- Maintain a running sum (`summ`) of elements as we traverse the array.↵
- Use a hash map (`count`) to store the frequency of each prefix sum.↵
- If the difference between the current sum and \( k \) has been seen before, then all subarrays ending at the current index with that prefix sum difference contribute to the answer.↵
- This works because the subarray sum equals \( k \) when the difference between the current sum and a previously seen sum is exactly \( k \).↵
↵
This solution also works in \( O(n) \) time complexity due to the single pass over the array and \( O(n) \) space complexity for the hash map. ↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
```python3↵
from collections import defaultdict↵
↵
k = int(input())↵
nums = list(map(int, list(input())))↵
↵
count = defaultdict(int) # Dictionary to store frequency of prefix sums↵
ans = 0↵
summ = 0↵
count[0] = 1 # To handle the case when subarray starts from index 0↵
↵
for val in nums:↵
summ += val # Calculate prefix sum↵
↵
# Check how many subarrays end at current index and sum to k↵
ans += count[summ-k]↵
↵
# Update the frequency of the current prefix sum↵
count[summ] += 1 ↵
↵
print(ans)↵
```↵
</spoiler>↵
↵
↵
### [A. Nth Digit in Sequence](https://codeforces.net/gym/588468/problem/A)↵
↵
<spoiler summary="Solution">↵
The problem requires us to find the `n-th` digit in an infinite sequence formed by concatenating all positive integers starting from 1.↵
### Observations:↵
1. The sequence starts as: `123456789101112131415...`, and we need to determine the digit at position \(n\).↵
2. A simple way to construct the sequence is to append numbers as strings until we reach the required length.↵
### Approach:↵
- Initialize an empty string `sequence`.↵
- Iterate from `1` onwards, converting each number to a string and appending it to `sequence`.↵
- Stop when `sequence` reaches at least `n` characters.↵
- Print the `n-th` digit (adjusting for 0-based indexing).↵
### Complexity Analysis:↵
Since numbers grow in length, the loop runs approximately `O(sqrt{n})` times, making the approach efficient.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
n = int(input())↵
sequence = ""↵
for num in range(1, 1000):↵
sequence += str(num)↵
if len(sequence) >= n: # You can stop early when sequence is long enough↵
break↵
print(sequence[n - 1])↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [B. Anansi and Trip-Photographs](https://codeforces.net/gym/588468/problem/B)↵
↵
<spoiler summary="Problem Understanding">↵
Anansi needs to arrange **2n** A2SVians into two rows:↵
- **Front row:** Shorter individuals.↵
- **Back row:** Taller individuals.↵
↵
Each person in the back row must be at least **x** units taller than the corresponding person in the front row.↵
↵
We need to determine if this arrangement is possible for each test case.↵
</spoiler>↵
↵
<spoiler summary="Hints">↵
<details> ↵
<summary>Hint 1</summary> ↵
How can sorting help in organizing the two rows optimally? ↵
</details> ↵
↵
<details> ↵
<summary>Hint 2</summary> ↵
Try to place the smallest `n` people in the front row and the largest `n` people in the back row. ↵
</details> ↵
↵
<details> ↵
<summary>Hint 3</summary> ↵
After sorting, check if every person in the back row is at least `x` units taller than their corresponding person in the front row. ↵
</details> ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
### **Approach**↵
1. **Sorting for optimal arrangement** ↵
- To maximize our chances of meeting the height requirement, we sort the heights in **non-decreasing order**.↵
- Assign:↵
- **Front row:** First `n` elements.↵
- **Back row:** Last `n` elements.↵
↵
2. **Checking the Condition** ↵
- Ensure that for every `j`:↵
\[↵
\text{back}[j] — \text{front}[j] \geq x↵
\]↵
- If all pairs satisfy the condition, print `"YES"`, otherwise print `"NO"`.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
↵
# Input handling↵
t = int(input()) # Number of test cases↵
for _ in range(t):↵
n, x = map(int, input().split()) # Read n and x↵
heights = list(map(int, input().split())) # Read 2n heights↵
↵
heights.sort() # Step 1: Sort the heights↵
front_row = heights[:n] # Step 2: First n people go to the front row↵
back_row = heights[n:] # Step 3: Last n people go to the back row↵
↵
# Step 4: Check if each person in the back row is at least x units taller↵
for j in range(n):↵
if back_row[j] - front_row[j] < x:↵
print("NO")↵
break↵
else:↵
print("YES")↵
```↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
### **Time Complexity**↵
1. **Sorting the array:** \(O(2n \log (2n)) = O(n \log n)\)↵
2. **Splitting into front and back rows:** \(O(n)\)↵
3. **Checking the height condition:** \(O(n)\)↵
↵
**Total Time Complexity:** ↵
\[↵
O(n \log n) + O(n) + O(n) = O(n \log n)↵
\]↵
which is efficient for \( n \leq 100 \).↵
↵
### **Space Complexity**↵
1. **Input storage:** \(O(2n)\) for storing heights.↵
2. **Two separate lists:** \(O(n)\) each for front and back row.↵
3. **Overall auxiliary space:** \(O(n)\)↵
↵
Since sorting is done in-place, **Total Space Complexity = O(n)**.↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [C. Minimal TV Subscriptions](https://codeforces.net/gym/588468/problem/C)↵
↵
<spoiler summary="Hint"> To solve this problem efficiently, consider how the shows are distributed over the days and how you can dynamically track the number of unique shows in each window of consecutive days. </spoiler>↵
↵
↵
↵
<spoiler summary="Solution"> <p> The problem asks us to determine the minimum number of TV show subscriptions needed to ensure that we can watch at least <b>d</b> consecutive days without missing any episodes. The key is to use a sliding window approach to efficiently count the number of unique shows in each window of <b>d</b> consecutive days. <ul> <li><b>Sliding Window:</b> We first initialize a window with the first <b>d</b> shows and count how many unique shows are in that window using a hash table (Counter). Then, as the window slides forward by one day, we update the count of unique shows by adding the new day’s show and removing the show that is no longer in the window.</li> <li><b>Efficiency:</b> Instead of recalculating the number of unique shows for every possible window from scratch, we only adjust the window by removing one show and adding another, making the solution efficient.</li> </ul> <p> We start by counting the unique shows in the first <b>d</b> days. As the window slides through the entire schedule, we keep track of the minimum number of unique shows across all windows of length <b>d</b>. This minimum gives us the answer. </p> </p> </spoiler>↵
↵
↵
↵
<spoiler summary="Code"> ↵
```python ↵
from collections import Counter, defaultdict, deque↵
t = int(input()) # Number of test cases↵
for _ in range(t):↵
n, k, d = map(int, input().split()) # Read values for n, k, d↵
arr = list(map(int, input().split())) # Read the show schedule↵
window = Counter(arr[:d]) # Initialize window with first 'd' shows↵
ans = len(window) # Track minimum unique shows↵
↵
for i in range(d, n): # Slide the window through the array↵
window[arr[i]] += 1 # Add new show to window↵
window[arr[i - d]] -= 1 # Remove old show from window↵
↵
if window[arr[i - d]] == 0: # Remove show from counter if it no longer exists in window↵
del window[arr[i - d]]↵
↵
ans = min(ans, len(window)) # Update the minimum unique shows↵
↵
print(ans) # Output the result for the test case↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [D. Bernabas and the Harmonious Melody](https://codeforces.net/gym/588468/problem/D)↵
↵
<spoiler summary = "Solution">↵
<p>↵
Let’s initialize two pointers $l$ and $r$ at the beginning and at the end of the given string $s$. We will move $l$ to the right and $r$ to the left is $s[l]$ == $s[r]$. If $l$ and $r$ become equal or move past each other at some point, that means the given string is a palindrome and we don’t need to delete any character. Our answer in this case would be $0$.↵
</p>↵
↵
<p>↵
If that is not the case then $s[l]$ != $s[r]$ at some point. Since we are only allowed to delete one character, to make$s$ a palindrome, one of these characters must be deleted. We try deleting each character separately and we will take the alternative that requires minimum deletion. If it’s not possible to make $s$ a palindrome in both cases, we will print $-1). ↵
</p>↵
↵
<p>↵
So, the first time $s[l]$ becomes different from $s[r]$, let’s say deleting the character $c$ = $s[l]$ is our first option. We will have a variable $deleted$ to count the number of characters we will delete to try to make $s$ a palindrome. So every time $s[l]$ is not equal to $s[r]$, if either of them are equal to $c$, we can increment $deleted$ by one and move the pointer that’s pointing at a character that is equal to $c$. If $l$ becomes greater or equal to $r$, that means by deleting $deleted$ number of character $c$, we successfully made $s$ a palindrome. We do the same for the other case, $c$ = $s[r]$ as well, and print the option that requires minimum deletions. We have three cases↵
</p>↵
↵
<ul>↵
<li>↵
$case 1:$ if it is not possible to make $s$ a palindrome in both of our options, we print $-1$.↵
</li>↵
↵
<li>↵
$case 2:$ if it is not possible to make $s$ a palindrome in one of the options, and possible in the other by deleting $deleted$ number of characters, we print $deleted$.↵
</li>↵
<li>↵
$case 3:$ if it is possible to make $s$ a palindrome in both of our options, our answer will be the option that requires the minimum deletions.↵
</li>↵
</ul>↵
↵
<ul>↵
<li>↵
$\text{Time Complexity: } O( n)$↵
</li>↵
<li>↵
$\text{Space Complexity: } O(1)$↵
</li>↵
</ul>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
def count_deletions(c):↵
l, r = 0, n - 1↵
deleted = 0↵
while l < r:↵
if melodies[l] != melodies[r]:↵
if melodies[l] == c:↵
deleted += 1↵
l += 1↵
elif melodies[r] == c:↵
deleted += 1↵
r -= 1↵
else: # It's impossible to make 'melodies' a palindrome by deleting c↵
return float('inf')↵
else:↵
l += 1↵
r -= 1↵
↵
return deleted↵
↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
melodies = input()↵
↵
is_palindrome = True↵
l, r = 0, n - 1↵
while l < r:↵
if melodies[l] != melodies[r]:↵
is_palindrome = False↵
break↵
l += 1↵
r -= 1↵
↵
if is_palindrome: #the given string is already a palindrome↵
print(0)↵
else:↵
deleted1 = count_deletions(melodies[l])↵
deleted2 = count_deletions(melodies[r])↵
↵
ans = min(deleted1, deleted2)↵
↵
print(ans if ans != float('inf') else -1)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### [E. Equalizing Arrays](https://codeforces.net/gym/588468/problem/E)↵
↵
<spoiler summary = "Solution">↵
Let's prove that next greedy solution works: each step we will find prefixes of minimal length of arrays $A$ and $B$ such that its sums are equal and we will cut them forming next block. If we will get valid partition in result so it is an optimal solution, otherwise there is no solution. Since length of prefix proportional to its sum, so prefixes are minimal since its sums are↵
minimal.↵
↵
Let's prove this algorithm: let optimal solution have alternative partition. Since our solution cuts minimal possible prefixes, so (at some step) optimal solution cuts prefix with greater sum (and greater length). But this prefixes in optimal solutions contain smaller prefixes, found by greedy solution, so it can be divided on two parts — contradiction.↵
↵
So we can keep prefixes and increase one which have smaller sum.↵
↵
Time complexity: $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
n = int(sys.stdin.readline().strip())↵
a = list(map(int, sys.stdin.readline().strip().split()))↵
m = int(sys.stdin.readline().strip())↵
b = list(map(int, sys.stdin.readline().strip().split()))↵
↵
if sum(a) != sum(b):↵
print(-1)↵
exit()↵
↵
p1, p2 =0, 0↵
↵
cur_sum1, cur_sum2 = 0, 0↵
↵
ans = 0↵
↵
while p1 < n:↵
↵
cur_sum1 += a[p1]↵
cur_sum2 += b[p2]↵
p1 += 1↵
p2 += 1↵
↵
while cur_sum1 != cur_sum2:↵
if cur_sum1 < cur_sum2:↵
cur_sum1 += a[p1]↵
p1 += 1↵
else:↵
cur_sum2 += b[p2]↵
p2 += 1↵
ans += 1↵
print(ans)↵
```↵
</spoiler>↵
↵
### [F. Binary Substrings with Exactly k Ones](https://codeforces.net/gym/588468/problem/F) ↵
↵
<spoiler summary="Hint 1"> ↵
Consider how to count subarrays with at most \( k \) ones efficiently. Think about using a sliding window to maintain the number of ones. ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Hint 2"> ↵
To find exactly \( k \) ones, calculate subarrays with at most \( k \) ones and subtract those with at most \( k-1 \) ones. ↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 1"> ↵
We need to find the number of subarrays containing exactly \( k \) ones. This can be done by calculating the number of subarrays with **at most** \( k \) ones and subtracting the number of subarrays with **at most** \( k-1 \) ones: ↵
\[↵
\text{Result} = \text{atmostk}(k) — \text{atmostk}(k-1)↵
\]↵
↵
The function `atmostk(k)` calculates the number of subarrays containing at most \( k \) ones using a sliding window approach:↵
- Two pointers (`left` and `right`) are used to maintain a window.↵
- Expand the window by moving `right`. If a '1' is encountered, increment the `count`.↵
- If `count` exceeds \( k \), move `left` until `count` is within the limit.↵
- For each position of `right`, add `right - left + 1` to the answer, as this is the number of subarrays ending at `right`.↵
↵
This approach works in \( O(n) \) time complexity because each pointer moves at most \( n \) times. ↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
```python3↵
k = int(input())↵
nums = input()↵
n = len(nums)↵
↵
def atmostk(k):↵
if k == -1:↵
return 0↵
↵
left = 0 ↵
count = 0↵
ans = 0↵
↵
# Expand window with right pointer↵
for right in range(n):↵
if nums[right] == "1":↵
count += 1 # Count the 1s in the window↵
↵
# If count exceeds k, shrink window from the left↵
while count > k:↵
if nums[left] == "1":↵
count -= 1 # Remove 1 from count↵
left += 1 ↵
↵
# Number of subarrays ending at right is (right - left + 1)↵
ans += right - left + 1↵
↵
return ans ↵
↵
# Subarrays with exactly k ones = atmostk(k) - atmostk(k-1)↵
print(atmostk(k) - atmostk(k-1)) ↵
``` ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3"> ↵
Try using prefix sums to keep track of the number of ones encountered so far. ↵
</spoiler>↵
↵
<spoiler summary="Hint 4"> ↵
Assume you are currently at the right end of a subarray. ↵
To find subarrays that sum to exactly \( k \), think about which prefix sum should be removed. ↵
The required prefix to remove is \( current\_sum — k \), since removing this would leave a subarray with a sum of \( k \). ↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution 2"> ↵
Another approach is to use the **Subarray Sum Equals K** method, which utilizes prefix sums and a hash map to efficiently count subarrays with exactly \( k \) ones. ↵
- Maintain a running sum (`summ`) of elements as we traverse the array.↵
- Use a hash map (`count`) to store the frequency of each prefix sum.↵
- If the difference between the current sum and \( k \) has been seen before, then all subarrays ending at the current index with that prefix sum difference contribute to the answer.↵
- This works because the subarray sum equals \( k \) when the difference between the current sum and a previously seen sum is exactly \( k \).↵
↵
This solution also works in \( O(n) \) time complexity due to the single pass over the array and \( O(n) \) space complexity for the hash map. ↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
```python3↵
from collections import defaultdict↵
↵
k = int(input())↵
nums = list(map(int, list(input())))↵
↵
count = defaultdict(int) # Dictionary to store frequency of prefix sums↵
ans = 0↵
summ = 0↵
count[0] = 1 # To handle the case when subarray starts from index 0↵
↵
for val in nums:↵
summ += val # Calculate prefix sum↵
↵
# Check how many subarrays end at current index and sum to k↵
ans += count[summ-k]↵
↵
# Update the frequency of the current prefix sum↵
count[summ] += 1 ↵
↵
print(ans)↵
```↵
</spoiler>↵
↵
