A subsequence doesn't have to be a continuous segment of a string. So the problem reduces to keeping track of the number of appearances of each character in the string.

This can be implemented by maintaining an array of size 26, where $$$arr[i]$$$ represents the number of appearances of the $$${i}^{th}$$$ character. For each query we can increment the count of the respective character. The answer of each query is the largest $$$arr[i]$$$.

Time Complexity: $$$ O(N+Q)$$$

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned _, i;
    cin >> _;
    while(_--){
        int n, q;
        cin >> n >> q;
        string str;
        cin >> str;

        vector<int> arr(26);
        int max_count = 0;
        for(i=0; i<n; i++){
            arr[str[i]-'a']++;
            max_count = max(max_count, arr[str[i]-'a']);
        }

        cout << max_count << " ";
        int idx;
        char chr;
        while(q--){
            cin >> idx >> chr;
            arr[chr-'a']++;
            max_count = max(max_count, arr[chr-'a']);
            cout << max_count << " ";
        }
        cout << "\n";
    }
    return 0;
}

from collections import Counter
for _ in range(int(input())):
    n, k = map(int, input().split())
    c = Counter(input())
    ans = [max(c.values())]
    for _ in range(k):
        c[input().split()[1]] += 1
        ans.append(max(c.values()))
    print(*ans)

Let's say Waldo is on pad $$$i$$$ and the next chocolate is present at $$$j$$$. It will take $$$j-i$$$ days for him to obtain it currently, and on the next day this count will reduce to $$$j-i-1$$$ and so on until he obtains the chocolate. After which this process repeats for a new $$$i$$$ and $$$j$$$.

It is sufficient to keep track of the day number and the current target chocolate. Once the target chocolate is obtained just continue the calculation with the next target chocolate.

Time Complexity: $$$ O(N)$$$

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned _, i, j;
    cin >> _;
    while(_--){
        unsigned n, m;
        cin >> n >> m;
        vector<int> pad(m);
        for(i=0; i<m; i++){
            cin >> pad[i];
        }

        for(int day_no=1, j=0; day_no<=n, j<m; j++){
            while(day_no<=pad[j]){
                cout << pad[j]-day_no << " ";
                day_no++; 
            }
        }
        cout << "\n";
    }
    return 0;
}

T = int(input())
ct = 0
while T > 0:
    N, M = map(int, input().split())
    store = list(map(int, input().split()))
    ct += N
    j = 0
    i = 1

    while i <= N:
        while i <= store[j]:
            print(store[j] - i, end=" ")
            i += 1
        j += 1
    print()
    T -= 1

For the least number of steps, assuming a solution exists, it will be sufficient to reduce all the elements to their GCD. If we divide all array elements by their GCD, it will sufficient find the number of steps to make them all 1.

To find this number of steps, we can count all their factors and the number of times they divide the elements. If there exists a factor that is not 2 nor 3 nor 5, the task is impossible.

Time Complexity: $$$ O(N\sqrt{A}\log{A}), A = max(A_i)$$$

#include <bits/stdc++.h>
using namespace std;

map<int, int> factor;
void prime_factorize(int n){
    if(n%2==0){
        do{
            factor[2]++;
            n/=2;
        }while(n%2==0);
    }
    for(int x=3; x*x<=n; x+=2){
        if(n%x==0){
            do{
                factor[x]++;
                n/=x;
            }while(n%x==0);
        }
    }
    if(n>1){
        factor[n]++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, g=0, i;
    cin >> n;
    vector<int> arr(n);
    for(i=0; i<n; i++){
        cin >> arr[i];
        g = __gcd(g, arr[i]);
    }

    for(i=0; i<n; i++){
        arr[i] /= g;
        prime_factorize(arr[i]);
    }

    int answer = 0; 
    for(auto x: factor){
        if(x.first>5){
            answer = -1;
            break;
        }
        answer += x.second;
    }

    cout << answer << "\n";
    return 0;
}

import math

def gcd(a, b):
    while b % a != 0:
        a, b = b % a, a
    return a

n = int(input())
arr = list(map(int, input().split()))
g = arr[0]

for i in range(n):
    g = gcd(min(g, arr[i]), max(g, arr[i]))

for i in range(n):
    arr[i] //= g

mp = {}
for i in range(n):
    x = arr[i]
    for j in range(2, int(math.sqrt(x)) + 1):
        while x % j == 0:
            x //= j
            if j in mp:
                mp[j] += 1
            else:
                mp[j] = 1
    if x != 1:
        if x in mp:
            mp[x] += 1
        else:
            mp[x] = 1

flag = False
ans = 0
for d, count in mp.items():
    if d == 2 or d == 3 or d == 5:
        ans += count
    else:
        flag = True
        break

if flag:
    print(-1)
else:
    print(ans)

Say any $$$i$$$ be one number in the pair that satisfies the condition. The minimum possible second number of the pair is $$$\lceil{\frac{M}{i}}\rceil$$$. It is sufficient to traverse for values of $$$i$$$ by brute-force.

Time Complexity: $$$ O(min(N, \sqrt{M}))$$$

#include <bits/stdc++.h>
using namespace std; 

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long N, M, i;
    cin >> N >> M;

    unsigned long long answer = UINT64_MAX;
    for(i=1; i <= min((long long)sqrtl(M)+1LL, N); i++){
        if((M+i-1)/i <= N)
            answer = min(answer, (unsigned long long)(M+i-1)/i*i);
    }

    cout << (long long)answer << "\n";
    return 0;
}

