Why is there a lot of difference in the 20% and the remaining 80% test data for DIVLAND?



Why is there a lot of difference in the 20% and the remaining 80% test data for DIVLAND(as illustrated by the score before the contest and after all the solutions are rejudged on the 100% test data)? What’s the concept of 20% test data? At least 20% percent of the test cases should contain all types of cases so that participants can get an approximate idea of their final score?


Those 20% were not representive at all:)

You are asked to minimize penalty, which is simply sum of bad edges. In pretests all tests have n<=100, m<=10000. And it is obvious that most of penalty is received for big graphs, and you main goal should be in building general approach for big graphs, not something to crack small cases well.

And it seems that people were focusing on maximizing pretest scores, instead of writing a good solution.


@lebron I guess this was a 10 days long CONTEST, so I don’t think it’s wrong to maximize the pretest scores. And this is the purpose of 20% test data - to give you an idea. If it is all about writing a good solution, then why 20%? Don’t give anything, not even 20%. Let people write good solutions. And test them all after the contest.


It is completely wrong to maximize pretest scores when they are not representative at all, and it is clearly visible that they are… Unless you are doing two different solutions, one for prestest scores and other for main task; otherwise we see situation like this month, when perfect score on pretest may lead to 55 points on final testing :slight_smile: You are right that this 20% should be representive enough to gie you insight - is your solution quite good, or it is awful. In such case there will be not much difference between writing good solution and optimizing pretest score.


Yeah… that’s what I’m saying. The problem setter should carefully decide the 20% test data. Optimizing an NP- Hard problem without strong test cases to help you is pretty difficult.