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;
}