PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Author: Alei Reyes
Tester: Felipe Mota
DIFFICULTY:
Tie-break
PREREQUISITES:
Triangulations
PROBLEM:
You are given the Delaunay triangulation of a set of N points, which consists of M triangles.
You are allowed to perform at most 1024 flips and then remove exactly M-R edges. Let A_1,...,A_R be the areas of the resulting regions after performing the operations. You are given the desired areas of those regions B_1, ..., B_R.
The goal is to perform the operations to minimize \sum_{i=1}^R |A_i - B_i|.
EXPLANATION:
To keep the information of the triangulation, let’s use a map that for each diagonal (u,v) stores the vertices x such that the triangle uvx is a face in the triangulation. Note that for each entry (u,v) in the map there can be at most two triangles that share the diagonal (u,v), let’s call them uvx and uvy. The edge (u,v) can be flipped iff the quadrialteral uxvy is convex.
After removing edges, two regions should be connected, we can use DSU to keep such regions. At the end of the removals the area of each region is the sum of the triangles it is composed.
One of the most simple solutions just randomly flips and removes valid edges, it gets a score of ~16 points.
The triangulation can be represented as a planar graph, and the regions after removals are subgraphs, we can generate the subgraphs in decreasing order of area, using something like knapsack (or other heuristics).
The flips makes it harder, is possible to use some kind of random search or simulated annealing with a heuristic that quickly calculates the partition in subgraphs after each flip. Another idea is to not start from a triangulation, but just from the points. Construct the polygons choosing some of the points, then triangulate the polygons, and reach it with flips from the delaunay.
Some of the top scorers kindly described their approaches. In their own words:
Pranav Rajagopalan (@explodingfrz) Solution, second in div1!
The core part of my idea relies on the fact that because the flips and removals are uniform randomly chosen and are somewhat less than the number of regions, its highly likely the resulting components will be small.
Furthermore its likely that the number of regions that are just a single triangle is pretty high.
We can make one more critical observation, which is that since the areas are extremely large, the chances of two regions with the same area is extremely low (1-2 such regions out of a thousand). But still to be safe, when I say “area is needed” I mean that the area exists in b exactly once.
So I first flip the diagonal of a convex quadrilateral iff either the area of one of the resulting triangles or the area of one of the resulting triangles and one of its neighbours is needed.
After these flips I use a number of heuristics to eliminate as many regions as possible, these are:
- Individual triangles
- A triangle and 1-3 triangles adjacent to it.
- A path of triangles of length 4.
It might be worth noting that these triangles are effectively vertices of a graph with the diagonals being edges.
Now we claim that the number of remaining vertices and connected components are small (and due to the uniform random flipping, they usually are).
So I just dfs, check if the area of an entire component is needed, if so eliminate it.
If it isn’t, then try all possible divisions into submasks to eliminate as many possible (with a limitation of the size of the component to prevent taking up valuable time).
Now we have a mostly matched sequence.
So I just try different ways of randomly merging remaining diagonals (with higher priority to ones between uneliminated triangles) for as much time as possible.
Some heuristics help here as well, like sorting the diagonals in decreasing order of resulting region size, and randomly swapping a few elements in each run.
Also it helps to “bound” the area of a merge. Like if after merging it will be the k-th largest component, ensure it is no more than c * (k-th largest b), for some constant c. I found that randomly deciding between c = 1 and c = 2 worked best, though maybe chosing a random real value in the range might have worked better.
Alvaro Carrera (@carre) Solution, 4th in div1
- Define time T1 to be approx 0.95 of time limit
- While running time is less than T1:
2.1. take the initial triangulation and erase M-R edges. The edges to be erased are chosen at random but avoiding creating a region with area greater than the maximum area B[R] (here I tried some minor detail of updating which B[i] is considered but did’t show any relevant difference)
2.2. Match the areas of the R regions obtained with the areas of the B[i] in order to evaluate the cost of the solution
2.3. Scan all the edges following a random order and, in case that edge can be flipped, perform the flip if this operation reduces the total cost (when performing the flip, new edges can be created that can be flipped but are not taken into account in tis scan)
2.4. Evaluate the cost of the solution and save it if it is the best obtained so far - Finally, for the best solution obtained, repeat step 2.3 while running time is less than time limit
Almost all procedures and data structures used where obtained from the “generator.cpp” 
Masahiro Inoue (@physics0523) Solution, 6th in Div 1
My improvement is very simple. Just use B_i like a kind of hash.
The number of removed edges is small, so there are a lot of triangle pieces, maybe. So, when I do some operations, if there are some pieces which has some areas which is exist in B, then, the operation should be evaluated better.
ABOUT CUTCAKE
The initial problem was about cutting a rectangular cake with slices (lines) that connects points from the perimeter of the rectangle. Alexey suggested to use integer coordinates to have an integer score, however I had troubles finding a good test plan generation. Then I came up with the idea of creating the portions by connecting points in a plane, the easiest way I though for generating test data was using triangulations.
(Unfortunately?) I used very small constraints N \leq 1024 that allowed @rns_cus to solve it optimally! after his submission, the relative score of all the other contestants became 0/S, and rns_cus got an undetermined relative score 0/0. So we decided to tweak a bit the scoring formula to eliminate indeterminant.
SOLUTIONS:
Basic solution, random flips and deletions
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct pt {
ll x, y;
pt() { }
pt(ll _x, ll _y) : x(_x), y(_y) { }
pt operator - (const pt& p) const {
return pt(x - p.x, y - p.y);
}
ll cross(const pt& p) const {
return x * p.y - y * p.x;
}
ll cross(const pt& a, const pt& b) const {
return (a - *this).cross(b - *this);
}
ll dot(const pt& p) const {
return x * p.x + y * p.y;
}
ll dot(const pt& a, const pt& b) const {
return (a - *this).dot(b - *this);
}
ll sqrLength() const {
return this->dot(*this);
}
bool operator == (const pt& p) const {
return x == p.x && y == p.y;
}
bool operator < (const pt& p) const{
if(x != p.x) return x < p.x;
return y <p.y;
}
};
bool ccw(pt a,pt b,pt c){
return ((b-a).cross(c-b))>0;
}
bool convex(pt a,pt b,pt c,pt d){
return (
(ccw(a,b,c) && ccw(b,c,d) && ccw(c,d,a) && ccw(d,a,b)) ||
(ccw(a,d,c) && ccw(d,c,b) && ccw(c,b,a) && ccw(b,a,d))
);
}
pair<int,int> makeEdge(int u, int v){
return {min(u,v), max(u,v)};
}
void replaceDiagonal(map<pair<int,int>, set<int> >&mp, int u, int v, int x, int y){
auto e = makeEdge(u, v);
assert(mp[e].count(x));
mp[e].erase(x);
mp[e].insert(y);
assert(mp[e].size() <= 2);
}
vector<int> parent;
int gp(int u){ return (u == parent[u] ? u : parent[u] = gp(parent[u])); }
string itos(int v){
if(v==0)return "0";
string ans="";
for(;v!=0;v/=10)ans=string(1,'0'+(v%10))+ans;
return ans;
}
char lastReadChar='?';
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
lastReadChar=ch;
if(nxt!='?')assert(ch==nxt);
break;
}
}
return v*sgn;
}
const int mxc = 1e5;
void solve(){
int n = rint(' ');
assert(n == 1024);
int m = rint(' ');
int r = rint('\n');
vector<pt>points(n);
for(int i = 0; i < n; i++){
points[i].x = rint(' ');
points[i].y = rint('\n');
assert(0 <= points[i].x && points[i].x < mxc);
assert(0 <= points[i].y && points[i].y < mxc);
}
map<pair<int,int>, set<int> > mp;
for(int it = 0; it < m; it++){
int i = rint(' ');
int j = rint(' ');
int k = rint('\n');
assert(1 <= i && i <= n);
assert(1 <= j && j <= n);
assert(1 <= k && k <= n);
--i, --j, --k;
mp[makeEdge(i,j)].insert(k);
mp[makeEdge(j,k)].insert(i);
mp[makeEdge(k,i)].insert(j);
assert(mp[makeEdge(i,j)].size() <= 2);
assert(mp[makeEdge(j,k)].size() <= 2);
assert(mp[makeEdge(k,i)].size() <= 2);
}
vector<int> b(r);
for(int i = 0; i< r; i++)
b[i] = rint(i == r-1 ? '\n' : ' ');
for(int i = 1; i < r; i++)assert(b[i] >= b[i-1]);
vector<pair<int,int> > diagonals;
diagonals.clear();
for(auto p : mp)
if(p.second.size() == 2)
diagonals.push_back(p.first);
vector<pair<int,int> > flips;
random_shuffle(diagonals.begin(), diagonals.end());
for(int i = 0; i < int(diagonals.size()) && flips.size() < 1024; i++){
auto diag = diagonals[i];
int x = diag.first;
int y = diag.second;
if(mp[diag].size() != 2) continue;
int s = *mp[diag].begin();
int t = *mp[diag].rbegin();
if(!convex(points[s], points[x] , points[t], points[y])) continue;
mp.erase(diag);
mp[makeEdge(s,t)] = {x,y};
replaceDiagonal(mp, x, s, y, t);
replaceDiagonal(mp, s, y, x, t);
replaceDiagonal(mp, y, t, x, s);
replaceDiagonal(mp, t, x, y, s);
flips.push_back({x, y});
}
cerr<<"flips size = "<<flips.size()<<endl;
diagonals.clear();
vector<vector<int> >striangles;
for(auto p : mp){
if(p.second.size() == 2)
diagonals.push_back(p.first);
int x = p.first.first;
int y = p.first.second;
for(int z : p.second){
vector<int> tri = {x, y, z};
sort(tri.begin(), tri.end());
striangles.push_back(tri);
}
}
sort(striangles.begin(), striangles.end());
int nt = unique(striangles.begin(), striangles.end()) - striangles.begin();
striangles.resize(nt);
parent.resize(nt);
iota(parent.begin(), parent.end(), 0);
vector<pair<int,int> >removals;
random_shuffle(diagonals.begin(), diagonals.end());
for(int it = 0; it < diagonals.size() && removals.size() < m-r; it++){
int i = diagonals[it].first;
int j = diagonals[it].second;
int k = *mp[diagonals[it]].begin();
int l = *mp[diagonals[it]].rbegin();
vector<int>t1 = {i, j, k};
sort(t1.begin(), t1.end());
vector<int>t2 = {i, j, l};
sort(t2.begin(), t2.end());
int u = lower_bound(striangles.begin(),striangles.end(), t1) - striangles.begin();
int v = lower_bound(striangles.begin(),striangles.end(), t2) - striangles.begin();
if(gp(u)==gp(v)){
continue;
}
parent[gp(u)] = gp(v);
removals.push_back({i, j});
}
map<int,int> areas;
for(int i = 0; i < nt; i++){
int pi = gp(i);
int x = striangles[i][0];
int y = striangles[i][1];
int z = striangles[i][2];
ll area = (points[y] - points[x]).cross(points[z] - points[x]);
if(area < 0) area = -area;
areas[pi] += area;
}
vector<int> a;
for(auto p : areas) a.push_back(p.second);
sort(a.begin(), a.end());
assert(r == (int) a.size());
ll score = 0;
for(int i = 0; i < r; i++) score += max(a[i] - b[i], b[i] - a[i]);
cerr<<"score="<<score<<endl;
printf("%d\n", int(flips.size()));
for(auto e : flips) printf("%d %d\n",e.first + 1, e.second + 1);
for(auto e : removals) printf("%d %d\n",e.first + 1, e.second + 1);
}
int main(){
/*
srand(time(NULL));
for(int tt=0;tt<8;tt++){
string rd="secret/"+itos(tt)+".in";
string wt="secret/"+itos(tt)+".out";
auto flr=freopen(rd.c_str(),"r",stdin);
auto flw=freopen(wt.c_str(),"w",stdout);
*/
solve();
/*
fclose(flr);
fclose(flw);
}
*/
}
Pranav’s solution
Alvaro’s Solution
Masahiro’s Solution
