Pop20push21 [TSOH]

Since solutions are not accessible as of now can someone share their approach for 4th problem ?. My approach was to calculate the max subarray sum ending at every index and then doing some manipulations with it but didn’t got time to implement it. Feel free to discuss other problems too.

3 Likes

My solutions in C++ and Python: https://github.com/Sky-Nik/CodeChef/tree/main/Pop20-Push21. I also published a video editorial on YouTube CodeChef Pop20-Push21 Livesove - YouTube

5 Likes

Thanks for sharing :slight_smile:

1 Like

Here is a recursive version of dp: #include <bits/stdc++.h>using namespace std;#define ll long long int#defin - Pastebin.com

Here s=0 implies we haven’t started first subarray
s=1 implies first subarray is going on
s=2 implies first subarray is done
s=3 implies second subarray started
and s=4 implies everythings done

1 Like

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 :joy: (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:

  1. Sort the array.
  2. 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.
  3. Take into account the left numbers from both the halfs.

SOLUTION - O(NlogN)

For problem TSOH.

  1. Use Kadane’s algorithm to store the maximum sum subarray ending at each index in forward and backward direction.
  2. 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.
  3. 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])
  4. 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 :slight_smile:

Wow man! this is nice, Thank you. Really nice explanation!

2 Likes

When will the editorial come for this contest @admin @decipher_