[Here](https://mirror.codeforces.com/contestInvitation/070264bf688e0218f036c17bf3cc720a3cef213f) is the mashup link (the problems are from Codeforces' problem set).↵
#### [A. Digit Diversity Challenge](https://mirror.codeforces.com/gym/504570/problem/A)↵
↵
<spoiler summary = "Solution">↵
Let's see how to check if all digits of $x$ are different. Since there can be only $10$ different numbers($0$ to $9$) in single digit, you can count the occurrences of $10$ numbers by looking all digits of $x$. You can count all digits by using modulo $10$ or changing whole number to string.↵
↵
For example, if $x = 1217$, then occurrence of each number will be $[0, 2, 1, 0, 0, 0, 0, 1, 0, 0]$, because there are two $1$s, single $2$ and single $7$ in $x$. So $1217$ is invalid number.↵
↵
Now do the same thing for all $x$ where $l \le x \le r$. If you find any valid number then print it. Otherwise print $-1$.↵
↵
Time complexity is $O((r-l) \log r)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
# Return if given number's digits are distinct.↵
def is_distinct(x):↵
return len(set(str(x))) == len(str(x))↵
↵
L, R = map(int, input().split())↵
↵
found = False↵
for i in range(L, R+1):↵
if is_distinct(i):↵
found = True↵
print(i)↵
break↵
↵
if not found:↵
print(-1)↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Palindrome Formation](https://mirror.codeforces.com/gym/504570/problem/B)↵
↵
<spoiler summary = "Hint">↵
<p>↵
Sort the array in ascending order.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:↵
↵
1. Sort the list of programming skills in ascending order.↵
2. Initialize two pointers, $start$ and $end$, both pointing to the beginning of the sorted list.↵
3. Iterate over the list using pointer $start$, and for each student skill $(skills[start])$, move pointer $(end)$ forward until the difference between the current skill `$(skills[end])$ and $(skills[start])$ exceeds 5.↵
4. At each iteration, update the maximum number of students in a balanced team $(maxNum)$ by taking the maximum between the current value of $maxNum$ and the difference between $end$ and $start$.↵
5. Finally, output the maximum number of students in a balanced team $(maxNum)$.↵
↵
↵
Time Complexity: Sorting the list takes O(n log n) time. The iteration over the sorted list takes O(n) time. Thus, the overall time complexity is O(n log n). ↵
↵
Space Complexity: Sorting requires O(1)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
n = int(input())↵
skills = sorted(map(int, input().split()))↵
↵
maxNum = 0↵
end = 0↵
↵
for start in range(n):↵
↵
while end < n and skills[end] - skills[start] <= 5:↵
end += 1↵
maxNum = max(maxNum, end - start)↵
↵
print(maxNum)↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Exam Results](https://mirror.codeforces.com/gym/504570/problem/C)↵
↵
<spoiler summary = "Solution">↵
Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness.to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. ↵
Total complexity: $O(n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
n = int(input())↵
nums = list(map(int, input().split()))↵
count = Counter(nums)↵
ans = 0↵
while len(count) > 0:↵
ans += (len(count) - 1)↵
keys = list(count.keys())↵
for key in keys:↵
count[key] -= 1↵
if count[key] == 0:↵
del count[key]↵
print(ans)↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [D. Skillful Group](https://mirror.codeforces.com/gym/504570/problem/D)↵
↵
<spoiler summary = "Hint">↵
<p>On the constraints, the size of the array cannot be larger than 2000.</p>↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
<p>↵
We can use two pointers (non-linearly). One starts from the zero, and stores the numbers in a set (left set) to mark them as seen. For every position on the left, as long as the items in the left set are unique, we use a right pointer and move backwards as long as the number on the right pointer satisfies following conditions:↵
<ul>↵
<li>It is not in the left set.</li> <li>The number is not repeated on the right (we can use a right set for every left).</li>↵
</ul>↵
<br>↵
This way we track the minimum distance between left and right. ↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
min_segment = float('inf')↵
left_seen = set()↵
a.append(0) # appended to handle edge cases (to avoid writing if conditions) ↵
↵
for left in range(n):↵
↵
num = a[left]↵
right_seen = set()↵
↵
for right in range(n, left - 1, -1):↵
if a[right] in left_seen or a[right] in right_seen:↵
break↵
↵
right_seen.add(a[right])↵
min_segment = min(min_segment, right - left)↵
↵
if num in left_seen:↵
break↵
↵
left_seen.add(num)↵
↵
↵
print(min_segment)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [E. 'a' Special Substring](https://mirror.codeforces.com/gym/504570/problem/E)↵
↵
<spoiler summary = "Hint 1">↵
Think about small substrings.↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
What are the strings that satisfy the given conditions?↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3">↵
If you got Wrong Answer on test $2$, then you're probably not checking $7$ length strings.↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
The following are all the possible minimal substrings (there aren't that many) which satisfy the given conditions: "aa", "aba", "aca", "abca", "acba", "abbacca", "accabba". Any other string that satisfies the condition contains at least one of these as a substring, and hence is not the optimal substring for the answer.↵
↵
**Claim:** If a substring exists which satisfies the given conditions, then the length of the shortest such substring is at most $7$. Otherwise the solution does not exist.↵
↵
**Proof:** Let us consider that the solution exists. We will try to prove this by breaking this into the following cases:↵
↵
**Case 1:** There exist two such "a" whose distance is less than or equal to $2$, where distance is the absolute difference of their indices.↵
↵
- In this case where there are two such "a" whose distance is less than $2$, then either these two "a" are present consecutive or there is only one single letter between these two "a". All these minimal substrings are "aa", "aba" and "aca" which satisfies all the given conditions.↵
Hence we can say that the shortest length of such substring that satisfies the given conditions is at most $3$ in this case.↵
↵
**Case 2:** There exists no two such "a" whose distance is less than or equal to $2$.↵
↵
- In this case all the consecutive occurrences of "a" are present at a distance at least $3$. Then in order for the number of "a" to be bigger than that of "b" and "c" the string must look like "a??a??a??a??a".↵
- Let us define "??" as a block. Now if there is any block consisting of different characters $i.e$ "bc" or "cb" then the substring "a??a" will satisfy all the given conditions and hence the minimal length will be $4$.↵
- Notice that there must be at least one block of "bb" and at least one block of "cc", otherwise "a" will not be in a majority. Hence, there must exist 2 consecutive blocks equal to "bb" and "cc" or "cc" and "bb" in the string (otherwise all blocks would be of the same character). Hence we can pick the substring "abbacca" or "accabba" which satisfies the given conditions. The minimal length is, therefore, $7$ in this case.↵
↵
Therefore we can say that the shortest length of such substring that satisfies the given conditions is at most $7$ in this case.↵
↵
Thus, it suffices to only check all substrings of length up to $7$ and find the smallest among them that satisfies the given conditions (or report that it does not exist).↵
↵
Time Complexity: $\mathcal{O}(7⋅n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline()[:-1]↵
↵
↵
T = int(input())↵
↵
for _ in range(T):↵
N = int(input())↵
s = input()↵
↵
if "aa" in s:↵
print(2)↵
elif "aba" in s or "aca" in s:↵
print(3)↵
elif "abca" in s or "acba" in s:↵
print(4)↵
elif "abbacca" in s or "accabba" in s:↵
print(7)↵
else:↵
print(-1)↵
```↵
</spoiler>↵
↵
↵
#### [A. Digit Diversity Challenge](https://mirror.codeforces.com/gym/504570/problem/A)↵
↵
<spoiler summary = "Solution">↵
Let's see how to check if all digits of $x$ are different. Since there can be only $10$ different numbers($0$ to $9$) in single digit, you can count the occurrences of $10$ numbers by looking all digits of $x$. You can count all digits by using modulo $10$ or changing whole number to string.↵
↵
For example, if $x = 1217$, then occurrence of each number will be $[0, 2, 1, 0, 0, 0, 0, 1, 0, 0]$, because there are two $1$s, single $2$ and single $7$ in $x$. So $1217$ is invalid number.↵
↵
Now do the same thing for all $x$ where $l \le x \le r$. If you find any valid number then print it. Otherwise print $-1$.↵
↵
Time complexity is $O((r-l) \log r)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
# Return if given number's digits are distinct.↵
def is_distinct(x):↵
return len(set(str(x))) == len(str(x))↵
↵
L, R = map(int, input().split())↵
↵
found = False↵
for i in range(L, R+1):↵
if is_distinct(i):↵
found = True↵
print(i)↵
break↵
↵
if not found:↵
print(-1)↵
```↵
</spoiler>↵
↵
↵
↵
#### [B. Palindrome Formation](https://mirror.codeforces.com/gym/504570/problem/B)↵
↵
<spoiler summary = "Hint">↵
<p>↵
Sort the array in ascending order.↵
</p>↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:↵
↵
1. Sort the list of programming skills in ascending order.↵
2. Initialize two pointers, $start$ and $end$, both pointing to the beginning of the sorted list.↵
3. Iterate over the list using pointer $start$, and for each student skill $(skills[start])$, move pointer $(end)$ forward until the difference between the current skill `$(skills[end])$ and $(skills[start])$ exceeds 5.↵
4. At each iteration, update the maximum number of students in a balanced team $(maxNum)$ by taking the maximum between the current value of $maxNum$ and the difference between $end$ and $start$.↵
5. Finally, output the maximum number of students in a balanced team $(maxNum)$.↵
↵
↵
Time Complexity: Sorting the list takes O(n log n) time. The iteration over the sorted list takes O(n) time. Thus, the overall time complexity is O(n log n). ↵
↵
Space Complexity: Sorting requires O(1)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python↵
↵
n = int(input())↵
skills = sorted(map(int, input().split()))↵
↵
maxNum = 0↵
end = 0↵
↵
for start in range(n):↵
↵
while end < n and skills[end] - skills[start] <= 5:↵
end += 1↵
maxNum = max(maxNum, end - start)↵
↵
print(maxNum)↵
↵
```↵
</spoiler>↵
↵
↵
#### [C. Exam Results](https://mirror.codeforces.com/gym/504570/problem/C)↵
↵
<spoiler summary = "Solution">↵
Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness.to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. ↵
Total complexity: $O(n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
n = int(input())↵
nums = list(map(int, input().split()))↵
count = Counter(nums)↵
ans = 0↵
while len(count) > 0:↵
ans += (len(count) - 1)↵
keys = list(count.keys())↵
for key in keys:↵
count[key] -= 1↵
if count[key] == 0:↵
del count[key]↵
print(ans)↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [D. Skillful Group](https://mirror.codeforces.com/gym/504570/problem/D)↵
↵
<spoiler summary = "Hint">↵
<p>On the constraints, the size of the array cannot be larger than 2000.</p>↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
<p>↵
We can use two pointers (non-linearly). One starts from the zero, and stores the numbers in a set (left set) to mark them as seen. For every position on the left, as long as the items in the left set are unique, we use a right pointer and move backwards as long as the number on the right pointer satisfies following conditions:↵
<ul>↵
<li>It is not in the left set.</li> <li>The number is not repeated on the right (we can use a right set for every left).</li>↵
</ul>↵
<br>↵
This way we track the minimum distance between left and right. ↵
</p>↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
min_segment = float('inf')↵
left_seen = set()↵
a.append(0) # appended to handle edge cases (to avoid writing if conditions) ↵
↵
for left in range(n):↵
↵
num = a[left]↵
right_seen = set()↵
↵
for right in range(n, left - 1, -1):↵
if a[right] in left_seen or a[right] in right_seen:↵
break↵
↵
right_seen.add(a[right])↵
min_segment = min(min_segment, right - left)↵
↵
if num in left_seen:↵
break↵
↵
left_seen.add(num)↵
↵
↵
print(min_segment)↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
#### [E. 'a' Special Substring](https://mirror.codeforces.com/gym/504570/problem/E)↵
↵
<spoiler summary = "Hint 1">↵
Think about small substrings.↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
What are the strings that satisfy the given conditions?↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3">↵
If you got Wrong Answer on test $2$, then you're probably not checking $7$ length strings.↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
The following are all the possible minimal substrings (there aren't that many) which satisfy the given conditions: "aa", "aba", "aca", "abca", "acba", "abbacca", "accabba". Any other string that satisfies the condition contains at least one of these as a substring, and hence is not the optimal substring for the answer.↵
↵
**Claim:** If a substring exists which satisfies the given conditions, then the length of the shortest such substring is at most $7$. Otherwise the solution does not exist.↵
↵
**Proof:** Let us consider that the solution exists. We will try to prove this by breaking this into the following cases:↵
↵
**Case 1:** There exist two such "a" whose distance is less than or equal to $2$, where distance is the absolute difference of their indices.↵
↵
- In this case where there are two such "a" whose distance is less than $2$, then either these two "a" are present consecutive or there is only one single letter between these two "a". All these minimal substrings are "aa", "aba" and "aca" which satisfies all the given conditions.↵
Hence we can say that the shortest length of such substring that satisfies the given conditions is at most $3$ in this case.↵
↵
**Case 2:** There exists no two such "a" whose distance is less than or equal to $2$.↵
↵
- In this case all the consecutive occurrences of "a" are present at a distance at least $3$. Then in order for the number of "a" to be bigger than that of "b" and "c" the string must look like "a??a??a??a??a".↵
- Let us define "??" as a block. Now if there is any block consisting of different characters $i.e$ "bc" or "cb" then the substring "a??a" will satisfy all the given conditions and hence the minimal length will be $4$.↵
- Notice that there must be at least one block of "bb" and at least one block of "cc", otherwise "a" will not be in a majority. Hence, there must exist 2 consecutive blocks equal to "bb" and "cc" or "cc" and "bb" in the string (otherwise all blocks would be of the same character). Hence we can pick the substring "abbacca" or "accabba" which satisfies the given conditions. The minimal length is, therefore, $7$ in this case.↵
↵
Therefore we can say that the shortest length of such substring that satisfies the given conditions is at most $7$ in this case.↵
↵
Thus, it suffices to only check all substrings of length up to $7$ and find the smallest among them that satisfies the given conditions (or report that it does not exist).↵
↵
Time Complexity: $\mathcal{O}(7⋅n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
from sys import stdin↵
↵
↵
def input(): return stdin.readline()[:-1]↵
↵
↵
T = int(input())↵
↵
for _ in range(T):↵
N = int(input())↵
s = input()↵
↵
if "aa" in s:↵
print(2)↵
elif "aba" in s or "aca" in s:↵
print(3)↵
elif "abca" in s or "acba" in s:↵
print(4)↵
elif "abbacca" in s or "accabba" in s:↵
print(7)↵
else:↵
print(-1)↵
```↵
</spoiler>↵
↵
↵