import math

N, M = map(int, input().split())
mini = float('inf')

for i in range(1, min(int(math.sqrt(M)) + 2, N + 1)):
    if (M + i - 1) // i <= N:
        mini = min(mini, i * ((M + i - 1) // i))

if mini != float('inf'):
    print(mini)
else:
    print(-1)

For each hunger value, we can say the number of chocolates Waldo will consume in $$$ O(N)$$$. And for any hunger values $$$ x>y$$$ the number of chocolates consumed $$$ f(x)≥ f(y)$$$ (Proof: exercise). Hence it is sufficient to binary search on possible hunger values.

Time Complexity: $$$ O(N\log{N})$$$

#include <bits/stdc++.h>
using namespace std; 

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    unsigned n, k, m, i;
    cin >> n >> k >> m;
    vector<int> arr(n);
    for(i=0; i<n; i++){
        cin >> arr[i];
    }
    unsigned low = 0, high = 1e9, mid;
    unsigned answer = UINT32_MAX, curr, count;
    while(low<=high){
        mid = (high+low)/2;
        curr = count = 0;
        for(i=0; i<n; i++){
            if(arr[i]<=mid)
                curr++;
            else
                curr=0;
            
            if(curr>=k){
                curr = 0;
                count++;
            }
        }

        if(count>=m){
            answer = min(mid, answer);
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    cout << (int)answer << "\n";

    return 0;
}

n, k, m = map(int, input().split())
arr = list(map(int, input().split()))
low = 0
high = 10**9
ans = 10**9 + 1

while low <= high:
    mid = (high + low) // 2
    ct = 0
    count = 0

    for i in range(n):
        if arr[i] <= mid:
            ct += 1
        if arr[i] > mid:
            ct = 0
        if ct >= k:
            ct = 0
            count += 1

    if count >= m:
        ans = min(mid, ans)
        high = mid - 1
    else:
        low = mid + 1

if ans == 10**9 + 1:
    ans = -1

print(ans)

The main idea of this task is as we traverse through the array we keep making the neighboring elements equal, either using subtracting from the prefix (Operation 1) or from the suffix (Operation 2). The number of steps in this process will simply be the sum of absolute difference of neighboring elements through out the array. Mathematically $$$\Sigma_{i=1}^{n}|arr[i]-arr[i-1]|$$$.

At the end of this process, all the array elements are equal to some value $$$x$$$. To further make all elements equal to 0, we require exactly $$$|x|$$$ operations. This can be done by either applying Operation 1 or Operation 3 $$$|x|$$$ times based on the sign of $$$x$$$.

Time Complexity: $$$ O(N)$$$

//OverRancid#0590
#include <bits/stdc++.h>    //Parental Advisory
using namespace std;       //Explicit Content

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned _, i;
    cin >> _;
    while(_--){
        unsigned n;
        cin >> n;
        vector<int> arr(n);
        for(i=0; i<n; i++){
            cin >> arr[i];
        }
        long long answer = 0LL, count = 0LL;
        for(i=1; i<n; i++){
            int diff = arr[i]-arr[i-1];
            answer += abs(diff);
            if(diff < 0){
                count += diff; 
            }
        }
        answer += abs(count+arr[0]);
        cout << answer << "\n";
    }
    return 0;
}

def main():
    for _ in range(int(input())):
        n = int(input())
        arr =  list(map(int, input().split()))
        answer = 0
        count = 0
        for i in range(n-1):
            diff = arr[i+1]-arr[i]
            answer += abs(diff)
            if diff<0:
                count += diff
        answer += abs(count+arr[0])
        
        print(answer)

if __name__ == '__main__':
    main()