Hey look here! IMP(PBOXES)

OK guys, when the contest ends, we ought to read the editorials and up solve problems which we couldn’t solve. OK, lets consider Nov Long Challenge, I couldn’t solve PBOXES problem.
I read the editorial(PBOXES EDITORIAL), got a fair idea(min cost-max flow, segment trees) what the editorial is trying to convey. I read the code portraying the editorial, tried and trying very very hard to understand them.

You can’t understand the code, until you know what every line does. So, trying my best, putting cout statements line by line, to get a clear picture what every line does!

I persisted, understanding every line…

But heck, its over a week, and things are getting overboard and still I have just covered a minuscule part of code…

And these recursions, oh my God!

Forget about solving such problems with that code, I am not able to understand yet what the code does.

How to overcome that???

I know this is a common issue for many competitive programmers out here, they can’t solve a problem, and when they read the editorial, they can’t understand it.

Please guide us!!!

My so-far code to understand P-BOXES.

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector vi;

typedef pair<ll,int> pli;
struct Tree {
typedef pli T;
const pii LOW = mp(1234567890,-1);
T f(T a, T b) { return min(a, b); }

int n;
vector s;
Tree() {}
Tree(int m, T def=mp(0,0)) { init(m, def); }
void init(int m, T def) {
cout<<“init function is called with m and def as: “<<m<<” (”<<def.first<<","<<def.second<<")\n";
n = 1; while (n < m) n *= 2;
cout<<“n updated value: “<<n<<”\n”;
cout<<“s initial values: \n”;
for(auto yk:s)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";
s.assign(n + m, def);
cout<<“s assign values: \n”;
for(auto yk:s)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";
cout<<“LOW: “<<LOW.first<<” “<<LOW.second<<”\n”;
s.resize(2 * n, LOW);
cout<<“s resize values: \n”;
for(auto yk:s)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";
cout<<“s loop values: \n”;
for (int i = n; i --> 1; ){
cout<<“i: “<<i<<”\n”;
cout<<“s[i] = f(s[i * 2], s[i*2 + 1]); as “<<” (”<<s[i*2].first<<","<<s[i*2].second<<") “<<” ("<<s[i*2 + 1].first<<","<<s[i*2 + 1].second<<") “<<” ("<<s[i].first<<","<<s[i].second<<") \n";
s[i] = f(s[i * 2], s[i*2 + 1]);
cout<<“after s[i]: “<<” (”<<s[i].first<<","<<s[i].second<<") \n";
}
}
void update(int pos, T val) {
pos += n;
cout<<“pos: “<<pos<<”\n”;
cout<<“s before values: \n”;
for(auto yk:s)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";
s[pos] = val;
cout<<“s after values: \n”;
for(auto yk:s)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";
for (pos /= 2; pos >= 1; pos /= 2)
{
cout<<“pos: “<<pos<<”\n”;
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
cout<<“s values: \n”;
for(auto yk:s)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";
}
}
T query(int l, int r) { return que(1, l, r, 0, n); }
T que(int pos, int l, int r, int lo, int hi) {
if (r <= lo || hi <= l) return LOW;
if (l <= lo && hi <= r) return s[pos];
int m = (lo + hi) / 2;
return f(que(2 * pos, l, r, lo, m),
que(2 * pos + 1, l, r, m, hi));
}
};
const int inf = 1e9+7;//////////////////ohhhhhhhhhhhhhhhhhh
struct Node {
Node *l = 0, *r = 0;
int lo, hi, madd = 0;
pair<ll,int> val = mp(-inf,-1);
Node(vi& v, int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo)/2;
l = new Node(v, lo, mid); r = new Node(v, mid, hi);
val = max(l->val, r->val);
}
else val = mp(v[lo],lo);
}
pli query(int L, int R) {
if (R <= lo || hi <= L) return mp(-inf,-1);
if (L <= lo && hi <= R) return val;
push();
return max(l->query(L, R), r->query(L, R));
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
madd += x;
val.fst -= x;
}
else {
push(), l->add(L, R, x), r->add(L, R, x);
val = max(l->val, r->val);
}
}
void push() {
if (madd)
l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
}
};
int p[20];///////////////////////////
int maxi(int l,int r){
if(p[l]>p[r]) return l;
else return r;
}
int mini(int l,int r){
if(p[l]<p[r]) return l;
else return r;
}
pii maxi(pii l,pii r){
if(p[l.fst]-p[l.snd]>p[r.fst]-p[r.snd]) return l;
else return r;
}
pii mini(pii l,pii r){
if(p[l.fst]-p[l.snd]<p[r.fst]-p[r.snd]) return l;
else return r;
}
int n;
struct Node2 {
Node2 *l = 0, *r = 0;
int lo, hi, madd = 0;
pii val;
int maxv,minv,lmaxv,lminv,rmaxv,rminv,mx,mn;
Node2(int lo, int hi) : lo(lo), hi(hi) {
cout<<“hiiiiiiiiiiiiiiiiiiiiiii: “<<l<<” “<<r<<”\n”;
cout<<"lo : “<<lo<<” "<<“hi : “<<hi<<”\n”;
if (lo + 1 < hi) {
cout<<"lo+1 : “<<lo+1<<” < "<<“hi : “<<hi<<”\n”;
int mid = lo + (hi - lo)/2;
cout<<“mid: “<<mid<<”\n”;
l = new Node2( lo, mid);
cout<<"l : “<<(l)<<” "<<"lo : “<<lo<<” "<<“hi : “<<hi<<”\n”;
r = new Node2( mid, hi);
cout<<"r : “<<r<<” "<<"lo : “<<lo<<” "<<“hi : “<<hi<<”\n”;

  	val = mp(n,n+1);
  	lmaxv=rmaxv=n;
  	lminv=rminv=n+1;
  	maxv=maxi(l->maxv,r->maxv);
  	minv=mini(l->minv,r->minv);
  	mx=mn=0;
  }
  else {
      cout<<"lo+1 : "<<lo+1<<" >= "<<"hi : "<<hi<<"\n";
  	val = mp(n,n+1);
  	lmaxv=rmaxv=n;
  	lminv=rminv=n+1;
  	maxv=minv=lo;
  	mx=mn=0;
  }

}
pli query(int L, int R) {
if (R <= lo || hi <= L) return mp(n,n+1);
if (L <= lo && hi <= R) return val;
push();
return val;
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
if(x==inf){
val=mp(n,n+1);
lmaxv=rmaxv=maxv=n;
lminv=rminv=minv=n+1;
return;
}
madd += x;
mx+=x,mn+=x;
if(mx<=0){
val = mp(n,n+1);
lmaxv=rmaxv=n;
lminv=rminv=n+1;
}
else if(mn>0){
val=mp(maxv,minv);
lmaxv=rmaxv=maxv;
lminv=rminv=minv;
}
else{
push();
}

  }
  else {
  	if(madd) push();
  	l->add(L,R,x);
  	r->add(L,R,x);
  	push();
  }

}
void push() {
if(madd) l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
val = maxi(maxi(l->val,r->val),maxi(mp(l->rmaxv,r->lminv),mp(r->lmaxv,l->rminv)));
maxv=maxi(l->maxv,r->maxv),minv=mini(l->minv,r->minv);
if(l->mn>0) lmaxv=maxi(l->maxv,r->lmaxv),lminv=mini(l->minv,r->lminv);
else lmaxv=l->lmaxv,lminv=l->lminv;
if(r->mn>0) rmaxv=maxi(r->maxv,l->rmaxv),rminv=mini(r->minv,l->rminv);
else rmaxv=r->rmaxv,rminv=r->rminv;
mx=max(l->mx,r->mx),mn=min(l->mn,r->mn);
}
};
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
cin>>n;
cout<<“n : “<<n<<”\n”;
Tree T(n);

