Consider the cost of buying exactly 1 fruit from the first shop $$$a$$$. The minimum amount we can spend in the second shop is $$$c$$$. If $$$a < c$$$ is is profitable to buy 1 fruit from the first shop, else it is always beneficial to buy from the second shop (This can be shown by induction).

Similarly consider the cost of buying exactly $$$b$$$ fruits. This will cost $$$a\cdot b$$$ from the first shop and $$$c$$$ from the second. For this to be profitable for the second shop, we require $$$c < a\cdot b$$$. If this does not hold, we can show that it is never optimal to buy from the second shop (by induction).

This produces our required answer in $$$O(1)$$$ per test case.

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int a, b, c;
        cin >> a >> b >> c;
        int x = -1, y = -1;

        if (a < c)
            x = 1;
        if (c < a * b)
            y = b;

        cout << x << " " << y << "\n";
    }
    return 0;
}

Claim: If a beautiful substring exists, there exists a beautiful substring of size 2.

After determining this, all we need to is traverse all beautiful substrings of size 2 and maintain the lexicographically smallest one, which can be done in $$$O(N)$$$.

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        string answer = "zz\n";

        for (i=0; i+1<n; i++) {
            if (s[i] != s[i+1]) {
                if (s[i] < answer[0] || (s[i+1] < answer[1] && s[i] == answer[0])) {
                    answer[0] = s[i];
                    answer[1] = s[i+1];
                }
            }
        }

        yn(answer != "zz\n");
        if (answer != "zz\n") {
            cout << answer;
        }
    }
    return 0;
}

As the only two directions that conveyor belt moves is in down and right, a luggage placed anywhere on the belt will reach either the last row or column in a finite number of moves (this can be shown by induction). If there is an R in the last row of the belt, the luggage will fall out of the belt so all Rs in the last row must be changed to Ds. Similarly if there are Ds in the last column of the belt they must be changed into Rs.

As we just need to check the last row and column, this task can be solved in $$$O(N+M)$$$.

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int n, m;
        cin >> n >> m;
        vector<string> grid(n);

        for (i=0; i<n; i++) {
            cin >> grid[i];
        }

        int answer = 0;

        for (i=0; i<n; i++) {
            if (grid[i].back() == 'R')
                answer++;
        }
        for (i=0; i<m; i++) {
            if (grid.back()[i] == 'D')
                answer++;
        }

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

As we are only concerned with the number of discs picked and we need to pick them in an ascending order let's greedily pick them from starting from disc $$$1$$$ to as many as possible. Further, as each pole can contribute atmost $$$1$$$ disc, we pick the disc with the smallest number from the pole with the smallest height to maximize the number of discs we pick.

This can be achieved in $$$O(N\log N)$$$ by simply sorting the poles based on size and then greedily picking the discs while traversing the poles.

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (i=0; i<n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        int answer = 0;
        for (i=0; i<n; i++) {
            if (a[i] > answer)
                answer++;
        }
        cout << answer << "\n";
    }
    return 0;
}

Let $$$X_i$$$ be the total cost of painting the wall using the $$$i^{th}$$$ brush. To calculate each $$$X_i$$$, we can simply traverse the wall. Whenever we encounter a black division we paint that white and skip the next $$$(i-1)$$$ segments as they will also be painted by the $$$i^{th}$$$ brush in $$$1$$$ operation.

$$$X_i$$$ for each $$$1\le i\le m$$$ can be calculated in $$$O(N)$$$. The final answer is simply the minimum among all $$$X_i$$$, giving us the solution in $$$O(N\cdot M)$$$ time.

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i, j;
    cin >> _;
    while (_--) {
        int n, m, c;
        cin >> n >> m;
        string s;
        cin >> s;
        int answer = INT_MAX;
        for (i=0; i<m; i++) {
            cin >> c;
            int curr = 0;
            for (j=0; j<n; j++) {
                if (s[j] == 'B') {
                    curr++;
                    j += i;
                }
            }
            answer = min(answer, c*curr);
        }
        cout << answer << "\n";
    }
    return 0;
}

