MaxEdges solution codechef

MaxEdges solution codechef – Tracy gives Charlie a Directed Acyclic Graph with N vertices. Among these N vertices, K vertices are sources, and L vertices are sinks.

MaxEdges solution codechef

Find out the maximum number of edges this graph can have.

Note:

  • source is a vertex with no incoming edge.
  • sink is a vertex with no outgoing edge.
  • A vertex can be both, a source, and a sink.

Input Format

  • First line will contain T, number of test cases. Then the test cases follow.
  • Each test case contains of a single line of input, three space-separated integers N, K, and L – the number of vertices, the number of sources and the number of sinks respectively.

Output Format

  • For each test case, output in a single line, the maximum number of edges this graph can have.

MaxEdges solution codechef

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 10^9
  • 1 \leq K \lt N
  • 1 \leq L \lt N

Sample 1:

Input

Output

2
3 1 1
5 3 3
3
4

 

 

MaxEdges solution codechef

Test case 1: Assume that the vertices are numbered 1,2, and 3. Let 1 be a source and 3 be a sink. The edges of a possible DAG are 1\rightarrow 2, 2\rightarrow 3, and 1\rightarrow 3.

The number of edges in this graph are 3. It can be shown that this is the maximum number of edges possible under given constraints.

Test case 2: Assume that the vertices are numbered 1,2,3,4, and 5. Let 1,2, and 3 be sources and 3, 4, and 5 be sinks. The edges of a possible DAG are 1\rightarrow 4, 2\rightarrow 4, 1\rightarrow 5 and 2\rightarrow 5.

The number of edges in this graph are 4. It can be shown that this is the maximum number of edges possible under given constraints.

Post navigation

Leave a Reply

Your email address will not be published.