The even prime number refers to $$$2$$$. The task is it simply check if the input number is divisible by $$$2$$$ and print the output as described.

Time Complexity: $$$O(1)$$$

print(*[['BLUE','RED'][int(input())&1] for _ in range(int(input()))],sep='\n')

We can trivially pick all good cookies. So let's focus on how we will handle the bad cookies.

Let $$$[l, r]$$$ be a continuous segment of bad cookies, i.e., $$$A_i = 0 \space \forall \space l \leq i \leq r$$$. We are only allowed to pick 1 cookie from this segment and we choose the one with maximum taste level.

Now let $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$, $$$l_1 < r_1 < l_2 < r_2$$$ be two non intersecting bad segments such that $$$\exists \space i | \space r_1 < i < l_2 and A_i = 0$$$. Then we can pick one cookie from each of the bad segments as we have picked a good cookie $$$A_i$$$ in between.

Hence we just need to maintain all segments of bad cookies and choose the best one from each of them.

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

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned _, i;
    cin >> _;
    while(_--){
        unsigned n;
        cin >> n;
        long long answer = 0, curr=0;
        long long type, value;
        for(i=0; i<n; i++){
            cin >> type >> value;
            if(type==0){
                answer += value;
                answer += curr;
                curr = 0;
            }
            else{
                curr = max(curr, value);
            }
        }
        cout << answer + curr << "\n";
    }
    return 0;
}

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    mx = ans = 0
    for _ in range(n):
        ok, taste = map(int, input().split())
        ok = not ok
        if ok:
            ans += taste
            ans += mx
            mx = 0
        else:
            mx = max(mx, taste)
    ans += mx
    print(ans)

In the easy version, as Santa always starts reading from the first index, we just need to traverse the string and keep track of the number of $$$'N'$$$ and $$$'G'$$$ we encounter. As it is optimal to remove the first $$$k$$$ $$$\space 'N'$$$ s, we stop the traversal when either the string ends or the count of $$$'N'$$$ exceeds $$$k$$$.

Our required answer is the count of $$$'G'$$$ at the point when we stop the traversal.

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

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

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while(_--){
        unsigned n, k;
        cin >> n >> k;
        string str;
        cin >> str;
        int G_count = 0, N_count = 0;
        for(i=0; i<n && N_count <=k; i++){
            str[i]=='G'? G_count++: N_count++;
        }
        cout << G_count << "\n";
    }
    return 0;
}

import sys
input = lambda:sys.stdin.readline().rstrip()
for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    cnt = ans = i = 0
    while cnt <= k and i < n:
        if s[i] == 'N':
            cnt += 1
        else:
            ans += 1
        i += 1
    print(ans)

For the trivial case where number of $$$'N'$$$ s in the string is less than or equal to $$$k$$$, all $$$'N'$$$ s can be removed and the answer is simply the count of $$$'G'$$$ in the string. We will focus on the solution for the non trivial case.

This version of the task can be solved using ideas from prefix sum.

We maintain an array $$$arr[n]$$$, where $$$arr[i]$$$ represents the maximum number of letters Santa will read if he starts reading from the first index and $$$i$$$ letters are removed. This array can be constructed in linear time by traversing the string just once.

Notice that in the final array, $$$arr[i] - arr[i-k-1]$$$ represents a continuous segment with exactly $$$k \space 'N'$$$ s. As it is always optimal to remove the maximum possible number of $$$'N'$$$ s, the required answer is the maximum between $$$arr[k]$$$ and $$$arr[i] - arr[i-k-1]$$$ over all $$$i$$$.

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

As an additional challenge, try to solve the task with the following conditions:

• Santa stops only if he has read all the letters in the list atleast once or he comes across a letter from a naughty child.

• After reading the last letter in the list, if not already read, Santa starts reading from the first letter.

//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, k;
        cin >> n >> k;
        string str;
        cin >> str;

        vector<int> res;
        int G_count = 0;
        for(i=0; i<n; i++){
            if(str[i]=='G'){
                G_count++;
            }
            else{
                res.push_back(G_count);
            }
        }
        res.push_back(G_count);

        if(res.size() <= k+1){
            cout << res.back() << "\n";
            continue;
        }
        
        int answer;
        answer = res[k];
        for(i=k+1; i<res.size(); i++){
            answer = max(answer, res[i]-res[i-k-1]);
        }
        cout << answer << "\n";
    }
    return 0;
}

import sys
input = lambda:sys.stdin.readline().rstrip()
for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    ind = [i for i in range(n) if s[i] == 'N']
    if len(ind) <= k:
        print(s.count('G'))
        continue
    ind = [-1] + ind + [n]
    ans = 0
    for i in range(len(ind)-k-1):
        ans = max(ans, ind[i+k+1]-ind[i]-1)
    print(ans - k)

The hard part of the solution is to understand which digit any number corresponds to, so let's tackle that first. This task is further divided into 3 parts.

Let's say any input number $$$A$$$ corresponds to digit $$$d_i$$$ and that digit is obtained from the integer $$$D = d_n...d_2d_1$$$. Let $$$A' = A - 9 ⋅ \sum_{i=0}^{n-1} (i+1) ⋅ 10^i$$$

In the first step, we determine the number digits in $$$D$$$. Notice that there are 9 1 digit numbers, 90 2 digit numbers and so on. We can use this recursive relation to find the number of digits in $$$D$$$.