There are multiple solutions to this task.

Greedy: The simplest solution to this task involves simply sorting all the given strings in lexicographical order and then comparing each string with it's direct neighbors — this will always work because after sorting the strings with the least difference will be adjacent to each other. Formally, let $$$s_{1\dots n}$$$ be the array of the $$$n$$$ given names sorted in lexicographical order, then

This gives us the answer in $$$O(\sum_{i=1}^{n} |s_i| \log{N})$$$.

Trie Data Structure: In this method we can simply use a trie and store all strings along with the prefix count in it. Then for each string we just need to perform a binary search on the length of the string to find the Best Match.

This method also gives us the answer in $$$O(\sum_{i=1}^{n} |s_i| \log{N})$$$.

String Hashing: In this method, for each string $$$s_j$$$ we hash the substrings $$$s_j[1\dots i]\space \forall\space 1 \le i \le |s_j|$$$ and store the count of this in a map. After preprocessing the hash's count for each string we again traverse each string's hash and choose the maximum $$$l_j$$$ such that $$$count(hash(s_j[0...l_j])) \ge 2\space \forall\space 1 \le j \le n$$$. The final answer is simply the array $$$[l_1, l_2, \dots, l_n]$$$

This method produces the answer in $$$O(\sum_{i=1}^{n} |s_i|)$$$.

from __future__ import print_function
from math import *
from collections import defaultdict, deque
import os
import random
import sys
from io import BytesIO, IOBase
from types import GeneratorType

# region fastio
 
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = []
for i in range(n):
    a.append((list(input()),i))
a.sort()
ans = [0]*n 
for i in range(n-1):
    x = a[i][0]
    y = a[i+1][0]
    count = 0
    for j in range(min(len(x),len(y))):
        if x[j] == y[j]:
            count += 1
        else:
            break
    
    ans[a[i][1]] = max(count,ans[a[i][1]])
    ans[a[i+1][1]] = max(count,ans[a[i+1][1]])
print(*ans)

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

