Cut the Cake Challenge Solution Codechef

Cut the Cake Challenge Solution February Challenge 2021

There are NN points in a plane (numbered 11 through NN). For each valid ii, the coordinates of the ii-th point are (Xi,Yi)(Xi,Yi). No three of these points are collinear. Let’s denote a line segment between points uu and vv by (u,v)(u,v).

You are given a Delaunay triangulation of those points, which consists of MM triangles (numbered 11 through MM). For each valid ii, the vertices of the ii-th triangle are the points Pi,1,Pi,2,Pi,3Pi,1,Pi,2,Pi,3.

Also See: February Long Challenge 2021 Solutions

You may perform the following operation any number of times (possibly zero):

  • Flip diagonal segment (u,v)(u,v): If there is a convex quadrilateral that contains this segment as a diagonal and does not contain any points other than its vertices, erase this segment and draw a new segment corresponding to the other diagonal of this quadrilateral. (Note that some segments cannot be flipped. It can be proved that if such a quadrilateral exists, it is unique and the result is also a triangulation.)

Then, you should perform the following operation some number of times:

  • Remove a segment (u,v)(u,v) that is shared by two regions with finite areas. When it is removed, the number of regions decreases by one.

region is defined as a maximal set in the plane such that it does not contain any of the given points or currently existing segments and it is possible to move from each point in this set to any other point in this set without crossing any edge. Note that a region is not necessarily convex. Two regions share a line segment if it is possible to move from one of these regions to the other one by crossing only this segment.

After performing all operations, there must be exactly RR regions with finite areas. Let A1,A2,…,ARA1,A2,…,AR be these areas sorted in non-decreasing order. You are given the desired areas B1,B2,…,BRB1,B2,…,BR of the regions, also sorted in non-decreasing order. Your goal is to make ∑Ri=1|Bi−2⋅Ai|∑i=1R|Bi−2⋅Ai| as small as possible by performing operations. However, you may only perform up to 1,0241,024 operations of the first type; note that the number of operations of the second type must always be M−RM−R.

Input

  • The first line of the input contains three space-separated integers NN, MM and RR.
  • NN lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers XiXi and YiYi.
  • MM more lines follow. For each valid ii, the ii-th of these lines contains three space-separated integers Pi,1Pi,1, Pi,2Pi,2 and Pi,3Pi,3.
  • The last line contains RR space-separated integers B1,B2,…,BRB1,B2,…,BR.

Output

  • First, print a line containing a single integer FF (F≤1024F≤1024) denoting the number of operations of the first type.
  • Then, print FF lines. Each of these lines should contain two space-separated integers uu and vv denoting that you want to flip a diagonal segment (u,v)(u,v).
  • Finally, print M−RM−R lines. Each of these lines should contain two space-separated integers uu and vv denoting that you want to remove a segment (u,v)(u,v).

Example Input

8 7 5
0 11
1 5
2 12
5 0
10 12
12 6
13 5
13 11
1 2 3
5 3 2
8 5 6
7 8 6
4 7 6
2 4 6
5 2 6
13 17 18 48 135

Example Output

2
6 8
2 5
2 6
6 7

Explanation

The initial triangulation is

Cut the Cake Challenge Solution Codechef

After flipping edges FHFH and BEBE, we obtain

Cut the Cake Challenge Solution Codechef

After removing edges BFBF and FGFG, we obtain

Cut the Cake Challenge Solution Codechef

With this sequence of operations, we get the minimum possible score 00.

Test Generation

The source code in C++ used to generate test data can be downloaded here. The generator may crash with some seeds, run it multiple times until it generates the test files.

  • N=1,024N=1,024
  • the coordinates of each point are chosen uniformly randomly between 00 and 105105 inclusive, in such a way that no three points are collinear
  • a Delaunay triangulation is calculated; this is the triangulation given on the input
  • a parameter FF is chosen from the set {0,64,256}{0,64,256}
  • then, FF times, a diagonal segment is chosen uniformly randomly among segments in the Delaunay triangulation, and this segment is flipped
  • let VV be the set of diagonal segments that can be removed from the triangulation after performing the flips.
  • a parameter SS is chosen from the set {64,128,256,512}{64,128,256,512}
  • then, SS uniformly randomly edges are chosen from VV and removed from the triangulation. If is not possible to remove all the SS edges, then the process is repeated.
  • R=M−SR=M−S is the number of resulting regions with finite areas after removing the edges
  • for each of these regions, its area is calculated and multiplied by 22 (the resulting value is always an integer); B1,B2,…,BRB1,B2,…,BR are these values sorted in non-decreasing order

