PB Hustle solution links

[yashwantsingh]

PB Hutle 2.23
August 28, 2020

Problem A
Problem B
Problem C
Problem D
Problem E
Problem F

These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page

[Deeepanshu_kumar_pal]

PB Hustle 2.24
Sep/04/2020

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F

• These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page *

[Deeepanshu_kumar_pal]

PB Hustle 2.25
Sep/11/2020

Problem A

Problem B

Problem C

Problem D

Problem E

• These are the links to original problems, solutions, and editorials can be found in the tutorial section on the problem page *

[Ravishek_Ranjan]

PB Hustle 2.26
Sep/18/2020

Problem A

Problem B

Problem C

Problem D

Problem E

• These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page *

[aman]

PB Hustle 3.01
Oct/02/2020

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F (removed from the contest)

• These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page *

[aman]

PB Hustle 3.2
Oct/09/2020

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F

• These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page *

[Deeepanshu_kumar_pal]

PB Hustle 3.3
Oct/16/2020

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F

• These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page *

[Deeepanshu_kumar_pal]

PB Hustle 3.4

Oct/23/2020

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F

• These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page *

[repe_frost]

PB Hustle 4.01
May/14/2021
Problem A
Problem B
Problem C
Problem D
Problem E

• These are the links to original problems, solutions and editorials can be found in the tutorial section on the problem page *

[repe_frost]

PB Hustle 4.02
May 21/2021
Problem A
ProblemB
ProblemC
ProblemD
ProblemE

[repe_frost]

PB Hustle 4.03
May 28/2021
Problem A
Problem B
Problem C
Problem D
Problem E

[repe_frost]

PB Hustle 4.04
June 4/2021
Problem A
The easiest trick is to take the input as a string and print the length as output
Problem Setter’s Solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    string a;
    cin>>a;

    cout<<a.size();
    return 0;
}

Problem B
You can xor all the characters if thy have a even frequency then the xor will be 0 else no

Problem Setter’s Solution:

#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main()
{
       string a;
    cin>>a;
    int x=0;
    for(char c:a)
        x^=c;
    if(x)
        cout<<"No";
    else 
        cout<<"Yes";
    return 0;
}

Problem C
There’s a efficient way to check what operation to use here we can just check the middle character if it is a ‘+’ then increment your counter or else decrement it

Problem Setter’s Solution:

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int n;
    cin>>n;
    int ans=0;
    while(n--)
    {
        string a;
        cin>>a;
        if(a[1]=='+')ans++;
        else if(a[1]=='-')ans--;
    }
    cout<<ans;
    return 0;
}

Problem D
This Problem reduces to Solve a Linear Diophantine Equations of the form 11x+111y there are many efficient ways to solve this using modular inverse and all but there is a nice trick
Problem Setter’s Solution :

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        if(n%11==0)
        {
            cout<<"YES\n";
        }
        else if(n%111==0)
        {
            cout<<"YES\n";
        }
        else if(n%122==0)
        {
            cout<<"YES\n";
        }
        else 
        {
            int y=1;
            while(n>=0)
            {
                
                if(n%11==0)
                {
                    cout<<"YES\n";
                    y=0;
                    break;
                }
                else if(n%111==0)
                {
                    cout<<"YES\n";
                    y=0;
                    break;
                }
                n-=122;
            }
            if(y)
                cout<<"NO\n";
        }
    }
    return 0;
}

Problem E
In this Problem we can see a pattern that if the n is even there is no solution and if the n is odd we can just use a normal permutation of 0 to n-1 and then repeat the same for b andc is just a+b

Eg:
5
0 1 2 3 4
0 1 2 3 4
0 2 4 1 3

Problem Setter’s Solution:

 #include<bits/stdc++.h>
using namespace std;
const int m=12345;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    if(n%2==0)
        cout<<-1;
    else{
    for(int i=0;i<n;i++)
    {
        cout<<i<<" ";
    }
    cout<<'\n';
    for(int i=0;i<n;i++)
    {
        cout<<i<<" ";
    }
    cout<<'\n';
    for(int i=0;i<n;i++)
    {
        cout<<(2*i)%n<<" ";
    }
    cout<<'\n';
    }
}