class Trie{
public:
    Trie(){
        root = new TrieNode;
    }
    void insert(string &str){
        //inserts string into Trie
        TrieNode *currentNode = root;
        for(char x: str){
            int c = (int)(x-'a');
            if(currentNode->next[c]==nullptr){
                currentNode->next[c] = new TrieNode;
            }
            currentNode->prefix_count++;
            currentNode = currentNode->next[c];
        }
        currentNode->prefix_count++;
        currentNode->count++;
    }
    int search(string &str){
        //returns number of strings equivalent to str in Trie.
        TrieNode *currentNode = root;
        for(char x: str){
            int c = (int)(x-'a');
            if(currentNode->next[c]==nullptr){
                return 0;
            }
            currentNode = currentNode->next[c];
        }
        return currentNode->count;
    }
    void remove(string &str){
        //removes string from Trie if it exists - does nothing otherwise.
        root = remove_worker(root, str, 0);
    }
    int search_prefix(string &str){
        //returns number of strings with given prefix.
        TrieNode* currentNode = root;
        for(char x: str){
            int c = (int)(x-'a');
            if(currentNode->next[c]==nullptr){
                return 0;
            }
            currentNode = currentNode->next[c];
        }
        return currentNode->prefix_count;
    }
private:
    class TrieNode{
    public:
        TrieNode(){
            fill(next.begin(), next.end(), nullptr);
            count = 0;
            prefix_count = 0;
        }
        bool empty(){
            return prefix_count == 0;
        }
        array<TrieNode *, 26> next;
        int count;
        int prefix_count;
    };
    TrieNode* remove_worker(TrieNode* node, string &str, int depth){
        node->prefix_count--;
        
        if(depth == str.size()){
            node->count--;
            if(node->empty() && node->count==0){
                delete node;
                node = nullptr;
            }
            return node;
        }
        int c = str[depth] - 'a';
        node->next[c] = remove_worker(node->next[c], str, depth+1);
        
        if(node->empty() && node->count==0){
            delete node;
            node = nullptr;
        }
        return node;
    }
    TrieNode *root;
};

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, i;
    cin >> n;
    vector<string> s(n);
    Trie t;

    for (i=0; i<n; i++) {
        cin >> s[i];
        if ('A'<=s[i].front() && s[i].front() <= 'Z') {
            s[i].front() = s[i].front() + 'a' - 'A';
        }
        t.insert(s[i]);
    }

    for (i=0; i<n; i++) {
        int ans = 0, l=0, r=s[i].size();
        while (l<=r) {
            int mid = (l+r)/2;
            string x = s[i].substr(0, mid);
            if (t.search_prefix(x) > 1) {
                ans = max(ans, mid);
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

d = {}
d2 = {}
a = []
MOD = 10**9+7
for _ in range(int(input())):
    s = input()
    k = 0
    c = 0
    p = 31
    p2 = 69
    k2 = 0
    ans = 0
    for i in s:
        k += ord(i)*p
        k2 += ord(i)*p2
        k%=MOD
        k2%=MOD
        if k not in d: d[k] = 0
        if k2 not in d2: d2[k2] = 0
        d[k]+=1
        d2[k2]+=1
        c+=1
        p = (p*31)%MOD
        p2 = (p2*69)%MOD
    a.append(s)
ans = 0
for s in a:
    k = 0
    c = 0
    p = 31
    p2 = 69
    k2 = 0
    ans = 0
    for i in s:
        k += ord(i)*p
        k2 += ord(i)*p2
        k%=MOD
        k2%=MOD
        if d[k]>=2 and d2[k2]>=2:
            ans += 1
        else:
            break
        c+=1
        p = (p*31)%MOD
        p2 = (p2*69)%MOD
    print(ans)

Let's define $$$[l, r]$$$ as the range of number of candies. We can initialize the range as $$$[0, \infty ]$$$ and at each step $$$i$$$ adjust the range such that it follows the condition for the first $$$i$$$ steps. Let $$$[l, r]$$$ be the range after the $$$(i-1)^{st}$$$ step. The 3 possible operations in the $$$i^{th}$$$ step can be handled as follows:

• on a b: Atleast $$$a$$$ candies and atmost $$$b$$$ candies can be added giving two ranges $$$[l+a, r+a]$$$ and $$$[l+b, r+b]$$$. The new range is the union of these two ,i.e., $$$[l+a, r+b]$$$.
• off a b: Atleast $$$a$$$ candies and atmost $$$b$$$ candies could have been removed giving two ranges $$$[l-a, r-a]$$$ and $$$[l-b, r-b]$$$. The new range is the union of these two, i.e., $$$[l-b, r-a]$$$.
• none a b: This directly gives us a range $$$[a, b]$$$. Our new range must accommodate both $$$[l, r]$$$ and $$$[a, b]$$$ hence it is the intersection of the two. Formally, new range is $$$[\max (l, a), \min (r, b)]$$$.

By this procedure we get the required range after the $$$N^{th}$$$ point. For obtaining the range before the $$$1^{st}$$$ operation we can traverse the points in the reverse direction and swap the functionalities of on and off.

This gives us the required answer in $$$O(N)$$$.

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

struct point {
    string op;
    int l, r;
};

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, i;
    cin >> n;
    vector<point> a;
    for (i=0; i<n; i++) {
        string s;
        int l, r;
        cin >> s >> l >> r;
        a.push_back({s, l, r});
    }

    pair<int, int> before = {0LL, INT_MAX}, after = {0LL, INT_MAX};
    for (i=0; i<n; i++) {
        if (a[i].op == "on") {
            after.first += a[i].l;
            after.second += a[i].r;
        }
        else if (a[i].op == "off") {
            after.first -= a[i].r;
            after.second -= a[i].l;
        }
        else if (a[i].op == "none") {
            after.first = max(after.first, a[i].l);
            after.second = min(after.second, a[i].r);
        }
    }

    for (i=n-1; i>=0; i--) {
        if (a[i].op == "on") {
            before.first -= a[i].r;
            before.second -= a[i].l;
        }
        else if (a[i].op == "off") {
            before.first += a[i].l;
            before.second += a[i].r;
        }
        else if (a[i].op == "none") {
            before.first = max(before.first, a[i].l);
            before.second = min(before.second, a[i].r);
        }
    }

    before.first = max(before.first, 0LL);
    before.second = max(before.second, 0LL);
    after.first = max(after.first, 0LL);
    after.second = max(after.second, 0LL);

    cout << before.first << " " << before.second << "\n";
    cout << after.first << " " << after.second << "\n";
    return 0;
}

Consider the case for just 2 numbers $$$a$$$ and $$$b$$$. Let $$$x_a$$$ and $$$x_b$$$ be the msb of $$$a$$$ and $$$b$$$.

Claim: $$$a\space AND\space b > a\space XOR\space b \space \iff \space x_a = x_b$$$ and $$$a\space AND\space b \neq a\space XOR\space b \space \forall \space a, b$$$

So to calculate the answer we just need to count the number of pair of numbers with different msb. This can be done in $$$O(N)$$$

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int n;
        cin >> n;
        unordered_map<int, int> b;
        for (i=0; i<n; i++) {
            int a;
            cin >> a;
            b[__builtin_clz(a)]++;
        }
        int answer = n * (n-1) / 2;
        for (pair<int, int> bx: b) {
            answer -= bx.second * (bx.second - 1) / 2;
        }

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

This task can be solved using dp. Let's define our dp state as:

$$$f(i, 0) =$$$ minimum cost of reaching the $$$i^{th}$$$ red station.

$$$f(i, 1) =$$$ minimum cost of reaching $$$i^{th}$$$ blue station.

It is easy to see the transition rules:

As we start from the first red station we can initialize $$$f(1, 0) = 1$$$ and populate the dp in a top-down fashion. The final answer is the minimum from $$$f(n+1, 0)$$$ and $$$f(n+1, 1)$$$

Alternate Solution: We can also model this situation as a directed graph with separate red and blue vertices. We then run a shortest path algorithm starting from the first red vertex and the answer will be the minimum distance among the $$$(n+1)^{st}$$$ red and blue vertex. For more information on such tasks go through the following blog

Both these solutions work in $$$O(N)$$$

//Created by Mehul G.
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        long long N, R, B;
        cin >> N >> R >> B;
        vector<long long> red(N + 1, 0);
        vector<long long> blue(N + 1, 0);
        for (int i = 1; i <= N; i++)
        {
            cin >> red[i];
        }
        for (int i = 1; i <= N; i++)
        {
            cin >> blue[i];
        }
        vector<vector<long long>> dp(N + 1, vector<long long>(2, LONG_LONG_MAX));
        dp[0][0] = 0;
        dp[0][1] = B;
        for (int i = 1; i <= N; i++)
        {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + R) + red[i];
            dp[i][1] = min(dp[i - 1][0] + B, dp[i - 1][1]) + blue[i];
        }
        cout << min(dp[N][0], dp[N][1]) << endl;
    }
    return 0;
}

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

