JOIN
Get Time

   Problem Statement  

 Problem Statement for MinimumCutsAgain

Problem Statement

    

In this problem you will be constructing a simple weighted directed graph.



A 0-1 cut in the graph is a subset S of vertices that does contain the vertex 0 but does not contain the vertex 1. Let T be the complement of S. The size of the cut is the total weight of all edges that lead from S to T. (The weight of edges from T to S does not matter.) A 0-1 cut is called a minimum 0-1 cut if its size is the smallest among all 0-1 cuts.



You are given an int n. Construct any undirected graph with the following properties:

  • The number of vertices must be between 2 and 20, inclusive.
  • The vertices must be numbered 0 through v-1, where v is their number.
  • The graph must be simple - i.e., no self-loops and no multiple edges going in the same direction. (However, for any distinct x,y the graph may contain both an edge from x to y and an edge from y to x.)
  • All edge weights must be integers between 1 and 10^9, inclusive.
  • The graph must have exactly n different minimum 0-1 cuts.

Suppose the graph you constructed has v vertices and e edges. Return a int[] with 1 + 3*e elements. Element 0 of the return value should be the number v of vertices. The rest of the return value should be a list of edges. For each edge i, give its source vertex si, its destination vertex ti, and its weight wi. That is, the return value should be formatted as follows: { v, s0, t0, w0, s1, t1, w1, ... }.



If there are multiple correct solutions, you may output any of them.

 

Definition

    
Class:MinimumCutsAgain
Method:construct
Parameters:int
Returns:int[]
Method signature:int[] construct(int n)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 1,000, inclusive.
 

Examples

0)
    
1
Returns: {2, 0, 1, 6 }
The return value describes a graph on 2 vertices. There is an edge from vertex 0 to vertex 1 of weight 6. This graph has exactly one minimum 0-1 cut: the cut {0}. The cost of this cut is 6.
1)
    
2
Returns: {3, 0, 2, 1, 0, 1, 1, 2, 1, 1 }
There are two different minimum 0-1 cuts: the cut {0} and the cut {0,2}. Each of these cuts has cost 2.
2)
    
4
Returns: {4, 0, 2, 4, 2, 1, 4, 0, 3, 2, 3, 1, 2 }
This time there are four 0-1 cuts: {0}, {0,2}, {0,3}, and {0,2,3}. The cost of each of them is 6. Thus, all four cuts are minimum 0-1 cuts.
3)
    
6
Returns: {6, 0, 1, 1, 0, 5, 2, 1, 0, 4, 1, 2, 1, 1, 3, 2, 1, 4, 1, 2, 5, 1, 3, 4, 2 }
The minimum 0-1 cuts in this graph have cost 1. There are six such cuts: the cuts {0,2,3,4,5}, {0,2,4,5}, {0,2,5}, {0,3,4,5}, {0,4,5}, and {0,5}.
4)
    
752
Returns: 
{20, 0, 16, 1, 1, 5, 2, 2, 11, 2, 3, 5, 2, 5, 2, 1, 5, 3, 1, 5, 11, 1, 7, 4, 2, 7, 18, 1, 9, 3, 2, 9, 17, 1, 11, 10, 2, 13, 1, 1, 13, 5, 2, 13, 15, 1, 14, 16, 2, 14, 17, 1, 16, 6, 2, 16, 13, 1, 16, 17, 1, 17, 12, 1, 18, 3, 2, 18, 6, 1, 19, 15, 1 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2016 TCO Algorithm Algo Semifinal 1 - Division I, Level Two