Problem F
Just Making the Number Square Free keep dividing the number by x if its divisible by x*x
(Note that a number can be of the form x*x*x*x*f here we need to check x 2 times basically a if statement wont work we need to use a while)
Problem Setter’s Solution :

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    long long int n;
    cin>>n;
    for(long long int i=1e6;i>=2;i--)
    {
        long long int y=i*i;
        while((n%y)==0)
        {
            n/=i;
        }
    }
    cout<<n;
    return 0;
}

[repe_frost]

PB Hustle 4.05
June 18/2021
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F

[repe_frost]

PB Hustle 5.01

Problem A

Solution : Turns out to be just the max - min element in the array because the difference remains constant no matter what constant number we add to the whole array

Setter’s Solution :

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int a[n];
        for(auto &i:a)
        {
            cin>>i;
        }
        cout<<*max_element(a,a+n)-*min_element(a,a+n)<<'\n';
    }
    return 0;
}

Problem B

Solution : A pretty Standard DP Problem well known as Coin Change Problem

Deepanshu’s Solution :

#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
#define nl cout<<endl
#define ns cout<<" "
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL)
#define forAuto(i,x) for(auto i: x)
#define forRange(i,l,h) for(ll i=l;i<h;i++)
#define all(x) x.begin(),x.end()
#define append push_back

 
void vsInput()
{
 #ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
 #endif // ONLINE_JUDGE
}

template<class T>
T GCD(T a,T b)
{
 if (b == 0) return a;
 return GCD(b, a % b);
}
ll bigmod(ll a,ll b, ll c)
{
 if(b==0) return 1;
 if(b%2) return (a%c * bigmod(a,b-1,c))%c;
 else
 {
     ll x = bigmod(a,b/2,c);
     return (x*x)%c;
 }
}

void print() {}
template <class T1, class... T2>
constexpr void print(const T1& var1, const T2& ... var2) { cout<<var1;ns; print(var2...); }
 
//const ll CPN = 600005;
//const ll M = 1e9 + 7;
//----------------------------CODE----------------------------/

void code()
{
    ll n,s; cin >> s >> n;
    ll a[n]; forRange(i,0,n) cin >> a[i];
    
    ll dp[n + 1][s + 1];
    memset(dp,0,sizeof(dp));
    
    forRange(i,0,n + 1) dp[i][0] = 1;
    
    forRange(i,1,n+1)
    forRange(j,1,s+1)
      {
          if(a[i - 1] > j) dp[i][j] = dp[i - 1][j];
          else dp[i][j] = dp[i - 1][j] + dp[i][j - a[i - 1]];
          
      }
    print(dp[n][s]);nl;   
}

Problem C

Solution : A Standard RSQ(range sum query) problem, can be solved using prefix sum / Fenwick tree or segment tree .
Since the problem in static RSQ we can just use prefix sums.

Setter’s Solution :

#include<bits/stdc++.h>

using namespace std;


#define int long long

int a[10000000];

signed main()
{
    int n,q;
    cin>>n>>q;
    while(q--)
    {
        int l,r,d;
        cin>>l>>r>>d;
        l--,r--;
        a[l]+=d;
        a[r+1]-=d;
    }
    for(int i=1;i<=n;i++)
    a[i]=a[i-1]+a[i];
    cout<<*max_element(a,a+n+1);
}

Problem D

Solution : A Standard balancing parenthesis problem can be solved using stack or counting

Setter’s Solution :

#include<bits/stdc++.h>

using namespace std;

#define int long long


signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string a;
        cin>>a;
        stack<char>s;
        for(char c:a)
        {
            if(s.empty())
                s.push(c);
            else if(s.top()=='(' && c==')')
                s.pop();
            else if(s.top()=='[' && c==']')
                s.pop();
            else if(s.top()=='{' && c=='}')
                s.pop();
            else
                s.push(c);
        }
        if(s.empty())
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
}

Problem E

Solution : Its Turns out that the total number of 0’s in the binary representation of n and all its combinations is the answer basically giving us 2^(number of 0’s in binary representaion);

Setter’s Solution :

