10526 - Intellectual Property

Per · Post by **Per** » Sun Jul 06, 2003 6:30 pm

I keep getting WA, and before I go about checking my loops for off-by-one errors yet again, I would like to be certain that my input is correct (most of my solution is based on well-tested code, so I suspect I might be doing some mistake with the input). How weird input can one expect? Can there be arbitrary 8-bit ASCII, even NULL's? And even though the problem statement does not say so explicitly, may I assume that "BEGIN JCN CODEBASE" and "END JCN CODEBASE" appear as actual lines and not just as part of lines?

And if none of these, does anyone have a really tricky test case I could try?

gvcormac · Post by **gvcormac** » Sun Jul 06, 2003 6:37 pm

The "BEGIN ..." and "END ..." are separate lines.

Have you considered:

TDP: abcxbcde

JDN: abcde

(Spoiler: the judges' data are available at Waterloo.)

Per wrote:I keep getting WA, and before I go about checking my loops for off-by-one errors yet again, I would like to be certain that my input is correct (most of my solution is based on well-tested code, so I suspect I might be doing some mistake with the input). How weird input can one expect? Can there be arbitrary 8-bit ASCII, even NULL's? And even though the problem statement does not say so explicitly, may I assume that "BEGIN JCN CODEBASE" and "END JCN CODEBASE" appear as actual lines and not just as part of lines?

And if none of these, does anyone have a really tricky test case I could try?

Per · Post by **Per** » Sun Jul 06, 2003 10:02 pm

Thanks! I handled that test case OK, but with the judges' data I was able to find a nasty bug in my suffix array implementation, so I guess it wasn't nearly as well-tested as I thought.

I'll take the fact that your elegant sample solution which just use qsort to create the suffix array was faster than my far too complicated construction routine (which pretty much follows the original paper by Manber and Myers) as a reminder to always keep things simple!

gvcormac · Post by **gvcormac** » Mon Jul 07, 2003 2:53 am

Thanks but don't throw away your Manber/Myers code, because its worst-cast run-time is n log n whereas the simple approach is n^2 log n.

Per wrote:Thanks! I handled that test case OK, but with the judges' data I was able to find a nasty bug in my suffix array implementation, so I guess it wasn't nearly as well-tested as I thought.

I'll take the fact that your elegant sample solution which just use qsort to create the suffix array was faster than my far too complicated construction routine (which pretty much follows the original paper by Manber and Myers) as a reminder to always keep things simple!

Per · Post by **Per** » Tue Jul 15, 2003 2:05 pm

Ah, it seems my construction actually was faster than qsort. The bottleneck was my searches, where I simply used a routine which counts the number of occurences of a string by doing lower and upper bound (i.e. two binary searches instead of one).

When I fixed this, the program ran 3.5 times faster on judge's input! (I resubmitted the old program as well to check that it wasn't just the new server.)

dwyak · Post by **dwyak** » Tue Jul 15, 2003 2:54 pm

I think n^2 is simple, but I don't know what's the nlogn approuch.
Can anybody give a hint?

shahriar_manzoor · Post by **shahriar_manzoor** » Wed Jul 16, 2003 4:21 am

I just reply to remove a confusion about the new server--

The old pentium III 800 is also now the judging machine. So the run times of programs remain the same.

the New server will act as a web server.

BiK · Post by **BiK** » Thu Nov 13, 2003 4:48 pm

Something very strange happens with this problem. When I wrote my program I got TLE answer from the ONLINE_JUDGE. Hopefully the test data for the problem were available at the Waterloo web page. When I ran my solution locally it was totally correct and its runtime was something around 1 sec. Far less than the 10 secs allowed by the judge.

Besides the complexity of my solution is such that I think there should be no problem with the time limit. I use Suffix tree construction -> O(n) + matching statistics -> O(n) + stable_sort -> O(n * log n * log n).

Could somebody explain? I'm totally stumped.

BiK · Post by **BiK** » Thu Oct 21, 2004 2:02 am

Well, I returned back to this problem after one year and decided to rewrite the input output procedures using <cstdio> instead of <iostream>. Actually I should have tried this one year ago but strange enough this idea did not come to me at that time. It was just recently that a friend of mine rediscovered how much faster the i/o with <cstdio> is. Of course my solution got accepted. ... but this is not the end of the story. I resubmited my old solution again and you won't believe me but it got accepted too. ... this is still not the end of the story. I looked at the runtimes of the two solutions and what do you think the difference was? Well, they were the same. Not even a thousandth of the second difference. Both were reported to have run for 0.328 seconds. I am damn curious to understand why my solution was rejected with TLE one year ago. Unfortunately the end of the story comes here. So maybe I'll never know. Neither will you ...

DD · Post by DD » Sat Mar 19, 2011 5:47 pm

I just solved this problem by using suffix array. However,I think this problem should clarify one thing more is that both "BEGIN TDP CODEBASE" and "BEGIN JCN CODEBASE" should not appear in code bases. I got some confusions before since the problem statement didn't clarify this.

chengouxuan · Post by **chengouxuan** » Thu Jun 09, 2011 6:57 am

can a O(n*n*lgn) solution be ACed?

OJ Board

10526 - Intellectual Property

10526 - Intellectual Property

Re: 10526 - Intellectual Property

New Server

Damn weird

Re: 10526 - Intellectual Property

Re: 10526 - Intellectual Property