-> If we can't collect the coins when k = 0, answer is Impossible

-> If any of the A[i] >= C, answer is Infinity

-> Other than that, we can binary search on the possible k

Am I somewhat close to the solution, or my approach is completely far off?

This one is the easiest, but I think that always that you read that you must give a number that is not the minimum or maximum of a list, you must think in make a vector, sort and print the position that you are interested. Like for example the second minimum would be a[1] or the second maximum a[n-2].

#include <bits/stdc++.h>

using namespace std;
/*

  


*/
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);  
}

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

void solve(){  
    vector<int> a(3);
    for(auto &x : a){cin >> x;}
    sort(a.begin(),a.end());
    cout << a[1] << '\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //cout.precision(10);
    int t = 0;
    cin >> t;
    for(int p = 0; p < t;p++){
        solve();
    }
}

The important thought that you must find is that if the maximum letter is 'a' you only need one and 'z' you need 26 and with only make in your mind the solution of two case you began to see what you need to do, I was a little nervous when I was writing the code and was thinking what is better if sort the string and see the last letter or used the function max_element, when you have dudes but you know that the code that you are in the middle of writing will work too, is best to commit to what you are writing in the moment that change to another solution in my experience. This work good in first or second problem for me because the solutions that you think probably will be right because they try to make easy for beginners like me, this is my way to be faster.

Another useful type for the problems that want you to make a letter a number is remember that 'a'-'a' is 0 or a character minus the same character will return 0.

#include <bits/stdc++.h>

using namespace std;
/*

  


*/
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);  
}

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

void solve(){  
    int n;
    cin >> n;
    string s;
    cin >> s;
    sort(s.begin(),s.end());
    cout << s[n-1] - 'a' + 1 << '\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //cout.precision(10);
    int t = 0;
    cin >> t;
    for(int p = 0; p < t;p++){
        solve();
    }
}

Here strike again the idea that we see in the problem A, in this problem you only care about the maximum and the second maximum so you make a vector, sort and use a[n-1] when the value x is not the maximum and a[n-2] if x is equal to the maximum, but I used a different method of only stored the two maximum numbers in a vector because I think a better version before beginning to write.

#include <bits/stdc++.h>

using namespace std;
/*

  


*/
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);  
}

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

void solve(){  
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(2);
    for(auto &x : a){cin >> x; 
        if(b[1] < x){
            b[0] = b[1];
            b[1] = x;
        }
        else if(b[1] == x){
            b[0] = b[1];
        }
        else if(b[0] < x){
            b[0] = x;
        }
        
    }
    for(auto x : a){
        if(x != b[1]){
            cout << x - b[1] << " ";
        }
        else{
            cout << x - b[0] << " ";
        }
    }
    cout << '\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //cout.precision(10);
    int t = 0;
    cin >> t;
    for(int p = 0; p < t;p++){
        solve();
    }
}

Is curious because I have come across this kind of problems many times that they want you to search there is a "Valley" or a "Peak" in the vector I still don't have a good way of approach this kind, but they always give you the conditions that must meet so the idea is always searching in a for if the condition is meet and see what are the corners case.

In this case you want to focus in every point because you can make L=R, the segments with same numbers but for example if you have a segment equal to {3,3,3,3} you don't want to waste your time with {3},{3,3},{3,3,3} because they will contradict the condition a[l−1]>a[l] or a[r] < a[r+1] other that this is good to keep in mind that l=0 or r = n-1 are free passes.

#include <bits/stdc++.h>

using namespace std;
/*

  


*/
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);  
}

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

void solve(){  
    int n;
    cin >> n;
    int i = 1;
    int l = 0;
    vector<int> a(n);
    cin >> a[0];
    int h = a[0];
    int ans = 0;
    int cnt = 1;
    for(i;i < n;i++){
        int x;
        cin >> a[i];
        x = a[i];
        if(x != h){
            // cout << l << " " << i <<  " ";
            if(l == 0){
                if(a[i-1] < a[i]){ans++;}
            }
            else if(a[l-1] > a[l]){
                if(a[i-1] < a[i]){ans++;}

            }
            // cout << ans << '\n';
            l = i;
            h = x;
        }
    }
    // cout << ans << " ";
    if(n == 1){
        cout << "YES\n";
        return;
    }

    if(a[n-1] == a[n-2]){
        if(l == 0){ans++;}
        else if(a[l-1] > a[l]){ans++;}
    }
    else{
        if(a[n-2] >  a[n-1]){ans++;}
    }
    // cout << ans << " ";
    ans == 1 ? cout << "YES\n" : cout << "NO\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //cout.precision(10);
    int t = 0;
    cin >> t;
    for(int p = 0; p < t;p++){
        solve();
    }
}

this one is just in my reach of knowledge so when I find problems that seem difficult at the beginning, I always try to see what type of input I can solve and corner case to corner case I will build my solution.

