Debugging on large tests

Revision en2, by szawinis, 2016-11-21 13:25:09

Extremely large tests are very hard to debug, because we are not able to understand the input anymore. The only choice that is left is to go back and look at the code, to potentially find any flaws. I find it quite hard to do this, as sometimes it is very hard to find the bug just looking at the code, especially when the code is confusing.

I was about to finish a problem called "Hotels" from POI, but I got 99%. There was only one case wrong and it was one of the larger cases (N = 5000). Now I'm stuck, because I couldn't find anything wrong with the code, even though it is relatively short. I used an approach similar to this.

I'm also quite confused, because I got OK verdict and got 9/10 points for the test case even though one of the subtests was wrong when I checked. Am I not supposed to get 5 points or so?

Would you guys be so kind to point out if I did anything wrong? Also, how do you guys deal with situations where you have to debug large tests?

#include <bits/stdc++.h>
using namespace std;

int n;
long long ans, tmp[5001], sum[5001], p[5001];
vector<int> g[5001];

void dfs(int u, int p, int d) {
	tmp[d]++;
	for(int i = 0, v = g[u][i]; i < g[u].size(); i++, v = g[u][i]) if(v != p) dfs(v, u, d+1);
}

int main() {
	scanf("%d",&n);
	for(int i = 1,u,v; i < n; i++) {
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) {
		fill(sum+1, sum+n+1, 0);
		fill(p+1, p+n+1, 0);
		for(int j = 0; j < g[i].size(); j++) {
			fill(tmp+1, tmp+n+1, 0);
			dfs(g[i][j], i, 1);
			for(int k = 1; k <= n; k++) {
				ans += tmp[k]*p[k];
				p[k] += tmp[k]*sum[k]; // distributive property
				sum[k] += tmp[k];
			}
		}
	}
	printf("%lld", ans);
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English szawinis 2016-11-21 13:25:52 14 Tiny change: 'or so?\n\n![ ](https://' -
en2 English szawinis 2016-11-21 13:25:09 323
en1 English szawinis 2016-11-21 13:14:55 1616 Initial revision (published)