#include<iostream>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    if(!n)
    {
        cout<<1;
        return 0;
    }
    int ans=64-__builtin_clzll(n)-__builtin_popcountll(n);
    cout<<(1LL<<ans);
}

Problem F

This problem was supposed to be a binary tree problem but then Vjudge dint support Function type problems so

Solution : This is a standard Sieve problem using sieve of eratosthenes method would work here

Setter’s Solution ;

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
  
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int n,m;
    cin>>n>>m;

    int a[n];
    set<int>fact;
    auto f=[&] (int x){
        for(int i=2;i*i<=x;i++)
            while(x%i==0){
                x/=i;
                fact.insert(i);
            }
             if(x!=1){fact.insert(x);}
    };
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]!=1)
        f(a[i]);
    }
    vector<bool>ans(m+1,0);
    for(int x:fact)
    {
        for(int j=x;j<=m;j+=x)
            ans[j]=1;
    }   
    int u=0;
    for(int i=1;i<=m;i++)
    {
        if(!ans[i])
            u++;
    }
    cout<<u<<'\n';
    for(int i=1;i<=m;i++)
    {
        if(!ans[i])
            cout<<i<<'\n';
    }
    return 0;
}

[repe_frost]

PB Hustle 5.02
Setter : Arjun S
Tester : Calan Pereira

Problem A
Analysis :
This was a Very easy observation based problem , we observe that when the number is divisible by 10 we don’t need to do any operations hence 0 is our answer, were as the only other case that can lead us to getting a number divisible by 10 by multiplying 2 is when the number is divisible by 5 and the number of operations is 1 hence the answer ,lastly rest of all cases we can never make the number divisible by 10 by multiplying 2 to it Hence giving us the answer -1 as per our problem statement.

Tester’s Code :

using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        if(n%10==0)
            cout<<0<<'\n';
        else if(n%5==0)
            cout<<1<<'\n';
        else
            cout<<"-1\n";
    }
    return 0;
} 

Problem B

Analysis :
The key fact to notice here is that we can subtract 1 always and as many times as we want so its always possible for a positive number x to be 0 by subtracting 1 ‘x’ number of times if the total sum of the array is negative then its impossible to achieve 0, Hence the problem reduces to checking if the sum of all array elements is >=0 or not is yes then Print “YES” else Print “NO”.

Tester’s Solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n],s=0;
        for(auto &i:a)
        {
            cin>>i;
            s+=i;
        }
        if(s<0)
            cout<<"NO\n";
        else 
            cout<<"YES\n";
    }
    return 0;
}

Problem C
Analysis :

The problem reduces to finding all possible Solutions to p*(500)+q*(100)+r*(50)=x
If we look at the problem constraints very carefully we can see that we can brute force the values of p,q,cr just by running nested for loops and at our worst case we will have o(505050) which will pass the time limit given

Setter’s Solution :

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,x;
    cin>>a>>b>>c>>x;
    int ans=0;
    for(int i=0;i<=a;i++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int k=0;k<=c;k++)
            {
                if(i*500+j*100+k*50==x)ans++;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

Problem D

Analysis :
In this problem we can first think of just dividing the whole volume by 2 which would gives a optimal solution but then as per the problem statement we need the 2 parallelepiped of blue and red the resulting operation which we taught about in some cases wouldn’t give a parallelepiped in fact there will be some residue . Think of Constructing 2 optimal Parallelepiped we see that we can take one surface /rectangle lets say a*b and then multiply it with other side /2 (c/2 in our case) we can have 3 possible combinations like this and also we need to print the difference which turns out to be →

a*b*(c/2) ==> 1st parallelpied 
then rest volume is ==> a*b*c(volume of whole cude)  - a*b*(c/2) 
so difference ==>  a*b*c-2*(a*b*(c/2))

Take the max of all 3 possible combinations.

Tester’s Solution :

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

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min({a*b*c-2*(a*b*(c/2)),a*b*c-2*a*c*(b/2),a*b*c-2*b*c*(a/2)})<<'\n';
    return 0;
}

Problem E

Analysis :
We can say that the optimal solution is the difference in position of first occurrence of A and last occurrence of Z in the given string

