PROBDIFF - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Soumyadeep Pal
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

Given the difficulty level of four problems as A_1, A_2, A_3, and A_4, find the maximum number of problem sets we can make. One problem can be used only once.

A problem set consists of two problems of distinct difficulties.

QUICK EXPLANATION

  • We can only make either 0 or 1 or 2 problem sets.
  • Two problem sets are possible if no difficulty appears more than twice.
  • One problem set is possible if all difficulties are not the same.
  • Otherwise, no problem set is possible.

EXPLANATION

Idea

Since there is a total of 4 problems, and each problem set requires 2 problems and no problem can be reused, at max 2 problem sets are possible.

We just need to calculate the maximum number of problem sets keeping the distinct difficulty constraint in mind.

If all elements are the same, then no problem set is possible, as no two problems have distinct difficulties.

Now, assuming all difficulties are not the same. We can create one problem set for sure. Now, if the remaining two problems have the same difficulty, we end up with only one problem set.

So, we need to choose the first two problems wisely. Specifically, consider example difficulties 1 2 2 3 , if we pair 1 with 3, we end up with only one problem set, but we can make two problems set if we make pairs (1, 2) and (2, 3)

We can generalize and conclude that the only time we are forced with only one problem set is when there are three problems with the same difficulty.

Lastly, if no element appears more than twice, we can make them into two problem sets.

Implementation

Let’s sort all difficulties. Then

  • If A_1 = A_4, then all difficulties are same, leading to 0 problem sets.
  • Otherwise, if A_1 == A_3 or A_2 == A_4, then a value appears thrice, leading to 1 problem set.
  • Otherwise, we can make two problem sets.

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

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


int main() {
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
	    vector<int> a(4);
	    set<int> s;
	    for (int i = 0; i < 4; i++) {
		    cin >> a[i];
		    s.insert(a[i]);
	    }
	    sort(a.begin(), a.end());
	    if (s.size() >= 3) {
		    cout << "2\n";
	    } else if (s.size() == 1) {
		    cout << "0\n";
	    } else if (a[1] == a[2]) {
		    cout << "1\n";
	    } else {
		    cout << "2\n";
	    }
    }
    return 0;
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
    #include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../in.txt", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    forn(tc, T)
    {
	    int mx = 2;
	    vector<int> A(11);
	    forn(i, 4)
	    {
		    int tmp;
		    cin >> tmp;
		    ++A[tmp];
		    mx = max(mx,A[tmp]);
	    }
	    cout << 4 - mx << endl;
    }

    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class PROBDIFF{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = 4;
        int[] A = new int[N];
        for(int i = 0; i< N; i++)A[i] = ni();
        Arrays.sort(A);
        if(A[0] == A[3])pn(0);
        else if(A[0] == A[2] || A[1] == A[3])pn(1);
        else pn(2);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new PROBDIFF().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

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

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
long long int t;
cin>>t;
while (t–)
{
map<int,int>mp;
for(int i=0; i<4; i++)
{
int t;
cin>>t;
mp[t]++;
}
int cnt=0,cnt1=0;
for(auto i : mp)
{
if(i.second<=2)
cnt+=i.second;
else
cnt++;

   }
   cout<<cnt/2<<"\n";
}
return 0;

}

//CAN ANYONE TELL WHAT’S WRONG IN THIS CODE
//WHY IS IS GIVING WA ON SUBMISSION

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–){
vector v;
int temp,c=0;
for(int i=0;i<4;i++){
cin>>temp;
v.push_back(temp);
}
for(int i=1;i<4;i++){
if(v[0]!=v[i]){
c++;
v.erase(v.begin()+i);
v.erase(v.begin());

            break;
        }
    }

    if(v[0]!=v[1])  c++;
    cout<<c<<"\n";
}
return 0;

}

How can 1 2 3 2,have 2 sets (1,2) and (2, 3) when it is clearly mentioned that “A problem can belong to at most one problem set.” Problem statement needs to have better English. I asked the same doub t during contest but no one answered.

1 Like

A1 = 1, A2 = 2, A3 = 3, A4 = 2. {A1, A2} = {1,2} is one problem set. {A3, A4} = {3,2} is another problem set. There is another combination that also produces two problem sets, but the problem only asks for the number of problem sets that can be generated, which in this case is two. I agree that the problem statement is a little confusing.

3 Likes

sets are stored unique values so I used Set for this problem but the result came WA.

This Problem gave AC if I used vector or map, And gave WC if I used Set, Why ??
Please anyone can explain this?

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

void solve() {
	set<int> arr;
	int n;
	for (int i = 0; i < 4; i++) {
		cin >> n;
		arr.insert(n);
	}
	int ans  = arr.size();
	if ( ans == 1) {
		cout << 0 << endl;
	}
	else if (ans == 2 || ans == 3) {
		cout << 1 << endl;
	}
	else {
		cout << 2 << endl;
	}

}

int main() {

	int n;
	cin >> n;

	while (n != 0) {
		solve();
		n--;
	}
	return 0;
}

Try this test case

Input

1
1 2 1 2

Expected Output

2

Your Output

1
1 Like

this particular submission kept giving WA, which surprised me

t = int(input())
for i in range(1, t+1):
	difficulties = list(map(int, input().split(" ")))
	freq = {}
	pSet = []
	# get frequency of the difficulties
	for i in difficulties:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1
	#try to find 2 distinct questions and increase possible p Sets by 1 if found
	while True:
		ques = {}
		if sum(map(bool, freq.values())) >= 2:
			for i in freq:
				if i not in ques:
					ques[i] = 1
					freq[i] -= 1
				else:
					pass
			if sum(map(bool, ques.values())) >= 2:
				pSet.append(ques)
		else:
			break
	print(len(pSet))

Ooo I see, I need to give more attention to questions.
Thanks mate.

Try this test case

Input

1
1 2 3 3

Expected Output

2

Your Output

1

ohh, seems i might have over complicated my solution. thanks a lot

If anyone is interested in reducing number of if-else

unordered_map <int, int> mp;
int ans = 2;
for(int i=0; i<4; i++) {
    int a;
    cin >> a;
    mp[a]++;
    if (mp[a] > 2) ans--;
}
cout << ans << "\n";
2 Likes

Nice!