PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Simple
PREREQUISITES
None
PROBLEM
Given a rod weighing W_r and N weights, ith weight weighing w_i. In order to maintain balance, Chef can lift rod if and only if on both sides of rod, the sequence of weights is symmetric. Determine if Chef can lift the rod weighing atleast W.
QUICK EXPLANATION
- If grouping by weight, some weight appear odd number of times, the last one cannot be paired. Calling this last weight as useless weight.
- After discarding useless weights, if the sum of weight of rod and the remaining weights exceed the target weight, Chef can lift rod with weight atleast W, otherwise Chef can’t.
EXPLANATION
Since we want to check if Chef can lift weight at least W, it is sufficient to determine the maximum weight Chef can lift while maintaining balance, and compare it with W.
Only constraint that stops Chef from adding all weight is the balance. Let’s group the weights by their weight in grams. We can see that weights of different weight do not affect each other.
Say there are C weights of weight G.
- If C is even, we can put C/2 weights on left side and C/2 weights on the right side, thus maintaining balance while adding weight C*G to the total weight.
- If C is odd, we cannot pair the last weight. we can put \lfloor C/2 \rfloor weights on left side and \lfloor C/2 \rfloor weights on the right side, thus maintaining balance while adding weight (C-1)*G to the total weight.
Hence, it is sufficient to count the occurrence of each weight, compute the maximum weight achievable while maintaining balance and compare it with target.
Summary
Can you write expression to avoid writing if condition or ternary operator for handling even and odd case?
Summary
(C-C%2)*G
Bonus
- Can Chef lift exactly W weight?
- What is the minimum weight greater than W the chef can lift?
TIME COMPLEXITY
The time complexity is O(N*log(N)) using normal sorting, or O(N+W) using counting sort.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int maxw = 2e5, maxwr = 2e4, maxwi = 1e5, maxt = 10, maxn = 1e5;
int f[maxwi + 1];
int main()
{
int t; cin >> t;
int n, w, wr;
while(t--){
cin >> n >> w >> wr;
memset(f, 0, sizeof(f));
int x;
for(int i = 0; i < n; i++){
cin >> x;
f[x]++;
}
long long int tot = wr;
for(int i = 1; i <= maxwi; i++)tot += (long long int)i * 2 * (f[i] / 2);
string ans = (tot >= w ? "YeS" : "No");
cout << ans << endl;
}
}
Tester's Solution
import java.util.*;
import java.io.*;
class BENCHP{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), targetW = ni(), rodW = ni();
int[] W = new int[N];
for(int i = 0; i< N; i++)W[i] = ni();
Arrays.sort(W);
long maxWeight = rodW;
for(int i = 0, ii = 0; i< N; i = ii){
while(ii < N && W[i] == W[ii])ii++;
int cnt = (ii-i);
maxWeight += (cnt-cnt%2)*(long)W[i];
}
pn(maxWeight >= targetW?"yEs":"nO");
}
//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 BENCHP().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. 