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. 