Problem Statement
In this problem a directed forest is an arbitrary directed acyclic graph in which each node has at most one incoming edge. (Note that each node may have arbitrarily many outgoing edges.)
Your friend has a directed forest. The vertices of the forest are numbered starting from 0. You do not know what the forest looks like. Your friend has told you that he assigned a positive integer weight to each vertex: vertex i got weight a[i].
Your friend then computed aggregate weights of vertices. The aggregate weight of vertex i is the sum of the weights of all vertices reachable from i, including i itself.
You are given two int[]s: a and b. Your friend now claims that for each i the aggregate weight of vertex i is b[i].
Return "Possible" if there exists a valid directed forest that corresponds to the above scenario. Otherwise, return "Impossible".
Definition
- Class:
- HiddenTreeDiv2
- Method:
- isPossible
- Parameters:
- int[], int[]
- Returns:
- String
- Method signature:
- String isPossible(int[] a, int[] b)
- (be sure your method is public)
Constraints
- a,b will have the same number of elements.
- a will have between 1 and 14 elements, inclusive.
- Each element of a,b will be between 1 and 10^9, inclusive.
Examples
{1,1,1,1,1,1,1,1,1,1,1,1,1}{1,1,1,1,1,1,1,1,1,1,1,1,1}Returns: "Possible"
A valid forest in this case is one with no edges.{123}{321}Returns: "Impossible"
{1,1,1}{3,1,2}Returns: "Possible"
A valid forest is one with edges 0->2 and 2->1.{4,1,4,2,1,3}{5,1,6,2,4,3}Returns: "Possible"
{536870912,536870912,536870912,536870912,536870913, 536870912,536870912,536870912,536870915}{536870912,536870912,536870912,536870912,536870913, 536870912,536870912,536870912,536870916}Returns: "Impossible"
Back to all problems