Блог пользователя szawinis

Автор szawinis, история, 8 лет назад, По-английски

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?

See screenshot

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);
}
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Wrong answer is always 0 / x points.

9/10, 5/10, etc is a case of TLE. After exceeding HALF of runtime, you start to get less points for your code.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Oh, I see. So if I solve the TLE and still get the wrong answer I will get 0 points? This is a strange system. I thought normally it should allow you to use the whole runtime.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, I'm pretty sure you should solve the TLE.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I know I should always solve TLE. My apologies for being unclear. The question is, does the TLE verdict assume that my answer is correct? Because should TLE also get 0 points if the answer is incorrect?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Have you tried stress testing?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As in trying huge cases? When I submitted, there was only one TLE case from half of them having maximum constraints. The rest were way below the halfway line. I'm wondering if I only need to do a slight optimization?