11272 - Summing the Lengths of the Longest Increasing Subseq

[baodog]

Note that it asks for 3 digits, not 5 anymore and sample i/o
has been corrected also.

What happened is that I made a mistake and thought it was 2*Sqrt(n)*n!
That would have been solvable by Monte Carlo Simulation and finding
a pattern for the mean value... i.e. Generate many random permutations
and averaging the LIS to find the pattern of 2*Sqrt(n)... But this
approximation, while correct in the limit of n->infinity is actually not precise enough to get 5 digits, unless n>10^10 ... but in that case
monte carlo simulation is not really possible.

In this corrected version, it's much more difficult, but now it's
correct. The way to solve it is to use Monte Carlo simulation to find
a close enough approximation of the following form for the mean
value:

k1*Sqrt(n)+k2*n^(1/6).

[Robert Gerbicz]

The way to solve it is to use Monte Carlo simulation to find
a close enough approximation of the following form for the mean
value:

k1*Sqrt(n)+k2*n^(1/6).

I've downloaded 2 articles related to the problem. There is an about 60 pages long article from this year, in that they prove your formula. But what is the error term?! Has it been proved some exact theorems, because I haven't found that in these articles. If formula gives you, say:
18400001*10^k then how sure are you that the error term is less than 10^k ?
And it has got large probability that this critical data will happen for random input set, because there are (at most) 100000 test cases.

If you are unable to prove a correct theorem, say

Code: Select all

abs(f(n)-k1*n^(1/2)-k2*n^(1/6))<n^(1/12) 

( and using this you will be able to find the first 3 digits in almost all cases
, or in all cases if your formula is better )

then you should delete this problem from the site.

[Robert Gerbicz]

I've tried some (k1,k2) pairs what I've found in the articles, all of them WAs.
After it I've written a Monte Carlo simulation to get a probably better pairs. What is so surprising that I've found the sample input/output is wrong. For n=101 the correct answer should be 158, which is quite far from the posted 154. I think it's absolutely wrong problem, because if you use an approximation formula then for critical inputs you will get still WA, or if you simulate by Monte Carlo you will get either TLE ( because there are 100,000 inputs ) or WA for critical inputs.
[ and if you use an approximation formula how you give the error term?
or the problemsetter is the newest owner of the Fields medal ?]
Anyway here is my program's output for n=101 and for different runs, in each run I've generated 100,000 random tests, *first* means what should be the first 3 digits if we use average for approximation. [ Note that for critical inputs 100,000 tests aren't enough, and there should be lot of critical inputs ]:

Code: Select all

n=101,TRY=100000,average=16.839260,first=158
n=101,TRY=100000,average=16.840970,first=158
n=101,TRY=100000,average=16.833720,first=158
n=101,TRY=100000,average=16.847520,first=158
n=101,TRY=100000,average=16.845340,first=158
n=101,TRY=100000,average=16.836660,first=158
n=101,TRY=100000,average=16.843800,first=158
n=101,TRY=100000,average=16.843510,first=158
n=101,TRY=100000,average=16.843360,first=158
n=101,TRY=100000,average=16.835200,first=158
n=101,TRY=100000,average=16.847330,first=158
n=101,TRY=100000,average=16.846940,first=158
n=101,TRY=100000,average=16.828870,first=158
n=101,TRY=100000,average=16.834780,first=158
n=101,TRY=100000,average=16.832950,first=158
n=101,TRY=100000,average=16.832890,first=158
n=101,TRY=100000,average=16.840970,first=158
n=101,TRY=100000,average=16.832670,first=158
n=101,TRY=100000,average=16.841920,first=158
n=101,TRY=100000,average=16.839880,first=158
n=101,TRY=100000,average=16.837690,first=158
n=101,TRY=100000,average=16.846350,first=158
n=101,TRY=100000,average=16.845390,first=158
n=101,TRY=100000,average=16.833740,first=158
n=101,TRY=100000,average=16.839300,first=158
n=101,TRY=100000,average=16.839150,first=158
n=101,TRY=100000,average=16.839940,first=158
n=101,TRY=100000,average=16.831450,first=158
n=101,TRY=100000,average=16.837570,first=158
n=101,TRY=100000,average=16.837650,first=158
n=101,TRY=100000,average=16.835740,first=158
n=101,TRY=100000,average=16.832960,first=158
n=101,TRY=100000,average=16.839590,first=158
n=101,TRY=100000,average=16.838700,first=158
n=101,TRY=100000,average=16.839570,first=158
n=101,TRY=100000,average=16.849940,first=158
n=101,TRY=100000,average=16.829000,first=158
n=101,TRY=100000,average=16.845570,first=158
n=101,TRY=100000,average=16.841860,first=158
n=101,TRY=100000,average=16.848770,first=158
n=101,TRY=100000,average=16.840170,first=158
n=101,TRY=100000,average=16.836740,first=158
n=101,TRY=100000,average=16.844040,first=158
n=101,TRY=100000,average=16.836080,first=158
n=101,TRY=100000,average=16.843800,first=158
n=101,TRY=100000,average=16.844250,first=158
n=101,TRY=100000,average=16.839160,first=158
n=101,TRY=100000,average=16.842420,first=158
n=101,TRY=100000,average=16.845130,first=158
n=101,TRY=100000,average=16.842120,first=158
n=101,TRY=100000,average=16.837930,first=158
n=101,TRY=100000,average=16.845840,first=158
n=101,TRY=100000,average=16.844130,first=158
n=101,TRY=100000,average=16.829320,first=158
n=101,TRY=100000,average=16.833550,first=158
n=101,TRY=100000,average=16.832960,first=158
n=101,TRY=100000,average=16.833850,first=158
n=101,TRY=100000,average=16.842320,first=158
n=101,TRY=100000,average=16.832090,first=158
n=101,TRY=100000,average=16.841100,first=158
n=101,TRY=100000,average=16.840870,first=158
n=101,TRY=100000,average=16.839840,first=158
n=101,TRY=100000,average=16.844760,first=158
n=101,TRY=100000,average=16.846740,first=158
n=101,TRY=100000,average=16.831040,first=158
n=101,TRY=100000,average=16.842490,first=158
n=101,TRY=100000,average=16.839410,first=158

[baodog]

Thanks for the correction.
Actually many random generators are biased.
They give very different results.

Ignore this problem for now...

It is been updated to ask for only order
of magnitude approximation instead, i.e.

log10(answer) rounded to integer.

[sclo]

Has the problem been updated yet? It seems that the problem statement is still the old one.

[baodog]

Not yet.
I will send them a reminder.