Special thanks to feysel_mubarek for preparing the contest.
Our goal is to detect if the situation is dangerous or not. The condition we need to check is 7 players of the same team standing one after the other. so what we can do is count contiguous players of the same team. Iterate through the given string and compare each value at current index with the value of the previous index, if equal increment our count else assign count equal to 1. If count reaches 7 it means the situations is dangerous then print "YES".
s = input() curr = 1 for i in range(1,len(s)): if s[i-1] != s[i]: curr = 0 curr += 1 if curr >= 7: print('YES') break else: print('NO')
- Time complexity — $$$O(n)$$$
- Space complexity — $$$O(1)$$$
Lets make some observations, if there were no constraints we could make a total of (a+b)//4 teams. the number of teams we can make is limited by min(a, b) because the smaller number(say mathematicians) will be the limiting factor and some of the larger number(say programmers) will be left without a team. So we can deduce that the possible amount of teams is min((a+b)/4, a, b) for example say a = 10 and b = 2 we can see that its not possible to create more than two teams due to the given constraint so min((2+10)/4, min(2,10)) == 2 lets say a=3 and b=2 here it might look like b=2 is the limiting factor and the answer, but notice that its not logically possible to make 2 teams of 4 from 5 individuals so this time what limits us is actually (a+b)//4. min((2+3)//4, 2, 3) == 1.
for _ in range(int(input())): a, b = map(int, input().split()) print(min((a+b)//4, a, b))
- Time complexity: $$$O(1)$$$
- Space complexity: $$$O(1)$$$
Binary search on Answer.
def is_valid(a, b, teams): return min(a, b) >= teams and a + b >= 4 * teams def solve(a, b): lo, hi = 0, min(a,b) best = 0 while lo <= hi: mid = (lo + hi) // 2 if is_valid(a, b, mid): best = mid lo = mid + 1 else: hi = mid - 1 return best t = int(input()) res =  for _ in range(t): a, b = map(int, input().split()) res.append(solve(a,b)) print(*res, sep="\n")
- Time complexity — $$$O(logn)$$$
- Space complexity — $$$O(1)$$$
For better illustration of the problem analysis let's go through this train of thought, first considering the string "usknnruu": We would start from the first left side of the string and write how many versions we would build up from the letters: u — 1 us — 1 usk — 1 uskn — 1 usknn — 2 : NOW we spot two consecutive n's which could have been interpreted by the machine as really "nn" or "m" thus leaving us with two cases (one case is we added to the previous string "uskn" + the other case is we added m to the previous previous string "usk"): LEADING TO VERSIONS "usknn, uskm" usknnr — 2: LEADING TO VERSIONS "usknnr", "uskmr" usknnru — 2: LEADING TO VERSIONS "usknnru", "uskmru" usknnruu — 4 (since we add u to the previous two strings: LEADING TO VERSIONS "usknnruu, uskmru" + we add w to the previous previous strings: LEADING TO VERSIONS "usknnrw", "uskmrw")
so at last we return 4 but the problem with this is we didn't consider the case "uu". If we had done it like earlier: u — 1 uu — 1 (it should have been 2 since we have two cases "uu" and "w" but we don't know how to construct "w")
So, we need to consider an empty string "" — 1 (in-case we have consecutive u's or n's at first it'll hold the w or m) u — 1 uu — 2 (cause we add u to the previous string: LEADING TO VERSION "uu" and we add w to the previous previous string: LEADING TO VERSION "w")
So overall, this is what we were doing: - Maintaining (keeping) the same version number as we added distinct letters - When we got consecutive u's or n's (like when we had processed the letter u previously and the coming letter is again u), we add the version of the previous string + the version of the previous previous string
Look closely, looks like we're building it up (constructing using DP-bottom up approach :D) Implementation detail hint: Use an array sized [0-n+1] and make sure the 0th and 1st index of the array is set to 1 (we saw the empty string proof earlier and a string with size 1 has only a version of 1)
And one last note: if the string includes "m" or "w", we should return 0 at once. Since the machine didn't mess with it if it included m or w in the first place.
def solve(s,m): n = len(s) for val in s: if val == "m" or val == "w": return 0 array =  * (n+1) for i in range(2, n+1): if s[i-2:i] == "nn" or s[i-2:i] == "uu": array[i] = (array[i-1] + array[i-2] ) % m else: array[i] = array[i-1] return array[n] s = int(input()) MOD = 10**9 + 7 print(solve(s, MOD))
- Time Complexity: O(n)
- Space Complexity: O(n+1)
The first thing to notice is that it's always optimal to perform the operation on the character that appears first on the string. Let's say the first character that appears first is E, then the we should repeatedly apply the operation on letter on that position (i.e. E->D->C->B->A). After performing these operations, there's nothing you can do for the first character so you can move to the next character on the string. At this point, if the character you encounter is lexicographically lower than the highest character you have seen so far (in this case E), you can just convert it to A without any cost (because it would have changed to A while you were applying the operations in the past). Furthermore, if you find a letter that's higher, say F, it would cost you 1 operation to get it down to A (Think if you rearranged the operations so that you did F->E before you did the other operations).
One additional point, is that if you don't have enough points to get a character (say Q) all the way to A. In this case, you use all the operations to get it as low as possible (Say G) and then continue to the other characters and if they are below or equal to Q but above G then you can convert it to G, but otherwise continue till the end.
t = int(input()) for _ in range(t): _, m = list(map(int, input().split())) s = input() max_changed = 'a' top_level = 'a' ceil_change = 'a' answer =  for c in s: if c <= max_changed: answer.append('a') continue if ord(c) - ord(max_changed) > m: if m > 0: ceil_change = chr(ord(c) - m) top_level = c m = 0 if c <= top_level: answer.append(min(c, ceil_change)) else: answer.append(c) else: m -= ord(c) - ord(max_changed) max_changed = c answer.append('a') print("".join(answer))
- Time complexity: $$$O(n)$$$
- Space complexity: $$$O(1)$$$ additional pace complexity