vector v(n);
cout<<“v initial values: \n”;
for(auto yk:v)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";

rep(i,n) cin>>v[i].fst>>v[i].snd;
cout<<“v input values: \n”;
for(auto yk:v)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";

sort(all(v));

cout<<“v sort values: \n”;
for(auto yk:v)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";

vi vals;
int mn = 1234567890;
set lol;
lol.insert({-1,inf-1});
lol.insert({n,-inf-1});

cout<<“lol set initial values: \n”;
for(auto yk:lol)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";

rep (i,n) {
vals.pb(v[i].snd-mn);
cout<<“mn: “<<mn<<”\n”;
cout<<“vals values: \n”;
for(auto yk:vals)
{
cout<<yk<<" “;
}
cout<<”\n";
if(v[i].snd<mn) {
lol.insert({i,v[i].snd});
cout<<“lol set values: \n”;
for(auto yk:lol)
{
cout<<" ("<<yk.first<<","<<yk.second<<") “;
}
cout<<”\n";

  }
  mn=min(mn,v[i].snd);//////
  cout<<"update "<<i<<" "<<"("<<v[i].snd<<" , "<<i<<")\n";
  T.update(i,mp(v[i].snd,i));
  p[i] = v[i].snd;
  cout<<"p array values: \n";
  for(auto yk:p)
  {
      cout<<yk<<" ";
  }
  cout<<"\n";

}

