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)