 # CUTCAKE - Editorial

Author: Alei Reyes
Tester: Felipe Mota

Tie-break

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:

1. Individual triangles
2. A triangle and 1-3 triangles adjacent to it.
3. 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

1. Define time T1 to be approx 0.95 of time limit
2. 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
3. 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.

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;
}
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{
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];
int y = striangles[i];
int z = striangles[i];
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);
}
*/

}

5 Likes

Guauu!   1 Like

that allowed @rns_cus to solve it optimally!

Imagine solving a problem so brilliantly that it forces the relative score of all other participants to zero.

and then it hits you back, because now there’s no one to fight and your score is not defined anymore. This guy wins.

1 Like

Can you please describe the optimal solutions by @rns_cus or @scheffeli

1 Like

Most inputs can be solved with a greedy strategy. If a region’s area is equal to some B_i, hold that region as fixed and do not consider flipping or removing any of its edges.

Let’s draw some pictures where triangles that are fixed in the beginning are shown in gray. A test case with 0 flips and 256 deletions looks like this: https://i.imgur.com/uNmBvET.png

This is almost trivial. There are very few possible moves. You can pick a non-fixed triangle and use dfs to find a connected set of triangles with total area equal to some B_i. Join those triangles together, repeat until all triangles are fixed.

Test cases that include flips get more and more difficult. Here is an example of the last case, 256 flips followed by 512 deletions: https://i.imgur.com/lQn3ibU.png

The final state, with original edges shown in light gray: https://i.imgur.com/ORH6svG.png

It’s definitely trickier than the zero-flip inputs, but even here we have so many fixed triangles that most white regions are quite small.

Some ideas: Flip an edge and run dfs from the two new triangles, flip several neighboring edges, include flips in the dfs… Keep trying stuff and fixing more and more regions. Once only a few regions are remaining, start flipping all edges randomly. If you’re lucky, you’ll eventually fix all regions and have an optimal solution.

If you’re unlucky, the greedy assumption we made in the beginning is wrong and will never find an optimal solution. This is because there is a “fixed” triangle that actually must be destroyed, and some region elsewhere will end up with the triangle’s original area. I believe this happened in one of the official test cases. One possibility is to run your solver as far as it goes and remember the regions that were not fixed in the end. Restart the solver, but try to fix those areas first, allowing breaking of fixed regions.

P.S. @alei The scoreboard is fixed now, but profile pages still show wrong ranks for FEB21B: 5 Likes