static const int N = 2e5+3;
vector<vector<pair<int, int>>> adj(N);
vector<int> d;

void dijkstra(int s){
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    while(!q.empty()){
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();

        if(d_v != d[v]){
            continue;
        }

        for(pair<int, int> edge: adj[v]){
            int u = edge.first;
            int w = edge.second;

            if(d[v] + w < d[u]){
                d[u] = d[v] + w;
                q.push({d[u], u});
            }
        }
    }
}

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int n, r, b, a;
        cin >> n >> r >> b;

        for (i=1; i<=n+1; i++) {
            adj[i].clear();
            adj[i + n+1].clear();
        }
        for (i=1; i<=n; i++) {
            cin >> a;
            adj[i].push_back({i+1, a});
            adj[i].push_back({i+(n+1), b});
        }
        for (i=1; i<=n; i++) {
            cin >> a;
            adj[i + (n+1)].push_back({i+1 + (n+1), a});
            adj[i + (n+1)].push_back({i, r});
        }
        adj[n+1].push_back({2*(n+1), b});
        adj[2*(n+1)].push_back({n+1, r});

        d = vector<int>(2*n+5, 5e15);
        dijkstra(1);

        cout << min(d[n+1], d[2*n+2]) << "\n";
    }
    return 0;
}

This task can be solved using the sliding window like technique. In each window we maintain 3 things to ensure we don't exceed our limit on number of operations.