And since the solution always exists this problem becomes simply too easy

Tester’s Solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string a;
    cin>>a;
    int fa=a.find('A');
    reverse(a.begin(),a.end());
    int fz=a.find('Z');
    cout<<a.size()-fz-fa<<'\n';
    return 0;
}

Problem F

Analysis :
This was one of the Hardest and also one of the most interesting Problem in our Problem Set .

This is a well-known problem and solutions can be easily found on the Internet. However, what is more important is to grasp the essence of such problems.

Our target is to find max (|xi-xj|+|yi-yj|) i,j->0,n Brute force will not work because it takes O(N^2) time which we cannot afford.

We Can Solve this using 2 methods Both ill explained here

1st Solution
complexity: o(n*log(n))
:
We Can see that in the given constraints xi,yi are always positive Consider the top upper left of the cartesian plane that is x>=0,y>=0 in this region we our points lie we can say that the maximum mantham distance would be the distance between the points nearest to the edges of our restricted area and the points farthest from it also it will have 4 possibilities taking the max out of all of these will give us our answer.

Tester’s Solution :

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int main()
{
    int t=1;
    while(t--)
    {
        int n;
        cin>>n;
        vector<pair<int,int>>a;
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            a.push_back({x,y});
        }
        int dx[4]={0,inf,0,inf};
        int dy[4]={0,0,inf,inf};
        vector<int>v[4];
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<n;j++)
            {
                int x1=a[j].first,y1=a[j].second;
                v[i].push_back(abs(x1-dx[i])+abs(y1-dy[i]));
            }
        }
        for(int i=0;i<4;i++)
        sort(v[i].begin(),v[i].end());
        cout<<max({v[0][n-1]-v[0][0],v[1][n-1]-v[1][0],v[2][n-1]-v[2][0],v[3][n-1]-v[3][0]})<<'\n';
    }
    return 0;
}

2nd Solution
We can optimize this to o(n) using 45° transformation
:
The key point is to expand absolute values. We should be aware that there is another definition of |x|∣x∣, that is |x|=max{x,-x}

So in this problem, we have

|xi-xj|+|yi-yj|=max{xi-xj+yi-yj,xi-xj+yj-yi,xj-xi+yi-yj,xj-xi+yj-yi}

Which can be further rearranged to
|xi-xj|+|yi-yj|=max{xi+yi-(xj+yj),xi-yi-(xj-yj),-xi+yi-(-xj+yj),-xi-yi-(-xj-yj)}

Then we have
max|xi-xj|+|yi-yj|=max{max(xi+yi-(xj+yj)),max(xi-yi-(xj-yj)),max(-xi+yi-(-xj+yj)),max(-xi-yi-(-xj-yj))}

Which can be easily done in O(N) time by storing maximum and minimum of each of the four forms.

If you have referred to a solution on the Internet, that is OK. But the important thing is to understand how this works. The simple expression |x|=max{x,-x} can help you in many more problems.

Setter’s Solution :

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e9;
signed main()
{
    int t=1;
    int dx[4]={1,-1,1,-1};
    int dy[4]={1,1,-1,-1};
    while(t--)
    {
        int n;
        cin>>n;
        vector<int>l(4,inf),h(4,-inf);
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            for(int k=0;k<4;k++)
            {
                int rs=x*dx[k]+y*dy[k];
                l[k]=min(l[k],rs);
                h[k]=max(h[k],rs);
            }
        }
        int ans=0;
        for(int i=0;i<4;i++)
            ans=max(ans,h[i]-l[i]);
        cout<<ans<<'\n';

    }
    return 0;
}

(disclaimer : all the problems were chosen from various online judges)
Hope y’all Read this

[repe_frost]

PB Hustle 5.03

Problem A
Problem B
Problem C
Problem D
Problem E
Problem F

[repe_frost]

PB Hustle 5.04

Problem A

cpp solution :

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    string a;
    cin>>a;
    int ans=INT_MAX;
    for(int i=0;i<a.size()-2;i++)
    {
        int x=(a[i]-'0')*100+(a[i+1]-'0')*10+a[i+2]-'0';
        ans=min(ans,abs(x-753));
    }
    cout<<ans;
    return 0;
}