p[n] = -inf,p[n+1]=inf;
cout<<“p array values: \n”;
for(auto yk:p)
{
cout<<yk<<" “;
}
cout<<”\n";
Node2 N2(0,n);
Node N(vals,0,n);
ll ans = 0;
rep(i,n/2){
pli cur = N.query(0,n);
pii z = N2.query(0,n);
if(p[z.fst]-p[z.snd]<=cur.fst){
ans+=cur.fst;
pli cur2 = T.query(0,cur.snd);
N2.add(0,cur.snd,1);
N2.add(cur.snd,cur.snd+1,inf);
N2.add(cur2.snd,cur2.snd+1,inf);
N2.add(0,cur2.snd,-1);
N.add(cur.snd,cur.snd+1,2inf);
N.add(cur2.snd,cur2.snd+1,2
inf);
auto it = lol.lower_bound({cur.snd,p[cur.snd]});
if(it!=lol.end()&&it==mp(cur.snd,p[cur.snd])) {
auto it2 = it;
T.update(cur.snd,{inf+1,cur.snd});
T.update(cur2.snd,{inf+1,cur2.snd});
auto it3 = it;
it2++;it3–;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fstsnd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
it = lol.lower_bound({cur2.snd,-inf});
auto it2 = it;
T.update(cur.snd,{inf+1,cur.snd});
T.update(cur2.snd,{inf+1,cur2.snd});
auto it3 = it;
it2++;it3–;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fstsnd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
else{
N2.add(z.fst,z.fst+1,inf);
N2.add(z.snd,z.snd+1,inf);
N2.add(0,z.fst,1);
N2.add(0,z.snd,-1);
ans+=p[z.fst]-p[z.snd];
N.add(z.fst,z.fst+1,2
inf);
N.add(z.snd,z.snd+1,2*inf);
T.update(z.fst,{inf+1,z.fst});
T.update(z.snd,{inf+1,z.snd});
auto it = lol.lower_bound({z.fst,p[z.fst]});
if(*it==mp(z.fst,p[z.fst])){
auto it2 = it;
auto it3 = it;
it2++;it3–;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fstsnd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
it = lol.lower_bound({z.snd,p[z.snd]});
if(*it==mp(z.snd,p[z.snd])){
auto it2 = it;
auto it3 = it;
it2++;it3–;
int st = it->fst+1,en=it2->fst;
while(st<en){
pli gg = T.query(st,en-1);
if(gg.fstsnd){
N.add(gg.snd+1,en,gg.fst-it->snd);
lol.insert({gg.snd,gg.fst});
en = gg.snd+1;
}
else{
N.add(st,en,it3->snd-it->snd);
en=st;
}
}
lol.erase(it);
}
}
cout<<ans<<’\n’;
}
return 0;
}

1 Like

Reading the code is literally the worst way to understand an editorial. Code examples are plain useless. Your best bet here is to fully understand that editorial.

3 Likes

Go step by step

  1. Understand the problem . Divide it into parts.
    Try to reach as far as u can.
  2. Now read editorial and try to implement each part on your own .
  3. First read all comments and approaches in editorial of the problem and understand the idea
    4 Whenever u stuck at some point try to search problems related to concept. If still stuck u can ask here .
  4. U need to implement on ur own each part.
    And remember a hard problem always teaches much more than many easy problems.
    Good luck
2 Likes

But after understanding editorial, we have to code it, and should understand how that code implements the idea explained in editorial.
Bro, you must have gone through that phase when you were a beginner, how did you tackle this?

1 Like

If you manage to understand the editorial fully you can quite implement the solution yourself. Reading the authour’s code is probably gonna do nothing but give you an eye-ache here.

I only took a scroll through and what’s with the mess of gmx functions.

3 Likes