The difficulty level is quite high, ig
1 Like
Would you please help me with first two questions ??
Please give the code anyone …
Your shameless is amazing!
7 Likes
lol
I am myself not clearing it. Can’t debug my code of A2. Now time is gone.
1 Like
Nop, but what in fact you can find is a well deserved account ban for asking the code of an ongoing contest
1 Like
Would you share your approach for A2? It did by making pairs and everytime a new room came I tried to adjust it between the pairs but couldn’t debug it and secondly time complexity of my code was also high.
The round was tougher of what I expected
Ya. I also felt it quite tough and I started late thinking I would clear cut off in time but Alas!
I used a disjoint-interval structure to keep updated the intervals. If the border of the new interval is inside an existing interval so don’t add its lenght.
By sure there will be several well wrinten editorials. If after reading probably better approaches you still want the details of mine I can try to explain it.
1 Like
Thanks! 
can you please ?
which data structure you were using and how was the update process working can you explain please I am focusing from 5 hours to understand that please write a nice tutorial for it!
I initially thought that my complexity for A2 was also high, but two nested loops don’t always mean n^2. The way I understood is, I insert each range in my set once, and erase it once. So even with nested loops it ran in under 2 seconds.
However the output was wrong for the final tests 
. So I’m not going to round 2.
1 Like
Sorry, don’t have the time to do that.
What I used is disjoint-interval structure. I don’t remember where I read about it but it’s pretty simple. The idea is to store intervals as pairs<int,int> using a set. The insertion of new intervals fuses the intervals that collide.
disjoint-intervals
struct disjoint_intervals {
set<pair<int,int>> segs;
void insert(pair<int,int> s) {
if(s.second - s.first == 0) return;
set<pair<int,int>>::iterator it, at;
at = it = segs.lower_bound(s);
if(at != segs.begin() && (--at)->second >= s.first)
s.first = at->first, --it;
for(; it != segs.end() && it->first <= s.second; segs.erase(it++))
s.second = max(s.second, it->second);
segs.insert(s);
}
};
To solve the chapter 2 of the fbk problem you need the add the perimeter while updating the intervals (bounches of “ifs” everywhere). My implementation of the solution is no clean and by sure there are much simpler approaches. It looks like this
Solution code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const ui MOD = 1E9 + 7;
#define FOR(i,n) for (int i=0;i<(n);++i)
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
void READ(bool _local){
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _DEBUG
if (_local) {
string filename = "perimetric_chapter_2_input";
freopen(string(filename + ".txt").c_str(), "r", stdin);
freopen(string(filename + ".out").c_str(), "w", stdout);
}
#endif
}
ll AL[4],AH[4],AW[4],pr;
vector<ll> L,H,W;
int n,k;
void upd(int i){
int i2 = (i>1?i-2:i+k-2);
int i1 = (i>0?i-1:i+k-1);
L[i] = (AL[0] * L[i2] % AL[3] + AL[1] * L[i1] % AL[3] + AL[2])%AL[3] + 1;
H[i] = (AH[0] * H[i2] % AH[3] + AH[1] * H[i1] % AH[3] + AH[2])%AH[3] + 1;
W[i] = (AW[0] * W[i2] % AW[3] + AW[1] * W[i1] % AW[3] + AW[2])%AW[3] + 1;
}
struct cmp {
bool operator()(const ii &a, const ii &b) { return a.first < b.first; }
};
struct disjoint_intervals {
set<ii,cmp> segs;
void insert(ii s,int h) {
set<ii>::iterator it, at;
at = it = segs.lower_bound(s);
ii s0=s;
if (it!=segs.end() && it->first==s.first){
if (it->second>=s.second) return;
pr -= (h + 2LL*(it->second-it->first))%MOD;
if (pr<0) pr += MOD;
it=segs.erase(it);
}else{
if(at != segs.begin() && (--at)->second >= s.first) {
if (at->second>=s.second) return;
s.first = at->first;
pr -= (2LL*(at->second-s0.first)+h)%MOD;
if (pr<0) pr += MOD;
it=segs.erase(--it);
}else if (it==segs.end() || it->first > s.first){
pr += h;
if (pr>=MOD) pr -= MOD;
}
}
pr += (2LL *(s0.second-s0.first) + h) %MOD;
if (pr>=MOD) pr -= MOD;
for (; it != segs.end() && it->first <= s0.second; segs.erase(it++)) {
pr -= 2LL * ((it->second - it->first) + h) %MOD;
if (pr < 0) pr += MOD;
s.second = max(s.second, it->second);
}
segs.insert(s);
pr %= MOD;
if (pr<0) pr += MOD;
}
};
void docase(){
cin>>n>>k;
L.resize(k),H.resize(k),W.resize(k);
FOR(i,k) cin>>L[i];
FOR(i,4) cin>>AL[i];
FOR(i,k) cin>>W[i];
FOR(i,4) cin>>AW[i];
FOR(i,k) cin>>H[i];
FOR(i,4) cin>>AH[i];
disjoint_intervals dj;
pr= 0;
ll ret = 1;
for(int i=0;i<n;++i){
int j=i%k;
dj.insert(ii(L[j],L[j]+W[j]),H[j]);
ret = ret * pr % MOD;
upd(j);
}
cout << ret << '\n';
}
int main() {
READ(1);
int T;cin>>T;
for(int tt=1;tt<=T;++tt){
cout << "Case #" << tt << ": ";
docase();
}
return 0;
}
1 Like
The contest was quite tough.
My approach was similar to the solution. I dont know where I went wrong. Please anyone help me to debug this solution.
Same here too.
Disjoint interval seems pretty interesting man