codeforces

• A. Channel

  Petya is an administrator of a channel in one of the messengers. A total of n people are subscribed to his channel, and Petya is not considered a subscriber.

  Petya has published a new post on the channel. At the moment of the publication, there were a(number of subscribers) subscribers online. We assume that every subscriber always reads all posts in the channel if they are online.

  After this, Petya started monitoring the number of subscribers online. He consecutively receives q notifications of the form "a subscriber went offline" or "a subscriber went online". Petya does not know which exact subscriber goes online or offline. It is guaranteed that such a sequence of notifications could have indeed been received.

  Petya wonders if all of his subscribers have read the new post. Help him by determining one of the following:

  it is impossible that all n subscribers have read the post;

  it is possible that all n subscribers have read the post;

  it is guaranteed that all n subscribers have read the post.

So in this problem we need to see 3 cases:

1. if a + noPlus < n then answer is NO.

2. if anytime doing Plus and minus we have a >= n answer is YES.

3. otherwise MAYBE.

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

bool notPossible(int n,int a,int q,vector<char> isOnline)
{
    int plus=0,minus=0;
    for(int i=0;i<q;i++)
    {
        plus+=(isOnline[i]=='+')?1:0;
        minus+=(isOnline[i]=='-')?1:0;
    }
    if(a+plus<n)
        return true;
    return false;
}

string solve(int n,int a,int q,vector<char> isOnline)
{
    if(n==a)
    {
        return "YES";
    }
    if(notPossible(n,a,q,isOnline))
    {
        return "NO";
    }
    for(int i=0;i<q;i++)
    {
        if(n==a)
        {
            return "YES";
        }
        else if(isOnline[i]== '+')
        {
            a++;
        }
        else if(isOnline[i]=='-')
        {
            a--;
        }
    }
    if(n==a)
    {
        return "YES";
    }
    return "MAYBE";
}

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        int n,a,q;
        cin>>n>>a>>q;
        vector<char> isOnline(q);
        for(int i=0;i<q;i++)
        {
            char x;
            cin>>x;
            isOnline[i]=x;
        }
        string res = solve(n,a,q,isOnline);
        cout<<res<<endl;
    }
}

• B. Split Sort
  You are given a permutation p1,p2,…,pn of integers 1 to n.

  You can change the current permutation by applying the following operation several (possibly, zero) times:

  • choose some x (2≤x≤n);

  • create a new permutation by:

    • first, writing down all elements of p that are less than x, without changing their order;

    • second, writing down all elements of p that are greater than or equal to x, without changing their order;

  • replace p with the newly created permutation.

For example, if the permutation used to be [6,4,3,5,2,1][6,4,3,5,2,1] and you choose x=4, then you will first write down [3,2,1][3,2,1], then append this with [6,4,5][6,4,5]. So the initial permutation will be replaced by [3,2,1,6,4,5][3,2,1,6,4,5].

Find the minimum number of operations you need to achieve pi=i for i=1,2,…,n. We can show that it is always possible to do so.

A permutation of length n is an array consisting of n distinct integers from 11 to n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (n=3 but there is 44 in the array).