 # PROBDIFF - Editorial

Tester: Istvan Nagy
Editorialist: Taranpreet Singh

Cakewalk

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 == a) {
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 == A)pn(0);
else if(A == A || A == A)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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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

Feel free to share your approach. Suggestions are welcomed as always. #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!=v[i]){
c++;
v.erase(v.begin()+i);
v.erase(v.begin());

``````            break;
}
}

if(v!=v)  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 ??

``````#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
``````

``````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
``````

``````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!