There is one test file for each possible combination of the parameters FF and SS.

Scoring

If your output is invalid (in particular, if you try to flip a non-diagonal segment, or to remove an edge that is not between two regions with finite areas, or to perform too many flips), you will receive the Wrong Answer verdict.

The score for each test case (and therefore each test file) is 108+∑Ri=1|Bi−2⋅Ai|108+∑i=1R|Bi−2⋅Ai|. The score of a submission is equal to the sum of its scores over all test cases. Your goal is to minimise the score of your submission.

There are 12 test files. During the contest, the displayed score will account for exactly 6 test files, i.e. your score reflects your submission’s performance on 50% (6/12) of the test files. However, if your program gets a non-AC verdict on any test file, your submission’s verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program’s scores over the other six test files.

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program C++:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define pii pair<int,int>
#define int long long
const int mod=998244353;
const int Max=1e6+1;
int n,m,r;
int R[Max],lookup[Max];


struct triplet{
    int x,y,z;
};


void refresh()
{
    for(int i=1;i<=n;i++)lookup[i]=0;
}


int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    
    cin>>n>>m>>r;
    vector<pii> xy(n);
    vector<triplet> triangle(m);
    
    
    for(int i=0;i<n;i++)cin>>xy[i].f>>xy[i].s;
    for(int i=0;i<m;i++)cin>>triangle[i].x>>triangle[i].y>>triangle[i].z;
    for(int i=0;i<r;i++)cin>>R[i];
    
    
    map<pii,int> mp;
    for(int i=0;i<m;i++){
        mp[{min(triangle[i].x,triangle[i].y),max(triangle[i].x,triangle[i].y)}]++;
        mp[{min(triangle[i].y,triangle[i].z),max(triangle[i].y,triangle[i].z)}]++;
        mp[{min(triangle[i].z,triangle[i].x),max(triangle[i].z,triangle[i].x)}]++;
    }
    
    vector<pii> valid;
    for(auto it:mp)
    {
        pii p=it.f;int cnt=it.s;
        if(cnt>1)valid.pb({p.f,p.s});
    }
    
    vector<pii> print;
    while(true)
    {
        refresh();
        for(int i=0;i<valid.size();i++){
            lookup[valid[i].f]++;
            lookup[valid[i].s]++;
        }
        
        int cnt=0,val=-1;
        for(int i=1;i<=n;i++){
            if(lookup[i]>cnt){
                cnt=lookup[i];
                val=i;
            }
        }
        
        if(cnt<=2)break;
        vector<pii> temp;
        int track=0;
        for(int i=0;i<valid.size();i++){
            if(track>=cnt-2){
                temp.pb({valid[i].f,valid[i].s});
            }
            else if(valid[i].f==val || valid[i].s==val){
                print.pb({valid[i].f,valid[i].s});
                track++;
            }
            else{
                temp.pb({valid[i].f,valid[i].s});
            }
        }
        
        valid.clear();
        valid=temp;
    }
    
    cout<<0<<endl;
    for(int i=1;i<=m-r;i++){
        cout<<print[i-1].f<<" "<<print[i-1].s<<endl;
    }
    
	cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
	return 0;
}

Program Java:

import java.util.*;
import java.security.SecureRandom;
import java.security.NoSuchAlgorithmException;

class Point {
  int id;
  int x;
  int y;
  
  public Point(int id, int x, int y) {
    this.id = id;
    this.x = x;
    this.y = y;
  }
}

class Segment {
  
  int key;
  Point u;
  Point v;
  Triangle first;
  Triangle second;
  boolean shared;
  boolean locked;
  boolean matched;
  long area;
  Segment flipped;
  
  static HashMap<Integer, Segment> all = new HashMap<Integer, Segment>();
  
