#5?? - DWITE round #2 30th Dec 2011

[hoyifung04]

Anyone else notice that line 18 of the "fixed" test cases claims that there will be 100,000 lines, yet line 100,019 is still giving us input? It is not until line 100,469 that there is another number, meaning that there is another 450 extra lines after the "end" of the third data set and before "start" of the fourth data set.

[hoyifung04]

lufthansa747 @ Thu 01 Dec, 2011 21:58 wrote:

i found a problem this line in the test cases is missing a space

p eelhieluaelldyplb[...]

This isn't the only case like that. There are a total of 368 lines (including that one) that only have one word (instead of two). All of them are in the large test case with long names (number 4).

[A.J]

@crossley7- Yeah, I'll do anything to make sure that NEVER happens again

[crossley7]

I don't mind worst case scenario in terms of mathematical obscure cases, but the time out type massive cases are a pain. When the entire time is spent doing read/write, you have to have a negative run time solution

[PatrickWhite]

What crossley said.
An example of a good limit would be the accidentally easy question from last time, amended with Cyril's limit. That would kill off bad algorithms, not good algorithms that take time to read files.

[A.J]

That's just the problem. There are a lot of problems that kills off bad algorithms just because of the time constraints. In fact, a lot of path finding questions (well, some of the more challenging ones at least) can be solved using a more naive implementation if the input constraints weren't too strict.

I realise that the big testcases did cause problems for this round, so we'll keep these type of questions to a minimum. However, if we want to incorporate non-standard questions, we might have to increase the input constraints once in a while.

[SamScott]

I have downloaded the test file, removed the underscores, fixed the line with no space in it as above, but I have found many more just like it. I started fixing them in the way you suggested - making sure they form a big chain - but there are just too many of them to fix by hand. Other than that, my answers are agreeing with yours.

[nayuki]

Here's my attempt at fixing the input data. I hope this will be the last.

File: https://github.com/nayuki/DWITE-programming-contest-solutions/blob/master/testdata/201111-DATA5.txt