• multiset $$$useX$$$: consisting of all numbers on which we wish to apply operation of type 1.
• multiset $$$useY$$$: consisting of all numbers on which we wish to apply operation of type 2.
• integer $$$sumX$$$: the sum of all numbers on which we wish to apply operation of type 1.

A window (subarray) can be considered valid if:

• size of $$$useY \le Y$$$
• $$$sumX \le X$$$

For any window we can greedily keep applying as many operations of type 2 as possible. Once this is no longer possible we apply operation of type 1 on the smallest numbers in the window.

This can be implemented in $$$O(N\log N)$$$ using std::multiset or std::priority_queue or even ordered set from __gnu_pbds.

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

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

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

    int n, x, y, i, j;
    cin >> n >> x >> y;
    vector<int> a(n);
    for (i=0; i<n; i++) {
        cin >> a[i];
    }

    multiset<int> useX, useY;
    int answer = 0, sumX = 0;
    for (i=0, j=0; i<n; i++) {
        useY.insert(a[i]);

        while (useY.size() > y) {
            int small = *useY.begin();
            sumX += small;
            useX.insert(small);
            useY.erase(useY.begin());
        }

        while (sumX > x) {
            int last = a[j];
            if (useX.count(a[j])) {
                sumX -= a[j];
                useX.erase(useX.find(a[j])); 
            }
            else {
                useY.erase(useY.find(a[j]));
                int big = *useX.rbegin();
                sumX -= big;
                useX.erase(useX.find(big));
                useY.insert(big);
            }
            j++;
        }

        answer = max(answer, (useX.size() + useY.size()) * 1LL);
    }
    cout << answer << "\n";

    return 0;
}

// Created by Mehul G.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<pair<int, int>, null_type, greater<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long N, X, Y, x_used, ans;
    cin >> N >> X >> Y;
    ordered_set o_set;
    vector<long long> store(N);
    for (int i = 0; i < N; i++)
    {
        cin >> store[i];
    }
    x_used = ans = 0;
    long long i = 0;
    for (int j = 0; j < N; j++)
    {
        if (o_set.size() >= Y)
        {
            o_set.insert({store[j], j});
            int ind = o_set.order_of_key({store[j], j});
            if(ind >= Y){
                x_used += store[j];
            }
            else{
                auto itr = *o_set.find_by_order(Y);
                x_used += itr.first;
            }
            while (x_used > X)
            {
                ind = o_set.order_of_key({store[i], i});
                if (ind >= Y)
                {
                    x_used -= store[i];
                }
                else
                {
                    auto itr = *o_set.find_by_order(Y);
                    x_used -= itr.first;
                }
                o_set.erase({store[i], i});
                i++;
            }
            ans = max(ans, j - i + 1);
        }
        else
        {
            o_set.insert({store[j], j});
            ans = max(ans, j - i + 1);
        }
    }
    cout << ans << endl;
    return 0;
}

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