Problem B

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int n;
    cin>>n;
    int s=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        s+=x;
    }
    if(s==(n*(n+1))/2)
        cout<<"YES\n";
    else
        cout<<"NO\n";
    return 0;
}

Problem C

#include<bits/stdc++.h>

#define int long long
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string a;
        cin>>a;
        int x=count(a.begin(),a.end(),'1');
        cout<<(x*(x+1))/2<<'\n';
    }
    return 0;
}

Problem D

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        int a1=a,b1=b,c1=c;
        int ans1=0,ans2=0;
        while(1)
        {
            if(b>1 && a>0)
                ans1++,a--,b-=2;
            else break;
        }    
        while(1)
        {
            if(b>0 && c>1)
                ans1++,b--,c-=2;
            else break;
        }
        while(1)
        {
            if(b1>0 && c1>1)
                ans2++,b1--,c1-=2;
            else break;
        }    
        while(1)
        {
            if(b1>1 && a1>0)
                ans2++,b1-=2,a1--;
            else break;
        }
        cout<<3*max(ans1,ans2)<<'\n';
 
    }
    return 0;
}

Problem E

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n];
        for(auto &i:a)
        cin>>i;
        int x=0,y=0,z=0,l=0;
        for(int i=1;i<n-1;i++)
        {
            int f=0,p=0;
            x=i;
            for(int j=0;j<i;j++)
            {
                if(a[j]<a[x]){
                    y=j;
                    f=1;
                    break;
                }
            }
            for(int j=i+1;j<n;j++)
            {
                if(a[j]<a[x]){
                    z=j;
                    p=1;
                    break;
                }
            }
            if(f && p){l=1; break;}
        }
        if(!l)
            cout<<"NO\n";
        else
        {
            cout<<"YES\n";
        cout<<y+1<<" "<<x+1<<" "<<z+1<<'\n';
        }
    }
    return 0;
}

Problem F

#include<bits/stdc++.h>

#define int long long
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int t=1;
    while(t--)
    {
        int n;
        cin>>n;
        priority_queue<double,vector<double>,greater<double>>q;
        for(int i=0;i<n;i++)
        {
            double x;
            cin>>x;
            q.push(x);
        }
        while(q.size()>1)
        {
            double a=q.top();
            q.pop();
            double b=q.top();
            q.pop();
            q.push((a+b)/2);
        }
        cout<<q.top()<<'\n';
    }
    return 0;
}

[repe_frost]

PB Hustle 5.05

Problem A
Problem B
Problem C
Problem D
Problem E
Problem F

[repe_frost]

PB Hustle 6.01

Problem A

Note : Please dont output stuff like “Enter the number” this will be marked as a wrong answer

Solution : you need to check the greatest difference between any two numbers and this can be achieved my max(all elements)-min(all elements) and then check if it is greater than than k

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

void solve()
{
    int a[5], k;
    for (int i = 0; i < 5; i++)
        cin >> a[i];
    cin >> k;

    auto m=minmax(a,a+5);
    if (m.second-m.first> k)
        cout << ":(";
    else
        cout << "Yay!";
}

int main()
{
    solve();
}

Problem B

Solution : There are 3 possibilities press button x 2 times (x+x-1) , press button y 2 times (y+y-1), or press x and y simultaneously (x+y) so take the max of all 3 possibilities.

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a,b;
    cin>>a>>b;
    cout<<max({2*a-1,2*b-1,a+b});
    return 0;
}

Problem C

Solution : We can brute force because the constraints are too low. check valid for all substring and print the longest valid substring size.

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
 
int main() {
	string s;
	cin >> s;
	int cnt = 0;
	int ans = 0;
	rep(i,s.size()) {
		if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') cnt += 1;
		else {
			ans = max(ans,cnt);
			cnt = 0;
		}
	}
cout << ans << endl;
}

Problem D

