I'm working on a puzzle and have solved it, but my code is not fast enough to get the maximum score (if the code is faster than a certain achievable threshold, one gets awarded the maximum score). I have tried multiple approaches but it seems I can't figure it out. My Java code is appended at the end.
The puzzle is as follows: Input is a number >= 1 of lines of two integers separated by a space which represent edges in a graph. This graph is a tree with 0 as root. We have to calculate the "value" of the graph defined as:
Each node initially has value 1. If a node has children, they each increase its value by their value +1. The final value of a node it its new value + values of all it's children. So:
node value = 1 + (# of children) + (sum of children's values).
The value of the graph is the sum of values of its nodes.
Then print the value modulo 1234567.
Examples:
0 1
2 1
2 3
has value 16
.
1 0
2 0
1 3
1 4
has value 17
.
Here's my code, if someone has any idea where I'm being inefficient, thanks for the help!
public static void main (String[] args) {
Scanner stdin = new Scanner(System.in);
Stack<Tuple> allNodes = new Stack<>();
List<Integer> input = new ArrayList<>();
//add all input to input list
while (stdin.hasNext()) {
input.add(stdin.nextInt());
}
allNodes.push(new Tuple(0, -1));
int index, childIndex, child, parent, iterator = 0;
//search input for known nodes from parents and add them to allNodes
while (input.size() > 0) {
parent = allNodes.get(iterator++).id;
while ((index = input.indexOf(parent)) >= 0) {
//check whether index is even or odd
childIndex = (index%2 == 0) ? index+1 : index-1;
child = input.get(childIndex);
allNodes.push(new Tuple(child, parent));
input.remove(index);
if (index > childIndex) { input.remove(childIndex); }
else { input.remove(index); }
}
}
int[] values = new int[allNodes.size()];
Tuple currentNode;
//compute values
while (allNodes.size() > 1) {
currentNode = allNodes.pop();
values[currentNode.parent] += ++values[currentNode.id]+1;
}
values[0]++;
int sum = 0;
for (int i=0; i<values.length; i++) {
sum += values[i];
}
System.out.println(sum%1234567);
stdin.close();
}
public static class Tuple {
int id;
int parent;
public Tuple (int id, int parent) {
this.id = id;
this.parent = parent;
}
}
9
. I ran your program and got16
, so i think that the behavior you need is different from the one you describe \$\endgroup\$