HackerEarth Crushing Violence problem solution

YASH PAL,
In this HackerEarth Crushing Violence problem solution, The students of college XYZ are getting jealous of the students of college ABC. ABC managed to beat XYZ in all the sports and games events. The main strength of the students of ABC is their unity. The students of XYZ decide to destroy this unity. The geeks of XYZ prepared a special kind of perfume. Anyone who inhales this perfume becomes extremely violent. The students of XYZ somehow manage to spread this perfume throughout ABC’s campus atmosphere.
 
There are N boys {1,2,3,…..N} and N girls (1,2,3,…..N) in ABC college. Each boy has a crush on a single girl and each girl has a crush on a single boy. Since the perfume has been inhaled by each and every student of ABC college, every student decides to beat up his/her crush’s crush, ie. , if boy x has a crush on girl y and girl y has a crush on boy z, x will beat z up, provided, of course, if x and z is not the same person.
 
The doctor of ABC college foresees this situation. He cannot stop so many people from beating each other up, however, he can be prepared for the worst-case patient(s). The worst-case patient(s) will be the patient(s) who get(s) beaten up by the maximum number of students. The doctor comes to you for help. He has 2 questions for you :
 
  1. What is the number of beatings received by the worst-case patient(s) ?
  2. What is the total number of pairs of students who ended up beating up each other ?
 
 
HackerEarth Crushing Violence problem solution

 

 

HackerEarth Crushing Violence problem solution.

#include<stdio.h>
int main()
{
    int t,n,b[100010],g[100010],i,j;
    scanf("%d",&t);
    while(t--)
    {
        int bbeat[100010]={0},gbeat[100010]={0};
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&g[i]);
        }
        for(i=1;i<=n;i++)
        {
            if(g[b[i]]!=i)
            {
                bbeat[g[b[i]]]++;
            }
            if(b[g[i]]!=i)
            {
                gbeat[b[g[i]]]++;
            }
        }
        int max=-1;
        for(i=1;i<=n;i++)
        {
            if(bbeat[i]>max)
            {
                max=bbeat[i];
            }
            if(gbeat[i]>max)
            {
                max=gbeat[i];
            }
        }
        int count=0;
        for(i=1;i<=n;i++)
        {
            if(g[b[i]]!=i && g[b[g[b[i]]]]==i)
            {
                count++;
            }
            if(b[g[i]]!=i && b[g[b[g[i]]]]==i)
            {
                count++;
            }
        }
        printf("%d %dn",max,count/2);
    }
    return(0);
}
 

Second solution

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

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define PII pair<int,int>
#define all(x) x.begin(),x.end()
#define VI vector<int>
#define VII vector<pair<int,int> >
#define VL vector<long long int >
#define VLL vector<pair<long long ,long long > >
#define PLL pair<long long ,long long >
#define itr iterator
#define fill(x,v) fill(all(x),v)

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define sc4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define sc5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)

#define pr1(x) printf("%dn",x)
#define pr2(x,y) printf("%d %dn",x,y)
#define pr3(x,y,z) printf("%d %d %dn",x,y,z)
#define pr4(a,b,c,d) printf("%d %d %d %dn",a,b,c,d)
#define pr5(a,b,c,d,e) printf("%d %d %d %d %dn",a,b,c,d,e)

#define scll(x) scanf("%lld",&x)
#define prll(x) printf("%lldn",x)
#define ms(x) memset(x,0,sizeof(x))

#define ll long long int
#define li long int
#define ff float
#define db double

#define rep(i,a,b) for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>=b;i--)

#define print_v(x) for(int i=0;i<x.size();i++) cout << x[i] << " " 
#define debug(x) cout << "#debug" << " " << x << endl

#define MOD 5000000

int random_long(int digit=8)
{
   int len=digit;
   int x=0;
   for ( int i = 0; i < len; ++i )
   {
    int dig = rand() % 10;
    while ( x == 0 && dig == 0 )
      dig = rand() % 10;
    x = x * 10 + dig;
  }
   return x;
}

int random(int l, int r)
{
    int diff = r - l + 1;

    return l+random_long()%diff;

}

VI G,B,MG,MB;
int main(){

    int t;
    sc1(t);
    assert(t<=10 && t>=1);
    while(t--){
        int n,i;
        sc1(n);
        assert(n<=100000 && n>=1);
        map< pair<int,int> ,int > S1,S2;
        
        G.resize(n+1);
        B.resize(n+1);
        MG.resize(n+1);
        MB.resize(n+1);

        rep(i,1,n+1) {
            sc1(B[i]);
            assert(B[i]<=n && B[i]>=1);     
        }
        rep(i,1,n+1) {
            sc1(G[i]);
            assert(G[i]<=n && G[i]>=1);
        }
    
        fill(MB,0);
        fill(MG,0);
        int maxx = 0;
        rep(i,1,n+1){
            if(i!=G[B[i]]){
                MB[G[B[i]]]++;
                maxx = max(maxx, MB[G[B[i]]]);
                S1[mp(max(i,G[B[i]]),min(G[B[i]],i))]++;
            }
        }

        rep(i,1,n+1){
            if(i!=B[G[i]]){
                MG[B[G[i]]]++;
                maxx = max(maxx, MG[B[G[i]]]);
                S2[mp(max(i,B[G[i]]),min(B[G[i]],i))]++;
            }
        }   
        int ans = 0;

        for(map<PII,int > :: itr it=S1.begin(); it!=S1.end() ; it++){
            if(it->sd >=2){
                ans ++;
            }
        }
        for(map<PII,int > :: itr it=S2.begin(); it!=S2.end() ; it++){
            if(it->sd >=2){
                ans ++;
            }
        }
        pr2(maxx,ans);
    }
    return 0;
}
 
coding problems solutions HackerEarth

Leave a Reply

Your email address will not be published. Required fields are marked *