CAC203 - CRACK-A-CODE 2.0 Editorial

editorial
, , ,
1

Practice
Contest

Author: Pushkar Kukde
Tester: Mayuresh Patle

DIFFICULTY:

SIMPLE

PREREQUISITES:

Maps

PROBLEM:

Given certain letters with values, an array of integers, 4 special characters with values and a number locknum, find two combinations such that the difference between the sum of above (value of letters + a number from array of integers which is divisible by the letter value + special character values) is greater than locknum

QUICK EXPLANATION:

Check all the possible combinations and find the difference between the maximum and minimum obtainable value.

EXPLANATION:

The idea is to just brute force all the combinations. Take the letter value as the key and store all divisible values of it as the values to that key.
To get the min value, check if the sum of key with the minimum divisible value is less than existing minimum value or not.
To get the max value, check if the sum of key with the maximum divisible value is greater than existing maximum value or not.
Check the difference between max value and min value with the locknum variable. Print “WOOF” if greater, else print “HECK”.
Take care of the case where it is possible that no elements from the array are divisible by any of the letter values.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {   
        ll n,k,locksum;
        cin>>n>>k>>locksum;
        
        vector<char> charcode(n);
        vector<ll> charval(n); 
        for(auto i = 0 ; i < n ; ++i)
            cin>>charcode[i]>>charval[i];
        
        map<ll,char> alpcode;
        for(auto i = 0 ; i < n ; ++i)
            alpcode[charval[i]] = charcode[i];
        
        vector<ll> arr(k); 
        for(auto i = 0 ; i < k ; ++i)
            cin>>arr[i];
        
        vector<ll>spe(4);
        for(auto i = 0 ; i < 4 ; ++i)
            cin>>spe[i];
        
        vector<char> spe1 = {'@','#','%','&'};
        vector<pair<ll,char>> spepair(4);
        for(int i = 0 ; i < 4; ++i)
            spepair[i] = make_pair(spe[i],spe1[i]);
        
        sort(begin(spepair),end(spepair));
        
        map<ll,set<ll>> val;
        
        for(auto i : arr) {
            for(auto j : charval) {
                if(i%j == 0)
                    val[j].insert(i);
            }
        }
        unsigned ll minval = ULONG_MAX, maxval = 0;
        ll minidx = -1, maxidx = -1;
        ll actmin = 0, actmax = 0;
        for(auto i : val) {
            auto itr = i.second.begin();
            auto itr1 = i.second.rbegin();
            if(minval > i.first + *itr) {
                minval = i.first + *itr;
                minidx = i.first;
                actmin = *itr;
            }
            if(maxval < i.first + *itr1) {
                maxval = i.first + *itr1;
                maxidx = i.first;
                actmax = *itr1;
            }
        } 
        minval += spepair[0].first;
        maxval += spepair.back().first;
        if(maxval - minval > locksum && maxidx >= 0 && minidx >= 0)
            cout<<"WOOF\n";
        else
            cout<<"HECK\n";
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
int main()
{
	//freopen("si.txt","r",stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	string ans[]={"HECK\n","WOOF\n"};
	cin>>T;
	while(T--)
	{
		ll n,k,ln,i,mn=1e10,mx=-1,t;
		char c;
		cin>>n>>k>>ln;
		unordered_map <ll,set<ll>> m;
		while(n--)
		{
			cin>>c>>t;
			m[t]=set<ll>();
		}
		for(i=0;i<k;++i)
		{
			cin>>t;
			for(auto& p:m) if(t%p.F==0) p.S.insert(t);
		}
		for(i=0;i<4;++i) cin>>t,mn=min(mn,t),mx=max(mx,t);
		i=0;
		mx-=mn;
		for(auto p:m) if(p.S.size())
		{
			for(auto q:m) if(q.S.size())
			{
				if(abs(mx+p.F+*(--(p.S.end()))-q.F-*q.S.begin())>ln)
				{
					i=1;
					break;
				}
			}
			if(i) break;
		}
		cout<<ans[i];
	}
	return 0;
}
1 Like