# 2020 January Silver - Clock Tree (Optimization)

2020 January Silver Problem #3 - Clock Tree - USACO

## My Work

``````import java.io.*;
import java.util.*;

public class clocktree {
public static TreeMap<Integer, TreeSet<Integer>> connections;
public static int[] clocks;
public static void main (String[] args) throws IOException {
clocks = new int[N+1];
connections = new TreeMap<>();
for (int i=1;i<=N;i++) {
clocks[i] = Integer.parseInt(st.nextToken());
connections.put(i, new TreeSet<Integer>()); }
for (int i=0;i<N-1;i++) {
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// check if each starting room is valid
// System.out.println(connections);
int count = 0;
for (int i=1;i<=N;i++) if (isPossible(i)) count ++;
// write result
//PrintWriter out = new PrintWriter(System.out);
PrintWriter out = new PrintWriter(new FileWriter("clocktree.out"));
out.println(count);
out.close();

}
static boolean isPossible (int start) {
// check if position is valid starting point
// set up
int n = clocks.length;
int[] clockPos = clocks.clone();
clockPos = 12;
int[] checker = new int[n];
Arrays.fill(checker, 12);
boolean[] changedTo12 = new boolean[n];
stack.push(new int[] {start, -1});
// simulate a walk through the tree with a depth-first search
// (where leaves are moved to 12 and removed, and then repeat)
while (!stack.isEmpty()) {
// System.out.println(stack);
int[] s = stack.pop();
int node = s;
int parent = s;
if (Arrays.equals(clockPos, checker)) return true; // if all clocks at 12 stop and return true
if (parent != -1) clockPos[node] = add(clockPos[node], 1); // move dial forward 1 to represent walking into room
boolean isLeaf = true;
for (int c: connections.get(node)) { // check if node is not a leaf
if (c!=parent && !changedTo12[c]) {
isLeaf = false;
stack.push(new int[] {c, node});
break; } }
if (isLeaf) { // otherwise simulate going back and forth between leaf and parent until leaf is 12 (ending on leaf)
if (!changedTo12[parent]) {
clockPos[node] = 12;
changedTo12[node] = true;
} }
}
return Arrays.equals(clockPos, checker);
}
static int add (int a, int b) {
// adds b hours to time a on a 12-hour system
while (a+b > 12) {
b -= 12-a;
a = 0; }
return a+b; }
}
``````

This basically solves the problem with an O(N^2) solution. The algorithm starts at a given point on the tree, going all the way to each leaf and setting it to 12 by going back and forth between the leaf and its parent, and then ‘removing’ that leaf from consideration and repeating the process with newly-created leaves. This is done for each of the N nodes, with the number of successful ones counted and output as the answer.

## Question

Right now this code passes 12 out of 15 test cases, and times out on the last 3. I think there are probably just slow methods or sections that I haven’t recognized, but I’m just wondering how could I optimize this code to get those last three test cases? I know that there is an O(N) solution, however I’d like to try to get my O(N^2) solution to pass (so I don’t want to change the logic itself too much).

What I did in this problem what that I did dfs on the rooms and assigned either red or blue to each of the nodes. I colored it in a way so that no two connected nodes have the same color. I basically made a bipartite graph. Then I added up all the red nodes and then blue nodes then you can mathematically find out how many rooms you can start at. This was the code that I wrote:

if((redSum - 1) % 12 == blueSum % 12)
{
out.println(redSize);
}
else if((blueSum - 1) % 12 == redSum % 12)
{
out.println(blueSize);
}
else if(blueSum % 12 == redSum % 12)
{
out.println(nRooms);
}
else
{
out.println(0);
}

1 Like

You also how to keep track of the number of red and blue nodes.

Thank you, I’ll try that and see if it works!