Plz post solution of box reduction as well…if u got ac…
I used binary search over the answer (published above), but maybe there is a greedy linear solution as well
BXRED
#include<bits/stdc++.h>
#define ar array
using namespace std ;
signed main(){
int n ;cin >> n ;
vector<int>a(n) ;
for(int &x:a)
cin >> x ;
sort(a.begin(),a.end()) ; ;
set<ar<int,2>>A ;int ans = n ;
for(int i=0;i<n;i++)
A.insert({a[i],i}) ;
for(int i=n-1;~i;--i){
auto it = A.lower_bound({2*a[i],-1}) ;
if(it==A.end())
continue ;
A.erase(it) ; A.erase({a[i],i}) ;--ans ;
}
cout << ans ;
}
POPPUSH5
#include<bits/stdc++.h>
using namespace std ;
const int mxN =1e5+2 ;
int n,ev[mxN],eu[mxN],ew[mxN],c[mxN],ans=0;
vector<int>adj[mxN] ;
void dfs(int v,int p){
for(int x:adj[v]){
int u = (ev[x]^eu[x]^v) ;
if(u==p)
continue ;
dfs(u,v) ;c[v]+=c[u]+ew[x];
}
}
void dfs1(int v,int p){
if(c[v]==0)
return ;
for(int x:adj[v]){
int u = (ev[x]^eu[x]^v) ;
if(u==p)
continue ;
ans+=(c[u]==0 && ew[x]==1) ;
dfs1(u,v) ;
}
}
signed main(){
cin >> n ;
for(int i=0;i<n-1;i++){
cin >> ev[i] >> eu[i] >> ew[i] ;
adj[ev[i]].push_back(i) ;
adj[eu[i]].push_back(i) ; ew[i]-- ;
}
dfs(1,0) ; dfs1(1,0) ;
cout << ans ;
}
1 Like
Yup greedy works too, if we iterate in descending order we have to delete the element <=a[i]/2 at each step.
As a sidenote, iterating in ascending order and deleting lowerbound of a[i]*2 doesnt work in some cases. For example for 1 2 3 4 5 its optimal to club 1-3 and 2-4 together
3 Likes
Fun fact : I just found that my code fails for the samples , but I got an AC 
(BXRED)
INCORRECT_AC_CODE
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
typedef long long ll ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define CS custom_hash
#define vi vector
#define loop(i,a,b) for(ll i=a ;i<b;i++)
#define For(i,n) for(int i=0;i<(ll)n;i++)
#define Rev(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,n) for(int i=1;i<=n;++i)
#define F first
#define S second
#define pb push_back
#define em emplace_back
#define all(v) (v).begin(),(v).end()
#define mems(x, y) memset(x, y, sizeof(x))
#define sz(x) (int)(x).size()
#define mp(a,b) make_pair(a,b)
#define po(n) cout << n <<"\n "
#define ar array
#define endl "\n"
#define PI acos(-1)
#define umap unordered_map
#define gmap gp_hash_table
#define ld long double
#define SA(n) __builtin_popcountll(n)
#define LB lower_bound
#define UB upper_bound
// debugger credits: https://codeforces.com/blog/entry/68809
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template <typename T, typename V>
void mdebug(map<T,vi<V>>m){
for(auto x:m){
cerr << x.F << " : [ " ;
for(auto c:x.S)
cerr << c << " ";
cerr << "]"<<endl ;
}
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
//#ifndef ONLINE_JUDGE
//#ifndef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
//#else
//#define debug(x...)
//#endif
//#pragma GCC optimize "trapv"
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//template credits :William Lin(tmwilliamlin168)
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
template<class T> bool umin(T& a, const T& b) {
return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) {
return a<b?a=b, 1:0;
}
template<class A> void read(vi<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
cin >> x;
}
void read(double& d) {
string t;
read(t);
d=stod(t);
}
void read(long double& d) {
string t;
read(t);
d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class A> void read(vi<A>& x) {
EACH(a, x)
read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
EACH(a, x)
read(a);
}
string to_string(char c) {
return string(1, c);
}
string to_string(bool b) {
return b?"true":"false";
}
string to_string(const char* s) {
return string(s);
}
string to_string(string s) {
return s;
}
string to_string(vi<bool> v) {
string res;
FOR(sz(v))
res+=char('0'+v[i]);
return res;
}
template<size_t S> string to_string(bitset<S> b) {
string res;
FOR(S)
res+=char('0'+b[i]);
return res;
}
template<class T> string to_string(T v) {
bool f=1;
string res;
EACH(x, v) {
if(!f)
res+=' ';
f=0;
res+=to_string(x);
}
return res;
}
template<class A> void pff(A x) {
cout << to_string(x);
}
template<class H, class... T> void pff(const H& h, const T&... t) {
pff(h);
pff(t...);
}
void print() {
pff("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) {
pff(h);
if(sizeof...(t))
pff(' ');
print(t...);
}
struct PH{
size_t operator()(const pair<int,int>&x)const{
size_t ans=0;
for(int i=0;i<x.first;i++)
ans+=x.second;
return ans;
}
};
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
// void DBG() {
// cerr << "]" << endl;
// }
// template<class H, class... T> void DBG(H h, T... t) {
// cerr << to_string(h);
// if(sizeof...(t))
// cerr << ", ";
// DBG(t...);
// }
// // #ifdef _DEBUG
// #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
// // #else
// // #define dbg(...) 0
// // #endif
template<class T> void offset(ll o, T& x) {
x+=o;
}
template<class T> void offset(ll o, vi<T>& x) {
EACH(a, x)
offset(o, a);
}
template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
EACH(a, x)
offset(o, a);
}
template<class T> void fk(T a) {
print(a) ;
exit(0) ;
}
void FIO(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin) ;
freopen("output.txt","w",stdout) ;
#endif
}
#define pf(n) return print(n)
#define int ll
long const M=1e9+7;
const ll INF =1e18;
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
//Syntax to create a min heap for priority queue
// priority_queue <T, vector<T>, greater<T>>pq ;
//make sure to clear the adjacency list for every test case
// check mxN size
//check if numbers are big use powl,sqrtl,builtin_popcountll()......
const long mxN =1e5+2 ;
void solve(){
int n ;read(n) ;
vi<int>a(n) ;read(a) ;
sort(all(a)) ;
set<ar<int,2>>A ;
FOR(n){
A.insert({a[i],i}) ;
}
int ans =n ;
// debug(A);
vi<int>b(n) ;
for(int i=n-1;~i;--i){
if(b[i])
continue ;
auto it = A.lower_bound({2*a[i],-1}) ;
if(it==A.end())
continue ;
// debug(a[i],(*it)[1]) ;
b[(*it)[1]]=1 ;
A.erase(it) ;
// A.erase({a[i],i}) ;
--ans ;
}
pf(ans) ;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//cout << setprecision(20) << fixed ;
int T=1;
// read(T);
FOR(_,T){
// pff("Case #", _+1, ": ");
solve();
}
return 0;
}
2 Likes
Use greedy:
- Sort the array.
- Try to put first half of the sorted array numbers on the top of second half numbers iteratively because if once sorted and we can’t put some number having index i from first half on top of number at index j in the seconf half we will not be able to put any one after i on the top of number at index j.
- Take into account the left numbers from both the halfs.
SOLUTION - O(NlogN)
For problem TSOH.
- Use Kadane’s algorithm to store the maximum sum subarray ending at each index in forward and backward direction.
- Now calculate the maximum value till index i for both the arrays i.e. forward and backward and let’s say we stored in arrays forward_max and backward_max.
- Now iterate for each index i in [0, n-2] and update max_val(say initial = -INF) as max(max_val, max_forward[i] + max_backward[i+1])
- Output max_val.
3 Likes
Your idea passes all testcases, but still it doesn’t work either. Here is counterexample: n=4 and a=[15, 6, 5, 3]
According to your algorithm 2nd box is inside of first. And then we got that the answer is 3.
However, it is optimal to put 3rd box in 1st and put 4th box in 2nd. So the real answer is 2.
5 Likes
ooh thanks for pointing that out
Nice catch, how about doing the above greedy once traversing the sorted array in ascending and descending order and then taking the minimum of both of them ?
If I correctly understand then here is a counterexample: n=6 and a=[4, 7, 11, 32, 49, 70]. The answer is 3(just make such pairs: 1-4, 2-5, 3-6).
If we run that algorithm in ascending order we will get such pairs: 1-3, 2-4. And then result is 4
In descending order we have: 6-4, 5-3. And the result is 4 too
5 Likes
Can you share the correct approach please ?
Let’s denote M as number of boxes which are inside of some box in optimal solution.
Then the answer will be n-M.
Let’s mention that we can run binary search to find M.
Let’s see how to check if M>=x where x is an integer. We need to determine if we can put x boxes in some other boxes.
Obviously we need put boxes with the smallest width inside boxes with the largest width.
So, to check if M>=x, we just sort the initial array and check if a[i] *2<=a[n-x+i] for every i in [0;x-1]
That is approach for problem BXRED
4 Likes
Great explanation thanks a lot 
Wow man! this is nice, Thank you. Really nice explanation!
2 Likes
The editorial will be posted tomorrow afternoon for sure. Sorry for the inconvenience. 
3 Likes
My approach was to store the subarray sums where the each element in each subarray is positive,and then pick the maximum 2 sums and sum it and give the answer.
I handled the all negative and 1 positive and others negative cases differently easily,but the still the solution is wrong .
Can u tell the problem in my approach??
Here is my code
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<pair<int,int>,long> a ,pair<pair<int,int>,long> b){
return a.second<b.second;
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)cin>>arr[i];
map<pair<int,int>,long> m;
long sum=0;
int beg=-1;
for(int i=0;i<n;i++){
if(arr[i]>0 && beg==-1){
sum+=arr[i];
beg=i;
}
else if(arr[i]>0 && beg>=0)
sum+=arr[i];
else if(arr[i]<=0 && sum>0){
m.insert({{beg,i-1},sum});
sum=0;
beg=-1;
}
}
if(sum>0){
m.insert({{beg,n-1},sum});
sum=0;
beg=-1;
}
/*
for(auto i=m.begin();i!=m.end();i++){
cout<<(i->first).first<<" "<<(i->first).second<<" "<<i->second<<endl;
}
*/
if(m.size()==0){
sort(arr,arr+n);
cout<<arr[n-1]+arr[n-2]<<endl;
}
else if(m.size()==1){
if((m.begin()->first).first==(m.begin()->first).second){
sort(arr,arr+n);
cout<<arr[n-1]+arr[n-2]<<endl;
}
else
cout<<(m.begin()->second)<<endl;
}
else{
vector<pair<pair<int,int>,long> > v;
for(auto &i : m){
v.push_back(i);
}
sort(v.begin(),v.end(),cmp);
cout<<v[v.size()-1].second+v[v.size()-2].second<<endl;
}
}
I guess u forgot 
No @longtimenoshe2 I posted it but they are still not added with all the problems by codechef.
Please check them out below are the links:
POPPUSH1 - POPPUSH1 - Editorial
EASYABC - EASYABC - Editorial
TSOH - TSOH - Editorial
BXRED :BXRED - Editorial
POPPUSH5 - POPPUSH5 – Editorial
1 Like