USACO 2020 February Contest, Silver Problem 3. Clock Tree

Debugging Help
#1

So I replicated a C++ n^2 solution in Java but it gave the wrong answer. What am I doing wrong? I think the problem is probably in the recursion but I am not sure.

import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Stack;

public class clocktree {

    static ArrayList<Integer> adj [];
    static int [] clocks;
    static int [] using;
    static boolean [] finished;
    static int n;
    static int dfst [];
    static int[] t;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("clocktree.in"));
        PrintWriter pw = new PrintWriter(new FileWriter("clocktree.out"));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        clocks = new int[n];
        
        dfst = new int [10000];
    
        adj = new ArrayList[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            clocks[i] = Integer.parseInt(st.nextToken());
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken())-1;
            int last = Integer.parseInt(st.nextToken())-1;
            adj[first].add(last);
            adj[last].add(first);
        }
        int total = 0;
        for (int i = 0; i < n; i++) {
            dfst = clocks.clone();
            dfs(i,-1);
            if (dfst[i] == 1 || dfst[i] == 12) {
                total++;
            }
        }
        pw.println(total);
        pw.close();
    }   
    public static int dfs(int curr, int parent) {
        
        for (int i : adj[curr]) {
          if (i != parent) {
            dfst[i]++;
            dfst[curr] += (12 - dfs(i, curr));
            dfst[curr] = (dfst[curr]-1)%12 + 1;
          }
        }
        
        if (parent != -1) dfst[parent]++;
  
        return dfst[curr];
      }
}
#2

This is Carrara’s solution that I referred to. I’ve been spending hours trying to see what the issue is because it seems like everything should work. Is recursion handled differently in Java from cpp?

#include <fstream>
#include <vector>

using namespace std;

ifstream fin("clocktree.in");
ofstream fout("clocktree.out");

int n;
int t[10000];
int dfst[10000];
vector<int> adj[10000];

int dfs(int curr, int parent) {
  for (int i : adj[curr]) {
    if (i != parent) {
      dfst[i]++;
      dfst[curr] += 12 - dfs(i, curr);
      dfst[curr] = (dfst[curr]-1)%12 + 1;
    }
  }
  dfst[parent]++;
  
  return dfst[curr];
}

int main() {
  fin >> n;
  for (int i = 0; i < n; i++) {
    fin >> t[i];
  }
  for (int i = 0; i < n - 1; i++) {
    int x,y;
    fin >> x >> y;
    adj[x-1].push_back(y-1);
    adj[y-1].push_back(x-1);
  }
  int total = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dfst[j] = t[j];
    }
    dfs(i, -1);
    if (dfst[i] == 1 || dfst[i] == 12) {
      total++;
    }
  }
  fout << total;
}```
#3

Maybe try printing out all the i's and j's that get included in the C++ solution and the ones that get included in your Java solution. Then go into the dfs method with those specific values and see what comes out differently.

#4

I did that and sure enough, there was a difference in the values that were printed out for dfst[curr] but I don’t know how to fix it. I understand the logic in dfs recursion of the c++ solution and I am not sure why it does not work in Java.

#5

C++ and Java are handling += differently on the line where you are writing dist[cur] += …, because the recursive call will modify dist[cur]. But regardless of whether it works or not, this is not very well defined behavior.

C++: https://ideone.com/HSe49y likely interprets it as “b = inc(); a = a + b;”
Java: https://ideone.com/J3Y2MA likely interprets it as “b = a; a = b + inc();”

Keep functions self contained if possible. You can do this problem by passing values back recursively, avoiding modifying a global array at all.

Don’t trust all code out there, especially low quality code like this.

1 Like
#6

Thanks for the explanation. The code worked after storing the return value of the dfs call in a separate variable. I’ll keep those best practices in mind.