Solution : greedy . sort if according to (10-x%10)%10 (the value u need to add to round up).
then simulate the process.

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a[5]={},s=0;
    vector<pair<int,int>>v;
    for(int  i=0;i<5;i++)
    {
        cin>>a[i];
        v.push_back({(10-a[i]%10)%10,a[i]});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<4;i++)
    {
        s+=get<1>(v[i]);
        s+=(10-s%10)%10;
    }
    cout<<s+v[4].second<<'\n';
    return 0;
}

Problem E

Solution :

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

void solve()
{
    ll n;
    cin >> n;
    ll a[n];
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i > 0 && a[i] > a[i - 1])
            a[i]--;
    }

    if (is_sorted(a, a + n))
        cout << "Yes";
    else
        cout << "No";
}

int main()
{
    solve();
}

Problem F

Problem F :
Setter’s Solution : the answer would be the Number of connected components in the graph minus one. We can use dfs or a DSU.

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct dsu {
    vector<int> data;
    int components = 0;
 
    dsu(int n = -1) {
        if (n >= 0)
            init(n);
    }
 
    void init(int n) {
        data.assign(n + 1, -1);
        components = n;
    }
 
    int find(int x) {
        return data[x] < 0 ? x : data[x] = find(data[x]);
    }
 
    int get_size(int x) {
        return -data[find(x)];
    }
 
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
 
        if (x == y)
            return false;
 
        if (-data[x] < -data[y])
            swap(x, y);
 
        data[x] += data[y];
        data[y] = x;
        components--;
        return true;
    }
};
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int n,m,s;
    cin>>n>>s>>m;
    dsu u(n);
    //int ans=0;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        a--,b--;
        u.unite(a,b);
    }

    cout<<u.components-1<<'\n';
    return 0;
}

[repe_frost]

Problem A

