SORTHAT - Editorial

PROBLEM LINK:

Practice

Contest

Author: Sibasish Ghosh

Tester: Pritish Nayak

Editorialist: Sibasish Ghosh

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given the traits of a student, you need to decide which House the student will be sorted into. Each House has its own set of four traits. You need to figure out which House’s traits are present in the student the maximum number of times and sort the student into that House. If there are multiple Houses satisfying the condition, sort the student into the lexicographically smallest House.

EXPLANATION:

Create a 4\times 4 matrix that contains all the 16 traits. Each row of the matrix will contain all the 4 traits of a particular House.

Let’s think for a particular student. For each trait of that student, search the trait in the Traits Matrix. And note down the row where it was found. This row will represent the House the trait belongs to. Maintain a count for each House. Finally, print the House with the maximum count. If there are multiple Houses satisfying the condition, print the lexicographically smallest House.

Refer to the solutions below if you face any problem.

SOLUTIONS:

Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()

using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input3.txt","r",stdin);
    // freopen("output3.txt","w",stdout);
    ll t=1;
    cin>>t;
    string houses[4]={"Gryffindor", "Slytherin", "Ravenclaw", "Hufflepuff"};
    string trait[4][4]={"Courage", "Bravery", "Chivalry", "Daring",
                        "Resourcefulness", "Cunning", "Ambition", "Determination",
                        "Intelligence", "Wit", "Wisdom", "Creativity",
                        "Diligence", "Dedication", "Fairness", "Patience"};
    while(t--)
    {
        ll k,i,j,cnt[4]={0},mx=0;
        cin>>k;
        string s;
        while(k--)
        {
            cin>>s;
            for(i=0;i<4;i++)
            {
                for(j=0;j<4;j++)
                {
                    if(s == trait[i][j])
                        cnt[i]++;
                }
            }
        }
        string ans="z";
        for(i=0;i<4;i++)
        {
            if(cnt[i] > mx)
            {
                mx=cnt[i];
                ans=houses[i];
            }
            else if(cnt[i] == mx)
                ans=min(ans,houses[i]);
        }
        cout<<ans<<"\n";
    }
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   #ifdef Zoro
   freopen("/home/pritish/Competitive/in", "r", stdin);
   freopen("/home/pritish/Competitive/out", "w", stdout);
   #endif  
 
   int N;
   cin>>N;
 
   assert(N>=1&&N<=100000);
   
   set<string> mpp[4];
   mpp[0]={"Courage", "Bravery", "Chivalry","Daring"};
   mpp[1]={"Diligence", "Dedication", "Fairness","Patience"};
   mpp[2]={"Intelligence", "Wit", "Wisdom", "Creativity"};
   mpp[3]={"Resourcefulness", "Cunning", "Ambition","Determination"};
 
   for (int i = 0; i < N; i++)
   {
     int K;
     cin>>K;
 
     assert(K>=1&&K<=16);
 
     int a[4]={0};
     for(int j = 0; j< K; j++)
     {
        string s;
        cin>>s;
        
        int cnt=0;
        for(int l=0;l<4;l++)
        {
          if(mpp[l].find(s)!=mpp[l].end())
            a[l]++,cnt++;
        }
 
        assert(cnt>0);
     }
     int mx=*max_element(a,a+4);
 
     if(a[0]==mx)cout<<"Gryffindor\n";
     else
     if(a[1]==mx)cout<<"Hufflepuff\n";
     else
     if(a[2]==mx)cout<<"Ravenclaw\n";
     else 
     cout<<"Slytherin\n";
   }
 
   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
} 

Feel free to write your approach in the comments :slight_smile:

3 Likes

Submit button is not present.

Sorry about that. It takes a bit of time for Codechef to move the problems to the practice section. But, now I guess all problems have been moved for practice. You can now submit your solutions.