PlanarGraphShop
SRM 453.5 · 2009-11-20 · by misof
Problem Statement
In the Kocurkovo village there is a shop that sells simple planar graphs. (See Notes for a definition.)
The cost of any graph with X vertices and Y edges is (X^3 + Y^2) gold coins.
Monika has N gold coins, and she wants to spend all of them on simple planar graphs.
Write a method that gets the value N and computes the minimum number of simple planar graphs Monika has to buy in order to spend exactly N gold coins. She is allowed to buy multiple graphs of the same type.
Notes
- A simple graph is an ordered pair (V,E) where V is a finite non-empty set of objects called vertices, and E is a finite set of edges. Each edge is a two-element subset of V. (You can find drawings of several graphs in Example #3.)
- Note that a simple graph does not contain any loops (edges that connect a vertex to itself) and any duplicate edges. In other words, each edge connects two different vertices, and each pair of vertices is connected by at most one edge.
- A graph is called planar if it has a drawing in the plane such that no two edges intersect.
- Note that a simple planar graph does not have to be connected.
Constraints
- N will be between 1 and 50,000, inclusive.
36 Returns: 1
For 36 gold coins she can buy a triangle: a simple planar graph with 3 vertices and 3 edges.
7 Returns: 7
The only simple planar graph that costs 7 gold coins or less is the graph that consists of a single vertex (and no edges). This graph costs 1^3 + 0^2 = 1, so Monika has to buy 7 of them.
72 Returns: 2
She can buy 2 triangles for 36 gold coins each. No simple planar graph costs exactly 72 gold coins, hence the optimal answer in this case is 2.
46 Returns: 3
All the graphs Monika can afford are shown in the following picture: One optimal solution is to buy graphs worth 1 + 9 + 36 gold coins.
50000 Returns: 2
Submissions are judged against all 142 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PlanarGraphShop with a public method int bestCount(int N) · 142 test cases · 2 s / 256 MB per case