  public Segment(Point u, Point v) {
    this.u = u;
    this.v = v;
    this.key = getKey(u.id, v.id);
    this.shared = false;
    this.locked = false;
    this.matched = false;
  }
  
  private static int getKey(int idU, int idV) {
    return Math.min(idU, idV) * 1024 + Math.max(idU, idV);
  }
  
  private static Segment registerSegment(Point u, Point v, Triangle t) {
    int key;
    Segment s;
    // register the segment of a and b
    key = getKey(u.id, v.id);
    if (all.containsKey(key)) {
      s = all.get(key);
      s.second = t;
      s.shared = true;
      s.area += t.area;
      s.generateFlipped();
    } else {
      s = new Segment(u, v);
      all.put(s.key, s);
      s.first = t;
      s.area = t.area;
    }
    return s;
  }

  public static void registerTriangle(Triangle t) {
    t.ab = registerSegment(t.a, t.b, t);
    t.bc = registerSegment(t.b, t.c, t);
    t.ac = registerSegment(t.a, t.c, t);
  }
  
  private Segment generateFlipped() {
    Point a = first.getOppositePoint(this);
    Point b = second.getOppositePoint(this);
    Triangle t1 = new Triangle(first.id, u, a, b);
    Triangle t2 = new Triangle(second.id, v, a, b);
    flipped = new Segment(a, b);
    flipped.first = t1;
    flipped.second = t2;
    flipped.area = this.area;
    flipped.flipped = this;
    return flipped;
  }

  @Override
  public String toString() {
    return String.format("Segment[%d] (%d,%d) between %d and %d (shared: %b, matched: %b)", key, u.id, v.id, first.id, (second == null ? -1 : second.id), shared, matched);
  }

}

class Triangle {
  int id;
  Point a;
  Point b;
  Point c;
  Segment ab;
  Segment bc;
  Segment ac;
  int minX = 100001;
  int maxX = -1;
  int minY = 100001;
  int maxY = -1;
  long area;
  boolean locked;
  boolean matched;
  int region;
  
  public static Comparator<Triangle> compArea = new Comparator<Triangle>() {
    public int compare(Triangle t1, Triangle t2) {
      long area1 = t1.area;
      long area2 = t2.area;
      return (area1 < area2 ? -1 : area1 == area2 ? 0 : 1);
    }
  };
  
  public Triangle(int id, Point a, Point b, Point c) {
    this.id = id;
    setA(a);
    setB(b);
    setC(c);
    calculateArea();
    region = id;
    locked = false;
  }
  
  private void updateHull(int x, int y) {
    if (x < minX) minX = x;
    if (x > maxX) maxX = x;
    if (y < minY) minY = y;
    if (y > maxY) maxY = y;
  }
  
  public void setA(Point p) {
    this.a = p;
    updateHull(p.x, p.y);
  }
  
  public void setB(Point p) {
    this.b = p;
    updateHull(p.x, p.y);
  }
  
  public void setC(Point p) {
    this.c = p;
    updateHull(p.x, p.y);
  }
  
  private void calculateArea() {
    area = 2 * (maxX - minX) * (maxY - minY) - 
      (Math.abs(a.x - b.x) * Math.abs(a.y - b.y) +
      Math.abs(a.x - c.x) * Math.abs(a.y - c.y) +
      Math.abs(b.x - c.x) * Math.abs(b.y - c.y));
  }
  
  public void lock() {
    locked = true;
    ab.locked = true;
    bc.locked = true;
    ac.locked = true;
  }
  
  public Point getOppositePoint(Segment s) {
    return (s == ab ? c : s == bc ? a : b);
  }
  
  @Override
  public String toString() {
    return String.format("Triangle[%d]: %d (matched: %b)", id, area, matched);
  }
}

class Codechef
{
  static final double TIME_MAX_SEARCH = 9.5;
  static final boolean isLogOn = true;
  
  private static double getTime() {
    return 0.001 * System.currentTimeMillis();
  }

  private static void log(String message, Object... params) {
    if (isLogOn) System.out.println(String.format(message, params));
  }
  
