Questions That Don't Deserve Their Own Blog — I guess it'd be good to have something like this as a place to ask random questions about problems ("I accidentally my code, wat do?") without having your blog post get downvotebombed?↵
↵
<spoiler summary="old question">↵
I have a question about [Yandex.Algorithm 2015 round 2.2E](https://contest.yandex.ru/algorithm2015/contest/1299/problems/E/): the problem can be reduced to computing the min. bipartite vertex cover _that can't fully cover one side_ and since the dual of min. vertex cover is max. matching, I tried to find the dual of this problem.↵
↵
↵
↵
I mean, that vertex cover can be described as a linear programming problem ↵
↵
- $\mathrm{min}\sum_{i=1}^{N+M} x_i$↵
- $x_i \ge 0$↵
- $x_{u_j}+x_{v_j} \ge 1$ for each edge $e_j=(u_j-v_j), 1 \le j \le E$↵
- $\sum_{i=1}^N -x_i \ge -(N-1), \sum_{i=N+1}^{N+M} -x_i \ge -(M-1)$↵
↵
Its dual should be↵
↵
- $\mathrm{max} \sum_{j=1}^E y_j - (N-1) y_\mathrm{L} - (M-1) y_\mathrm{R}$↵
- $y_j,y_\mathrm{L},y_\mathrm{R} \ge 0$↵
- for $1 \le i \le N$, $\sum_{j: u_j=i} y_j \le 1+y_\mathrm{L}$ (sum over edges incident on vertex $i$ in the left part)↵
- for $N+1 \le i \le N+M$, $\sum_{j: v_j=i} y_j \le 1+y_\mathrm{R}$ (same as above for the right part)↵
↵
$y_j$ are variables assigned to edges (flow through them); $y_\mathrm{L},y_\mathrm{R}$ are assigned to the left and right part of the graph and if they're fixed, finding the optimal $y_j$ is just bipartite matching/flow. However, this gives the optimal solution as $y_\mathrm{L}=y_\mathrm{R}=0$ for example for an almost complete bipartite graph $K_{N,N}$ that's missing just one edge, which doesn't make sense.↵
↵
What am I missing here?↵
</spoiler>↵
↵
Next: I was upsolving DCJ problems during the second practice round (which ended yesterday). The only non-final problem I didn't manage to solve in time was highest_mountain and only because it gives me weird RE.↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include "highest_mountain.h"↵
// iostream is too mainstream↵
#include <cstdio>↵
// bitch please↵
#include <iostream>↵
#include <algorithm>↵
#include <cstdlib>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <queue>↵
#include <stack>↵
#include <list>↵
#include <cmath>↵
#include <iomanip>↵
#include <time.h>↵
#include <message.h>↵
#include <stdio.h>↵
#define dibs reserve↵
#define OVER9000 1234567890↵
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)↵
#define tisic 47↵
#define soclose 1e-8↵
#define chocolate win↵
// so much chocolate↵
#define patkan 9↵
#define ff first↵
#define ss second↵
#define abs(x) ((x < 0)?-(x):x)↵
#define uint unsigned int↵
#define dbl long double↵
#define pi 3.14159265358979323846↵
using namespace std;↵
// mylittledoge↵
↵
typedef long long cat;↵
↵
#ifdef DONLINE_JUDGE↵
// palindromic tree is better than splay tree!↵
#define lld I64d↵
#endif↵
↵
#define MASTER_NODE 0↵
↵
int main() {↵
cin.sync_with_stdio(0);↵
cin.tie(0);↵
cout << fixed << setprecision(10);↵
int nodes =NumberOfNodes(), my_id =MyNodeId();↵
int N =NumberOfPeaks();↵
↵
vector<int> ilen(nodes,N/nodes);↵
for(int i =0; i < N%nodes; i++) ilen[i]++;↵
int L =0, R =0;↵
for(int i =0; i < my_id; i++) L +=ilen[i];↵
for(int i =0; i <= my_id; i++) R +=ilen[i];↵
↵
vector< pair<cat,int> > H;↵
H.dibs(R-L);↵
for(int i =L; i < R; i++) {↵
cat h =GetHeight(i);↵
int s =H.size();↵
while(s >= 2 && (H[s-1].ff-h)*(H[s-2].ss-i) > (H[s-2].ff-h)*(H[s-1].ss-i)) {↵
H.pop_back();↵
s--;}↵
H.push_back(make_pair(h,i));}↵
int Hs =H.size();↵
↵
vector<int> comp1;↵
int K =2000;↵
for(int i =0; i < Hs; i +=K) comp1.push_back(H[i].ss);↵
if(Hs > 0 && comp1.back() != H[Hs-1].ss) comp1.push_back(H[Hs-1].ss);↵
PutInt(MASTER_NODE,comp1.size());↵
ALL_THE(comp1,it) PutInt(MASTER_NODE,*it);↵
Send(MASTER_NODE);↵
↵
if(my_id == MASTER_NODE) {↵
vector< pair<cat,int> > Hcomp;↵
Hcomp.dibs(nodes*2000);↵
vector< pair<int,int> > I(nodes,make_pair(N+1,-1));↵
vector< pair<int,int> > I2(nodes,make_pair(N+1,-1));↵
vector< vector<int> > V(nodes);↵
for(int i =0; i < nodes; i++) {↵
Receive(i);↵
int l =GetInt(i);↵
V[i].resize(l);↵
for(int j =0; j < l; j++) {↵
V[i][j] =GetInt(i);↵
I[i].ff =min(I[i].ff,V[i][j]);↵
I[i].ss =max(I[i].ss,V[i][j]);}↵
}↵
for(int i =0; i < nodes; i++) {↵
for(int j =0; j < (int)V[i].size(); j++) {↵
int a =V[i][j];↵
cat h =GetHeight(a);↵
int s =Hcomp.size();↵
while(s >= 2 && (Hcomp[s-1].ff-h)*(Hcomp[s-2].ss-a) > (Hcomp[s-2].ff-h)*(Hcomp[s-1].ss-a)) {↵
Hcomp.pop_back();↵
s--;}↵
Hcomp.push_back(make_pair(h,a));}↵
for(int j =(int)Hcomp.size()-1; j >= 0; j--) {↵
if(Hcomp[j].ss < I[i].ff) break;↵
I2[i].ff =Hcomp[j].ss;}↵
}↵
Hcomp.clear();↵
for(int i =nodes-1; i >= 0; i--) {↵
for(int j =(int)V[i].size()-1; j >= 0; j--) {↵
int a =V[i][j];↵
cat h =GetHeight(a);↵
int s =Hcomp.size();↵
while(s >= 2 && (Hcomp[s-1].ff-h)*(Hcomp[s-2].ss-a) < (Hcomp[s-2].ff-h)*(Hcomp[s-1].ss-a)) {↵
Hcomp.pop_back();↵
s--;}↵
Hcomp.push_back(make_pair(h,a));}↵
for(int j =(int)Hcomp.size()-1; j >= 0; j--) {↵
if(Hcomp[j].ss > I[i].ss) break;↵
I2[i].ss =Hcomp[j].ss;}↵
}↵
for(int i =0; i < nodes; i++) {↵
PutInt(i,I2[i].ff);↵
PutInt(i,I2[i].ss);↵
Send(i);}↵
}↵
↵
Receive(MASTER_NODE);↵
int mi =GetInt(MASTER_NODE);↵
int mx =GetInt(MASTER_NODE);↵
int l =0, r =Hs-1;↵
while(l < Hs && H[l].ss < mi) l++;↵
while(r >= 0 && H[r].ss > mx) r--;↵
vector<int> comp2l,comp2r;↵
for(int i =max(0,l-K); i <= min(Hs-1,r+K); i++) {↵
if(i <= l+K) comp2l.push_back(H[i].ss);↵
if(i >= r-K) comp2r.push_back(H[i].ss);↵
}↵
for(int i =0; i < my_id; i++) {↵
PutInt(i,comp2l.size());↵
ALL_THE(comp2l,it) PutInt(i,*it);↵
Send(i);}↵
for(int i =my_id+1; i < nodes; i++) {↵
PutInt(i,comp2r.size());↵
ALL_THE(comp2r,it) PutInt(i,*it);↵
Send(i);}↵
↵
vector<int> Pi;↵
Pi.dibs(Hs+nodes*5000);↵
vector< pair<cat,int> > Hi;↵
Hi.dibs(Hs+nodes*5000);↵
for(int i =0; i < nodes; i++) {↵
if(i == my_id) ALL_THE(H,it) Pi.push_back(it->ss);↵
else {↵
Receive(i);↵
l =GetInt(i);↵
for(int j =0; j < l; j++) Pi.push_back(GetInt(i));↵
}↵
}↵
ALL_THE(Pi,it) {↵
int a =*it;↵
cat h =GetHeight(a);↵
int s =Hi.size();↵
while(s >= 2 && (Hi[s-1].ff-h)*(Hi[s-2].ss-a) > (Hi[s-2].ff-h)*(Hi[s-1].ss-a)) {↵
Hi.pop_back();↵
s--;}↵
Hi.push_back(make_pair(h,a));}↵
int inH =0;↵
ALL_THE(Hi,it) if(it->ss >= L && it->ss < R) inH++;↵
PutInt(MASTER_NODE,inH);↵
Send(MASTER_NODE);↵
↵
if(my_id == MASTER_NODE) {↵
int ans =0;↵
for(int i =0; i < nodes; i++) {↵
Receive(i);↵
ans +=GetInt(i);}↵
cout << ans << "\n";}↵
}↵
↵
// look at my code↵
// my code is amazing↵
~~~~~↵
</spoiler>↵
↵
I'm merging $O(nodes)$ small convex hulls of size $O(N/nodes)$ by sending only every $K$-th point in each hull, merging them in master and sending back the range that remains in the merged convex hull; then, each node sends just the smallest $O(N/nodes/K)$ leftmost or rightmost points of this range to each other node and each node recomputes the convex hull of its own $O(N/nodes)$ points plus all $O(N/K)$ points it got sent.↵
↵
I proved that this is correct and it passes the small subproblem (with $K=10,nodes=10,N=1000$), while slightly incorrect implementations don't, so it really should be correct. I also verified that it passes at least one official maxtest, but gives RE later.↵
↵
The cause of RE should not be too much stuff sent, since each node sends/receives only $O(N/K)$ of data (numerically 2-3 MB, I tried "if this array is too large then return 0" checks and it changed nothing too). The memory limit shouldn't be exceeded too.↵
↵
Any ideas? Btw don't forget about GCJ/DCJ last online rounds this weekend.
↵
<spoiler summary="old question">↵
I have a question about [Yandex.Algorithm 2015 round 2.2E](https://contest.yandex.ru/algorithm2015/contest/1299/problems/E/): the problem can be reduced to computing the min. bipartite vertex cover _that can't fully cover one side_ and since the dual of min. vertex cover is max. matching, I tried to find the dual of this problem.↵
↵
↵
↵
I mean, that vertex cover can be described as a linear programming problem ↵
↵
- $\mathrm{min}\sum_{i=1}^{N+M} x_i$↵
- $x_i \ge 0$↵
- $x_{u_j}+x_{v_j} \ge 1$ for each edge $e_j=(u_j-v_j), 1 \le j \le E$↵
- $\sum_{i=1}^N -x_i \ge -(N-1), \sum_{i=N+1}^{N+M} -x_i \ge -(M-1)$↵
↵
Its dual should be↵
↵
- $\mathrm{max} \sum_{j=1}^E y_j - (N-1) y_\mathrm{L} - (M-1) y_\mathrm{R}$↵
- $y_j,y_\mathrm{L},y_\mathrm{R} \ge 0$↵
- for $1 \le i \le N$, $\sum_{j: u_j=i} y_j \le 1+y_\mathrm{L}$ (sum over edges incident on vertex $i$ in the left part)↵
- for $N+1 \le i \le N+M$, $\sum_{j: v_j=i} y_j \le 1+y_\mathrm{R}$ (same as above for the right part)↵
↵
$y_j$ are variables assigned to edges (flow through them); $y_\mathrm{L},y_\mathrm{R}$ are assigned to the left and right part of the graph and if they're fixed, finding the optimal $y_j$ is just bipartite matching/flow. However, this gives the optimal solution as $y_\mathrm{L}=y_\mathrm{R}=0$ for example for an almost complete bipartite graph $K_{N,N}$ that's missing just one edge, which doesn't make sense.↵
↵
What am I missing here?↵
</spoiler>↵
↵
Next: I was upsolving DCJ problems during the second practice round (which ended yesterday). The only non-final problem I didn't manage to solve in time was highest_mountain and only because it gives me weird RE.↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include "highest_mountain.h"↵
// iostream is too mainstream↵
#include <cstdio>↵
// bitch please↵
#include <iostream>↵
#include <algorithm>↵
#include <cstdlib>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <queue>↵
#include <stack>↵
#include <list>↵
#include <cmath>↵
#include <iomanip>↵
#include <time.h>↵
#include <message.h>↵
#include <stdio.h>↵
#define dibs reserve↵
#define OVER9000 1234567890↵
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)↵
#define tisic 47↵
#define soclose 1e-8↵
#define chocolate win↵
// so much chocolate↵
#define patkan 9↵
#define ff first↵
#define ss second↵
#define abs(x) ((x < 0)?-(x):x)↵
#define uint unsigned int↵
#define dbl long double↵
#define pi 3.14159265358979323846↵
using namespace std;↵
// mylittledoge↵
↵
typedef long long cat;↵
↵
#ifdef DONLINE_JUDGE↵
// palindromic tree is better than splay tree!↵
#define lld I64d↵
#endif↵
↵
#define MASTER_NODE 0↵
↵
int main() {↵
cin.sync_with_stdio(0);↵
cin.tie(0);↵
cout << fixed << setprecision(10);↵
int nodes =NumberOfNodes(), my_id =MyNodeId();↵
int N =NumberOfPeaks();↵
↵
vector<int> ilen(nodes,N/nodes);↵
for(int i =0; i < N%nodes; i++) ilen[i]++;↵
int L =0, R =0;↵
for(int i =0; i < my_id; i++) L +=ilen[i];↵
for(int i =0; i <= my_id; i++) R +=ilen[i];↵
↵
vector< pair<cat,int> > H;↵
H.dibs(R-L);↵
for(int i =L; i < R; i++) {↵
cat h =GetHeight(i);↵
int s =H.size();↵
while(s >= 2 && (H[s-1].ff-h)*(H[s-2].ss-i) > (H[s-2].ff-h)*(H[s-1].ss-i)) {↵
H.pop_back();↵
s--;}↵
H.push_back(make_pair(h,i));}↵
int Hs =H.size();↵
↵
vector<int> comp1;↵
int K =2000;↵
for(int i =0; i < Hs; i +=K) comp1.push_back(H[i].ss);↵
if(Hs > 0 && comp1.back() != H[Hs-1].ss) comp1.push_back(H[Hs-1].ss);↵
PutInt(MASTER_NODE,comp1.size());↵
ALL_THE(comp1,it) PutInt(MASTER_NODE,*it);↵
Send(MASTER_NODE);↵
↵
if(my_id == MASTER_NODE) {↵
vector< pair<cat,int> > Hcomp;↵
Hcomp.dibs(nodes*2000);↵
vector< pair<int,int> > I(nodes,make_pair(N+1,-1));↵
vector< pair<int,int> > I2(nodes,make_pair(N+1,-1));↵
vector< vector<int> > V(nodes);↵
for(int i =0; i < nodes; i++) {↵
Receive(i);↵
int l =GetInt(i);↵
V[i].resize(l);↵
for(int j =0; j < l; j++) {↵
V[i][j] =GetInt(i);↵
I[i].ff =min(I[i].ff,V[i][j]);↵
I[i].ss =max(I[i].ss,V[i][j]);}↵
}↵
for(int i =0; i < nodes; i++) {↵
for(int j =0; j < (int)V[i].size(); j++) {↵
int a =V[i][j];↵
cat h =GetHeight(a);↵
int s =Hcomp.size();↵
while(s >= 2 && (Hcomp[s-1].ff-h)*(Hcomp[s-2].ss-a) > (Hcomp[s-2].ff-h)*(Hcomp[s-1].ss-a)) {↵
Hcomp.pop_back();↵
s--;}↵
Hcomp.push_back(make_pair(h,a));}↵
for(int j =(int)Hcomp.size()-1; j >= 0; j--) {↵
if(Hcomp[j].ss < I[i].ff) break;↵
I2[i].ff =Hcomp[j].ss;}↵
}↵
Hcomp.clear();↵
for(int i =nodes-1; i >= 0; i--) {↵
for(int j =(int)V[i].size()-1; j >= 0; j--) {↵
int a =V[i][j];↵
cat h =GetHeight(a);↵
int s =Hcomp.size();↵
while(s >= 2 && (Hcomp[s-1].ff-h)*(Hcomp[s-2].ss-a) < (Hcomp[s-2].ff-h)*(Hcomp[s-1].ss-a)) {↵
Hcomp.pop_back();↵
s--;}↵
Hcomp.push_back(make_pair(h,a));}↵
for(int j =(int)Hcomp.size()-1; j >= 0; j--) {↵
if(Hcomp[j].ss > I[i].ss) break;↵
I2[i].ss =Hcomp[j].ss;}↵
}↵
for(int i =0; i < nodes; i++) {↵
PutInt(i,I2[i].ff);↵
PutInt(i,I2[i].ss);↵
Send(i);}↵
}↵
↵
Receive(MASTER_NODE);↵
int mi =GetInt(MASTER_NODE);↵
int mx =GetInt(MASTER_NODE);↵
int l =0, r =Hs-1;↵
while(l < Hs && H[l].ss < mi) l++;↵
while(r >= 0 && H[r].ss > mx) r--;↵
vector<int> comp2l,comp2r;↵
for(int i =max(0,l-K); i <= min(Hs-1,r+K); i++) {↵
if(i <= l+K) comp2l.push_back(H[i].ss);↵
if(i >= r-K) comp2r.push_back(H[i].ss);↵
}↵
for(int i =0; i < my_id; i++) {↵
PutInt(i,comp2l.size());↵
ALL_THE(comp2l,it) PutInt(i,*it);↵
Send(i);}↵
for(int i =my_id+1; i < nodes; i++) {↵
PutInt(i,comp2r.size());↵
ALL_THE(comp2r,it) PutInt(i,*it);↵
Send(i);}↵
↵
vector<int> Pi;↵
Pi.dibs(Hs+nodes*5000);↵
vector< pair<cat,int> > Hi;↵
Hi.dibs(Hs+nodes*5000);↵
for(int i =0; i < nodes; i++) {↵
if(i == my_id) ALL_THE(H,it) Pi.push_back(it->ss);↵
else {↵
Receive(i);↵
l =GetInt(i);↵
for(int j =0; j < l; j++) Pi.push_back(GetInt(i));↵
}↵
}↵
ALL_THE(Pi,it) {↵
int a =*it;↵
cat h =GetHeight(a);↵
int s =Hi.size();↵
while(s >= 2 && (Hi[s-1].ff-h)*(Hi[s-2].ss-a) > (Hi[s-2].ff-h)*(Hi[s-1].ss-a)) {↵
Hi.pop_back();↵
s--;}↵
Hi.push_back(make_pair(h,a));}↵
int inH =0;↵
ALL_THE(Hi,it) if(it->ss >= L && it->ss < R) inH++;↵
PutInt(MASTER_NODE,inH);↵
Send(MASTER_NODE);↵
↵
if(my_id == MASTER_NODE) {↵
int ans =0;↵
for(int i =0; i < nodes; i++) {↵
Receive(i);↵
ans +=GetInt(i);}↵
cout << ans << "\n";}↵
}↵
↵
// look at my code↵
// my code is amazing↵
~~~~~↵
</spoiler>↵
↵
I'm merging $O(nodes)$ small convex hulls of size $O(N/nodes)$ by sending only every $K$-th point in each hull, merging them in master and sending back the range that remains in the merged convex hull; then, each node sends just the smallest $O(N/nodes/K)$ leftmost or rightmost points of this range to each other node and each node recomputes the convex hull of its own $O(N/nodes)$ points plus all $O(N/K)$ points it got sent.↵
↵
I proved that this is correct and it passes the small subproblem (with $K=10,nodes=10,N=1000$), while slightly incorrect implementations don't, so it really should be correct. I also verified that it passes at least one official maxtest, but gives RE later.↵
↵
The cause of RE should not be too much stuff sent, since each node sends/receives only $O(N/K)$ of data (numerically 2-3 MB, I tried "if this array is too large then return 0" checks and it changed nothing too). The memory limit shouldn't be exceeded too.↵
↵
Any ideas? Btw don't forget about GCJ/DCJ last online rounds this weekend.
