You are not logged in. Please login at www.codechef.com to post your questions!

×

CAKE2AM - Editorial

2
2

PROBLEM LINKS

Contest
Practice

Author: Abdullah Al Mahmud
Tester: Gerald Agapov
Editorialist: Praveen Reddy Vaka

DIFFICULTY:

medium-hard

PREREQUISITES:

Graph Theory, Maximum Independent Set in Bipartite Graphs, Max Flow/Min Cut, Geometry

EXPLANATION

Consider the following diagram as an example. The several polygons (there are four in total) represent the cuts made and the numbered regions denote the pieces formed as a result. We can denote the cake as graph where each piece is a node and and two nodes will be connected if the corresponding pieces share an edge in the cake. In the original problem we have to choose cake pieces such that no two cake pieces have a side in common and the total volume of the cake pieces selected is maximum. If we denote the volume of each piece as a weight in the corresponding graph node. Our problem reduces to finding the set of nodes in the graph such that no two nodes are connected and the sum of weights is maximum. This is the maximum weighted independent set problem. This is a NP- Complete problem for general graphs but it can be solved in polynomial time for bipartite graphs. If we observe carefully the graph that we constructed will always be bipartite, due to the constraints placed on cuts (We will present a proof later). First let us see the graph representation of the cake shown above. The complement of a independent set in a graph is a vertex cover. So the complement of maximum weighted independent set in a graph will be its minimum weighted vertex cover. We can construct a new graph G' such that the the value of minimum weighted vertex cover in our graph will be same as the weight of minimum cut in G'. The construction is as follows. If our original graph is G and since G is bipartite we can divide the vertices into two sets R and B such all edges are between R and B only (we can use a simple dfs/ bfs to do this classification). Our G' will be a edge weighted graph with all the vertices of G intact and all edges are given a weight of infinity. We add two new vertices source and sink. for every i in R we add an edge from source to i with a weight oght of area(i). for every j in B we add an edge from j to sink with a weight of area(j). Minimum vertex cover in the original graph is same as minimum cut in G' which we can find using max flow. The answer will be (total area - obtained value for min cut).

SOLUTIONS

Setter's Solution: CAKE2AM.cpp
Tester's Solution: CAKE2AM.cpp

This question is marked "community wiki".

asked 20 Jan '14, 01:18

vaka's gravatar image

2★vaka ♦♦
253131822
accept rate: 16%

wikified 20 Jan '14, 09:44

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,198
×1,219
×632
×114
×97
×11
×1

question asked: 20 Jan '14, 01:18

question was seen: 7,734 times

last updated: 21 Jan '14, 14:01