  private static long[] filterZerosAndSort(long[] a) {
    int N = a.length;
    long[] b = new long[N], c;
    int pos = 0;
    for (long e : a) {
      if (e > 0) b[pos++] = e;
    }
    if (pos == N)
      c = b;
    else {
      c = new long[pos];
      System.arraycopy(b, 0, c, 0, pos);
    }
    Arrays.sort(c);
    return c;
  }
  
  private static long getScore(long[] target, long[] region) {
    int M = target.length;
    int N = region.length;
    long score = 0;
    for (int i = 0; i < N; i++) {
      score += Math.abs(region[i] - (i < M ? target[i] : 0));
    }
    return score;
  }
  
  public static int find(long[] a, long target)
  {
	  int pos = Arrays.binarySearch(a, target);
	  return pos < 0 ? -1 : pos;
  }
  
	public static void main (String[] args) throws java.lang.Exception
	{
    // final double startTime = getTime();
    double elapsedTime;

    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int M = in.nextInt();
    int R = in.nextInt();

    final double startTime = getTime();

    ArrayList<Point> points = new ArrayList<Point>();
    for (int i = 0; i < N; i++) {
      points.add(new Point(i, in.nextInt(), in.nextInt()));
    }
    ArrayList<Triangle> triangles = new ArrayList<Triangle>();
    Point a, b, c;
    Triangle triangle;
    for (int i = 0; i < M; i++) {
      a = points.get(in.nextInt() - 1);
      b = points.get(in.nextInt() - 1);
      c = points.get(in.nextInt() - 1);
      triangle = new Triangle(i, a, b, c);
      Segment.registerTriangle(triangle);
      triangles.add(triangle);
    }

    Map<Integer, Long> targets = new HashMap<Integer, Long>(R);
    long target;
    for (int i = 0; i < R; i++) {
      target = (long) in.nextInt();
      targets.put(i, target);
    }
    long[] arrTarget = targets.values().stream().mapToLong(Long::longValue).toArray();
    
    Collections.sort(triangles, Triangle.compArea);
    long[] areas = new long[M];
    int numRegion = M;
    for (Triangle t : triangles) {
      t.matched = targets.containsValue(t.area);
      areas[t.region] = t.area;
      // log("" + t);
    }
    
    ArrayList<Segment> flipped = new ArrayList<Segment>();
    ArrayList<Segment> removables = new ArrayList<Segment>();
    ArrayList<Segment> removed = new ArrayList<Segment>();
    
    Collection<Segment> segments = Segment.all.values();
    for (Segment s : segments) {
      if (s.shared) {
        int r1 = s.first.region;
        int r2 = s.second.region;
        s.matched = targets.containsValue(areas[r1] + areas[r2]);
        if (s.matched) {
          areas[r1] += areas[r2];
          areas[r2] = 0;
          s.second.region = r1;
          numRegion--;
          removed.add(s);
          // log("Removed segment by exact match (area = %d): %s", areas[r1], s);
        } else {
          removables.add(s);
        }
      }      
    }
    
    long[] regions = filterZerosAndSort(areas);
    long score = 0;
    // score = getScore(arrTarget, regions);
    // log("Score = %d Regions: %s", score, Arrays.toString(regions));
    
    SecureRandom rnd;

    try {
      rnd = SecureRandom.getInstance("SHA1PRNG");
      rnd.setSeed(N * (M - 1) * 79797979);

      long area1, area2, temp, minScore, newScore;
      int region1, region2, len, pos1, pos2;
      Segment minSegment;
      elapsedTime = getTime() - startTime;
      
      while (numRegion > R && removables.size() > 0 && elapsedTime < TIME_MAX_SEARCH) {
        minScore = Long.MAX_VALUE;
        minSegment = null;
        len = regions.length;  
        long[] minRegions = new long[len - 1];

        // search a segment to remove for a better score
        Segment segment;
        int index;
        Random random = new Random();
        @SuppressWarnings("unchecked")
        ArrayList<Segment> unchecked = (ArrayList<Segment>) removables.clone();
        elapsedTime = getTime() - startTime;
        double maxTimeForSearch = elapsedTime + (TIME_MAX_SEARCH - elapsedTime) / unchecked.size();
        int iteration = 0;
        while (unchecked.size() > 0 && elapsedTime < maxTimeForSearch) {
          // choose an unchecked segment
          index = rnd.nextInt(unchecked.size());
          segment = unchecked.get(index);
          region1 = segment.first.region;
          region2 = segment.second.region;
          pos1 = -1;
          pos2 = -1;
          // no self-shared segment?        
          if (region1 != region2) {
            area1 = areas[region1];
            area2 = areas[region2];
            if (area2 < area1) {
              temp = area1;
              area1 = area2;
              area2 = temp;
            }
            pos1 = find(regions, area1);
            if (pos1 < 0 || area1 == area2)
              pos2 = pos1 + 1;
            else
              pos2 = find(regions, area2);
          }

          if (pos1 >= 0 && pos2 > 0) {
            long[] newRegions = new long[len - 1];
            if (pos1 > 0) System.arraycopy(regions, 0, newRegions, 0, pos1);
            System.arraycopy(regions, pos1 + 1, newRegions, pos1, len - pos1 - 1);
            newRegions[pos2 - 1] = regions[pos1] + regions[pos2];
            Arrays.sort(newRegions);
    
            newScore = getScore(arrTarget, newRegions);
            // log("Merging %d and %d => Score = %d new regions: %s", area1, area2, newScore, Arrays.toString(newRegions));
            
            if (newScore < minScore) {
              minScore = newScore;
              minSegment = segment;
              System.arraycopy(newRegions, 0, minRegions, 0, len - 1);
            }
          } else {
            removables.remove(segment);
          }

          unchecked.remove(index);
          iteration++;
          elapsedTime = getTime() - startTime;
        } 
        
        if (minSegment != null) {
          int r1 = minSegment.first.region;
          int r2 = minSegment.second.region;
          areas[r1] += areas[r2];
          areas[r2] = 0;
          minSegment.second.region = r1;
          numRegion--;
          removed.add(minSegment);
          removables.remove(minSegment);
          // log("Removed segment by best score (%d): %s", minScore, minSegment);
          
          // regions = filterZerosAndSort(areas);
          // score = getScore(arrTarget, regions);
          regions = minRegions;
          score = minScore;

          elapsedTime = getTime() - startTime;
          // log("[At %.3f s] Score = %d after %d iterations, Regions: %s ", elapsedTime, score, iteration, Arrays.toString(regions));
        } else {
          // log("[At %.3f s] No score after %d iterations", elapsedTime, iteration);
        }
      }
      
      // log("Number of regions: %d / %d", numRegion, R);
      
      System.out.println(flipped.size());
      for (Segment s : flipped) {
        System.out.println(String.format("%d %d", s.u.id + 1, s.v.id + 1));
      }
      
      for (Segment s : removed) {
        System.out.println(String.format("%d %d", s.u.id + 1, s.v.id + 1));
      }
      if (numRegion > R) {
        Segment first = removed.get(0);
        int u = first.u.id + 1;
        int v = first.v.id + 1;
        for (int i = numRegion; i > R; i--) 
          System.out.println(String.format("%d %d", u, v));
      }
    } catch (NoSuchAlgorithmException e) {
      e.printStackTrace();
      System.exit(-1);
    }
	}
}

Program Python:

# cook your dish here
n,m,k=map(int,input().split())
pts=[]
for i in range(n):
    pts.append(list(map(int,input().split())))
trns=[]
for i in range(m):
    trns.append(list(map(int,input().split())))
b=list(map(int,input().split()))
c=0
print(0)
x=[]
def match(a,b):
    c=0
    for i in a:
        if i in b:
            c+=1
    return c>1
def common(a,b):
    c=0
    r=[]
    for i in a:
        if i in b:
            r.append(i)
            c+=1
        if c>1:
            return r
        
while(c<(m-k)):
    for i in range(m):
        if i not in x:
            for j in range(i,m):
                if j not in x and i!=j:
                    if match(trns[i],trns[j]):
                        #print(trns[i],trns[j])
                        print(*common(trns[i],trns[j]))
                        x.append(i)
                        x.append(j)
                        c+=1
                        break
        if c==(m-k):
            break

Codechef Long Challenges

September Long Challenge 2021 Solution

February Long Challenge 2021

Leave a Comment