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,2inf);
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,2inf);
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;
}