In the second step, we determine the exact number $$$D$$$ from which we will extract our digit. This is equal to $$$10^n + \lfloor \frac{A'-1}{n} \rfloor$$$.

In step three, we determine the exact digit. This information is given by $$$(A'-1)$$$ % $$$n$$$. Say $$$(A'-1)$$$ % $$$n = i$$$ then the required digit is the $$$i^{th}$$$ digit from the front.

Analysis: In these 3 steps, step 2 and 3 are $$$O(1)$$$, as they are just direct formula. In the first step the loop runs up to the number of digits in $$$A$$$ — making it an $$$O(\log_{10}A)$$$ process. Hence the total complexity of this procedure is $$$O(\log_{10}A)$$$.

In the main task, this has to be performed $$$N$$$ times, and the frequency of each digit has to be maintained, which can be done using an array.

Time Complexity: $$$O(N \log_{10}A), \space A = \max_{1 \leq i \leq n}(A_i)$$$

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

#define int long long
#define unsigned unsigned long long

int getDigit(int A){
    int base = 9;
    long digits = 1;
    while (A - base * digits > 0) {
        A -= base * digits;
        base *= 10;
        digits++;
    }
        
    int index = (A - 1) % digits;
    int offset = (A - 1) / digits;
    int start = pow(10, digits - 1);
    return to_string(start + offset)[index] - '0';
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned _, i;
    cin >> _;
    while(_--){
        unsigned n, x;
        cin >> n;
        vector<int> freq(10, 0);
        for(i=0; i<n; i++){
            cin >> x;
            freq[getDigit(x)]++;
        }

        cout << *max_element(freq.begin(), freq.end()) << "\n";
    }
    return 0;
}

The largest digit we can have is $$$9$$$, and there are up to $$$10$$$ unique digits. So the largest possible beautiful number has $$$90$$$ digits. We can traverse the string and check all substrings of size $$$\leq 90$$$ and check how many of them are beautiful.

The total number of substrings in a string of size $$$N$$$ is $$$\frac{N⋅(N+1)}{2}$$$.

Dividing these two values, we obtain the probability of Santa choosing a beautiful number.

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

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

const long long MOD = 1000000007;

long long powerr(long long x, long long y, long long M) { 
    if (y == 0) 
        return 1; 
  
    long long p = powerr(x, y / 2, M) % M; 
    p = (p * p) % M; 
  
    return (y % 2 == 0) ? p : (x * p) % M; 
}

long long modinv(long long a, long long M){
    return powerr(a,M-2,M);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long _;
    cin >> _;
    while(_--){
        string s;
        cin >> s;
        long long n = s.size();
        long long ct=0;

        for(long long i = 0; i < n; i++){

            vector<long long>count(10,0);
            long long maxi=0;
            long long keep=0;

            for(long long j = i; j < min(i+100,n); j++){

                maxi=max(maxi,(ll)(s[j]-'0'));
                count[s[j]-'0']++;
                keep=max(keep,count[s[j]-'0']);
                if(maxi>keep)
                    ct++;
	        
            }
        }
        long long d = modinv((n*(n+1)/2),MOD);

	long long ans = (ct*d)%MOD;
	cout << ans << endl;
    }
    return 0;
}

Notice that in any name or combination of names, we don't care about the frequency of characters. We are only interested in knowing the number of unique characters used. We can use this to our advantage and represent any name as a 10 bit binary number, in which the $$$i^{th}$$$ bit corresponds to the $$$i^{th}$$$ latin alphabet.

After that, we can start use all numbers which have exactly $$$k$$$ bits on and traverse them through the names, keeping track of number of names that can be formed and the stamps used. If at the end of the traversal $$$k$$$ stamps have been used, we update the answer if the count is greater.

Analysis:

• As each name has a maximum size of $$$15$$$, it takes $$$O(15)$$$ time to map any name to it's integer.
• The number of 10 bit numbers with exactly $$$k$$$ bits on is $$$\binom{10}{k} \leq 252$$$

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

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

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int64_t _, i, j;
    cin >> _;
    while(_--){
        int n, k;
        cin >> n >> k;
        string str;
        vector<int> names(n, 0);
        for(i=0; i<n; i++){
            cin >> str;
            for(char c: str){
                names[i] |= 1<<(c-'a');
            }
        }

        int answer = 0;
        for(i=0; i<(1<<10); i++){
            if(__builtin_popcountll(i)!=k){
                continue;
            }

            int count = 0;
            int temp = 0;
            for(j=0; j<n; j++){
                if((i&names[j])==names[j]){
                    temp |= names[j];
                    count++;
                }
            }
            if(temp==i){
                answer = max(answer, count);
            }
        }
        cout << answer << "\n";
    }
    return 0;
}

from sys import stdin
input = lambda:stdin.readline().rstrip()
from itertools import combinations
from collections import Counter
def mask(s):
    ret = 0
    for c in s:
        ret |= 1 << (ord(c) - ord('a'))
    return ret
for _ in range(int(input())):
    line = input()
    if not line: line = input()
    n, k = map(int, line.split())
    freq = [mask(input()) for _ in range(n)]
    ans = 0
    for choice in combinations('abcdefghij', k):
        cnt = 0
        ch = mask(choice)
        taken = 0
        for s in freq:
            if s & ch == s:
                cnt += 1
                taken |= s
        if taken == ch: ans = max(ans, cnt)
    print(ans)

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()