Solution : considering the constrains we can simply check for each number in the given range

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int l,r;
    cin>>l>>r;
    auto f = [&] (int x)
    {
        set<char>s;
        string h=to_string(x);
        for(char c:h)
            s.insert(c);
        return s.size()==h.size();
    };
    for(int i=l;i<=r;i++)
    {
        if(f(i))
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

[Problem - 873A - Codeforces](https://Problem B)

Solution : Since x is <= the min value in the array, we can ignore the last k values in the array and just add x instead, so im initializing the answer with x*k (last k values replaced with x) and then remaining values are added to the answer. Here is a simple code.

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    int n,k,x;
    cin>>n>>k>>x;
    int ans=x*k;
    for(int i=0;i<n;i++)
    {
        int y;
        cin>>y;
        if(i<n-k)ans+=y;
    }
    cout<<ans<<'\n';
    return 0;
}

Problem C

Solution 1: 1. Considering the constraints we can iterate over all possible combinations of a, b, c and count the number of divisors . After finding the number of divisors simply store the count of divisors in an array or map for a combination to avoid tle.

vector<int>vis(1e6+1,-1);
for(int i=1;i<=a;i++)
    {
        for(int j=1;j<=b;j++)
        {
            for(int k=1;k<=c;k++)
            {
                num=i*j*k;
                if(vis[num]!=-1)
                {
                    ans+=vis[num],ans%=mod;
                    continue;
                }
                int cnt= CountofDiv(num);
                ans+=cnt,ans%=mod;
                vis[num]=cnt;
            }
        }
    }

Solution 2: using sieve store the values of number of divisors and then just apply it in the formula .

#include<bits/stdc++.h>

using namespace std;

#define int long long
int d[1000001];
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OJ
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
    
    for(int i=1;i<=1000000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
        d[j]++;
    }
    int a,b,c;
    cin>>a>>b>>c;
    int m=(1<<30);
    int ans=0;
    for(int i=1;i<=a;i++)
    {
        for(int j=1;j<=b;j++)
        {
            for(int k=1;k<=c;k++)
            {
                ans=(ans%m + d[i*j*k]%m)%m;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

Problem D

Solution : We only have to satisfy this condition, no segment [x, y] satisfying the property , such that 1 ≤ l ≤ x ≤ y ≤ r ≤ ,
which means there shouldn’t be any subarray in range [l,r] having same count of distinct elements.
First we will check if it’s possible to get the ans we can do this by simply iterating from 1 till n
while cnt of distinct elements is less than k . if not possible print -1 -1.
Then we have to make sure there isn’t any subarray having same count of distinct elements.
For this we can simply use using multiset. Since our array starts from index 1 we will increment start index by 1 only if cnt(arr[start])>1
This will make sure our array is the smallest possible satisfying having count of distinct elements
equal to k

 vector<int>cnt(100001);
    vector<int>vis(100001);
    int x=-1,y=-1;
    int csize=0;
    int i=0,j=0;
        while(j<n && csize!=k)
        {
            if(vis[arr[j]])
            {
                cnt[arr[j]]++;
            }
            else
            {
                csize++;
                cnt[arr[j]]++;
                vis[arr[j]]++;
            }
            j++;
        }
        if(j==n && csize<k)
        {
          cout<<-1<<" "<<-1; 
           return;
        }
        
        while(i<n)
        {
        int ccnt=cnt[arr[i]];
        if(ccnt==1)
        {
            break;
        }
        cnt[arr[i]]--;
        i++;
        }
       
        x=i+1,y=j;
        
    
    cout<<x<<" "<<y;

Problem E

Solution : we notice that wen a and b both are equal there are infinite solutions , when b>a there are 0 solutions , when b<a we can write a%x=b as a=mx+b moving somethings around we can rewite the equation as a-b=mx => o=m*x (o=a-b) now basically we need to find two number whoes product is a-b this is nothing but the factors of (a-b) .rest is just checking if the mod equation works.

#include<bits/stdc++.h>

using namespace std;
#define int long long

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b;
    cin>>a>>b;
    if(a==b)
    cout<<"infinity\n";
    else if(b>a)
    cout<<0;
    else
    {
        int y=a-b,ans=0;
        for(int i=1;i*i<=y;i++)
        {
            if(y%i==0)
            {
                if(i>b)ans++;
                if(i*i!=y && (y/i)>b)
                ans++;
            }
        }
        cout<<ans;
    }
    return 0;
}

Problem F

Solution : Let’s denote a way to distribute numbers as a painting. Let’s also call the paintings that meet the constraints good paintings (and all other paintings are bad).

We can solve the problem for each connected component of the graph independently and multiply the answers. Let’s analyze a painting of some connected component. If some vertex has an odd number written on it, then we should write even numbers on all adjacent vertices, and vice versa. So in fact we need to check if the component is bipartite, and if it is, divide it into two parts. The number of good paintings is 2^a+2^b
2^a+2^b, where aa is the size of the first part, and bb is the size of the second part, because we write 22’s into all vertices of one part, and 11’s or 33’s into all vertices of another part.

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 999;
const int MOD = 998244353;

int n, m;
vector <int> g[N];
int p2[N];
int cnt[2];
int col[N];
bool bad;

void dfs(int v, int c){
	col[v] = c;
	++cnt[c];
	for(auto to : g[v]){
		if(col[to] == -1) dfs(to, 1 - c);
		if((col[v] ^ col[to]) == 0)
			bad = true;
	}
}

int main() {
    p2[0] = 1;
    for(int i = 1; i < N; ++i)
    	p2[i] = (2 * p2[i - 1]) % MOD;
    	
    int tc;
    scanf("%d", &tc);
    while(tc--){
    	scanf("%d%d", &n, &m);
    	for(int i = 0; i < n; ++i)
    	    g[i].clear();
    	
    	for(int i = 0; i < m; ++i){
    		int u, v;
    		scanf("%d %d", &u, &v);
    		--u, --v;
    		g[u].push_back(v);
    		g[v].push_back(u);
    	}
    	
    	int res = 1;
    	for(int i = 0; i < n; ++i) col[i] = -1;
    	for(int i = 0; i < n; ++i){
    	    if(col[i] != -1) continue;
            bad = false;
            cnt[0] = cnt[1] = 0;
            dfs(i, 0);
    	    if(bad){
    		    puts("0");
    		    break;
    	    }
    	    int cur = (p2[cnt[0]] + p2[cnt[1]]) % MOD;
    	    res = (res * 1LL * cur) % MOD;
    	}
    	
    	if(!bad) printf("%d\n", res);
    }
    
    return 0;
}