• The first one is what happen if n == 1? in this case no matter why I do the answer will be 0
• what happen if there are only ones? then the best is to make the last number a 0 and the answer will be n-1
• if there are only zeros? make the first number a 1 and the answer will be n-1

Now it's apparent that the best is to make the last one a zero or the first one converted to one and see how much we gain or lost for each operation and after seeing if it is good to make a change, go for all the vector and every see how much it will give to the answer. Another tip is to use comments when you feel that you are confused about what you have done and what not.

If you see my code is very inefficient but show that divide the problem in easy problems help you to see a solution.

#include <bits/stdc++.h>

using namespace std;
/*

  


*/
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);  
}

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

void solve(){  
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> pos;
    long long tots = 0;
    int i = 1;
    int fz = -1;
    int posz = 0;

    for(auto &x : a){
        cin >> x;
        if(x == 1){pos.push_back(i);}
        if(x == 0 && fz == -1){fz = i;posz =  i-1;}
        i++;
    }
    int n1 = pos.size();
    int cntz = n-n1;
    if(n == 1){cout << "0\n";return;}
    if(n1 == 0 || fz == -1 || cntz == 0){
        cout << n-1 << '\n';return;
    }
    int val1 = cntz-1-posz;// first z to 1
    int val2 = (n1-1)-(n-pos.back());//last 1 to z
    // cout << val1 << " " << val2 << '\n';
    if(val1 > val2){
        a[posz] = 1;
        cntz--;
    }
    else if(val2 > 0){
        a[pos.back()-1] = 0;
        cntz++;
    }
    for(int i = 0;i < n;i++){
        if(a[i] == 0){cntz--;}
        else{
            tots += cntz;
        }
    }
    cout << tots << '\n'; 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //cout.precision(10);
    int t = 0;
    cin >> t;
    for(int p = 0; p < t;p++){
        solve();
    }
}

There are many ways to do this. I simply output $$$a + b + c - \max(a, b, c) - \min(a, b, c)$$$.

The answer is the letter with the largest position in the alphabet.

If we are the strongest person, the strongest opponent is the second strongest person. If we are not the strongest person, the strongest opponent is the strongest person. Store the strongest and second strongest opponent in two variables to compute the answer in linear time.

Play around with examples to find that the array must consist of a non-increasing segment followed by a non-decreasing segment. Anything else will create at least two valleys. So make sure there are no occurrences of $$$a_i<a_{i+1}$$$ before $$$a_i>a_{i+1}$$$.

For each zero, the number of inversions containing that zero is the number of ones before the zero. So keep a running total of the number of ones to quickly compute the number of inversions of $$$a$$$ initially. Consider flipping each element. If we flip a zero, the number of inversions will increase by the number of zeroes after, and decrease by the number of ones before. If we flip a one, the number of inversions will decrease by the number of zeroes after, and increase by the number of ones before. Take the maximum possible increase, which is at least 0 if we do nothing, then add this to the number of inversions initially.

The maximum number of coins we can get decreases or stays the same whenever $$$k$$$ increases. So binary search for $$$k$$$. The maximum number of coins can be made by choosing the $$$k+1$$$ greatest elements in decreasing order in cycles until $$$d$$$ days have passed.

For example if $$$a = [1, 2, 3, 10, 5, 4, 3]$$$, $$$k = 5$$$, and $$$d = 16$$$, we choose $$$10, 5, 4, 3, 3, 2| 10, 5, 4, 3, 3, 2| 10, 5, 4, 3$$$. I put a bar where our selections start repeating.

We can quickly compute the most coins we make by sorting $$$a$$$ in decreasing order then making a prefix sum array. Take the $$$k+1$$$th element in our prefix sum array, multiply it by the number of times we can fully cycle through our $$$k+1$$$ elements, then add the sum of our remaining incomplete cycle.

If we revisit a vertex, the walk starting and ending from the revisited vertex must've crossed each edge an even number of times, because each edge in a tree is a cut-edge. So there's no point of revisiting a vertex, and a potential solution will consist of walking from $$$a$$$ to $$$c$$$ (without crossing $$$b$$$), teleporting to $$$d$$$, then walking from $$$d$$$ to $$$b$$$. The case where we don't teleport can be treated as teleporting from $$$c$$$ to $$$c$$$.

The xor of the edges of the paths from $$$a$$$ to $$$c$$$ combined with the edges of the path from $$$d$$$ to $$$b$$$ must be $$$0$$$. So the xor of the path from $$$a$$$ to $$$c$$$ is equal to the xor of the path from $$$d$$$ to $$$b$$$. Using depth-first search, compute the xor going from $$$a$$$ to each vertex, and the xor going from $$$b$$$ to each vertex, and see if any two xor values match. Remember that $$$a=c$$$ is forbidden and when you start your depth-first search from $$$a$$$, don't go into $$$b$$$.