TLE in ASCDFIB

[daft_wullie]

Hi,

I'm struggling with the problem ASCDFIB. I think I understood the principle concept (Fibbonacci and modulus). So i coded an approach using pre-generation of one period of fibonacci numbers. With this, all the code has to do is some apropriate slicing and ordering of the precalculated list.

""" SPOJ class. 15980. Ascending Fibonacci Numbers. Problem code: ASCDFIB """
##from __future__ import print_function
import sys
_MOD = 10**5
_PER = 15*10**4
_ALL = [0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 7, 8, 8, 9, 9, 9,
        11, 13, 13, 13, 15, 16, 16, 17, 17, 17, 19, 21, 21, 21, 23, 24, 24, 25,
        25, 25, 27, 29, 29, 29, 31, 32, 32, 33, 33, 33, 34, 34, 34, 34, 34, 34,
        34, 34, 35, 37, 37, 37, 39, 40, 40, 41, 41, 41, 43, 45, 45, 45, 47, 48,
        48, 49, 49, 49, 51, 53, 53, 53, 55, 56, 56, 57, 57, 57, 59, 61, 61, 61,
        63, 64, 64, 65]
def iter_fibos(num):
    fibos = [0] * num
    fibos[1] = 1
    for idx in range (2, num):
        fibos[idx] = (fibos[idx-1] + fibos[idx-2]) % _MOD
    return fibos
def calc_asc_fib(start, length, fibs):
    if length >= _PER:
        return _ALL
    start_relevant = start % _PER
    length_relevant = min(_PER, length)
    if start_relevant + length_relevant <= _PER:
        fibs_chosen = fibs[start_relevant-1:start_relevant+length_relevant]
    else:
        fibs_chosen = (fibs[:(start_relevant+length_relevant) % _PER] +
                        fibs[start_relevant-1:])
    fibs_chosen.sort()
    return fibs_chosen[:100]
def main():
    cases = sys.stdin.read().split('\n')
    output = sys.stdout.write
##    cases = [ c for c in cases if c]
    fibs = iter_fibos(_PER)
    results = []
    for num, line in enumerate(cases[1:]):
        start, length = map(int, line.split())
        res = calc_asc_fib (start, length, fibs)
        res = ' '.join(map(str, res))
        results.append('Case %d: %s' % (num+1, res))
    output('\n'.join(results))
    output('\n')
if __name__ == '__main__':
    main()

But I got TLE. With a little bit of optimization for large input values

##    if length >= _PER:
##        return _ALL

I got NZEC.

Any hints for optimization?
Regards
DaftWullie

[numerix]

The NZEC has nothing to do with your "optimization", it is caused by the way you read the input.
read().split("\n") does not work properly for all kinds of EOL.

If this is corrected, your code leads to WA, as the "optimization" is really fast, but unfortunately wrong.

Without that "optimization" my 0.60 s AC code is about 8 times as fast as yours, tested with some random data (with larger b).
About 95% of the runtime of your code is consumed by that operation: fibs_chosen.sort().
So, you have to find a better way of sorting the output without sorting it that way ...

[daft_wullie]

Thank you very much for your checks and the immediate response.

I was somewhat astonished to read that my optimization is wrong but you're absolutely right. I must have been so happy to detect the period in the fib sequence that I jumped to this wrong conclusion. But understanding that I have to consider elements of the sequence outside its period makes it even worse when it comes to returning the 100 smallest elements ... Perhaps I need another data structure?

The read.split('\n') was my favourite since adjusting the input reading for some early i/o related problems at spoj and I have used it without (known) problems since then... Do you recommend to use sys.stdin.readlines()?

[numerix]

happy to detect the period in the fib sequence

I don't know if there is another way to do it, but my AC solution uses the same period.

Perhaps I need another data structure?

I didn't need anything else but lists.

Do you recommend to use sys.stdin.readlines()?

There a several ways of reading the input in Python as you know. Sometimes (but not so often) I use readlines(), as it splits all kinds of EOL.

[daft_wullie]

Now I got AC Although it was the very next attempt submitted, I had to perfom some rework on the code. The perfomance issue was solved (although not in the same magnitude as your submission) using a different sorting algorithm. Thanks again!

[raptor_sof]

I ve precalculated the fibonacci no. along with mod operation.
Then i used merge sort to sort the output.
Getting TLE...plzz help
Here's my code:

// dp[]: contains fibonacci no.
// temp[]: chunk of array that is to be sorted [a to (a+c)]
// b[]:temporary array used for merge sort.

include

define ll long long int

int mod=100000;
int dp[1100001],b[1100001],temp[1100001];
void mergesort(int a[],ll,ll);
void merge(int a[],ll,ll,ll);
void mergesort(int a[],ll i,ll j)
{
ll mid;
mid=(i+j)/2;
if(i>=j)return;
mergesort(a,i,mid);
mergesort(a,mid+1,j);
merge(a,i,j,mid);
}
void merge(int a[],ll i,ll j,ll mid)
{
ll l,k;
l=i;
k=mid+1;
while(i<=mid && k<=j)
{
if(a[i]<=a[k])
b[l++]=a[i++];
else
b[l++]=a[k++];
}
if(i>mid)
for(;k<=j;)b[l++]=a[k++];
else
for(;i<=mid;)b[l++]=a[i++];
for(i=0;i<=j;i++)
temp[i]=b[i];
}

main()
{

int t,k;
ll a,c,i,count;
dp[0]=0;dp[1]=1;
for(i=2;i<1100001;i++)
dp[i]=(dp[i-1]+dp[i-2])%mod;
scanf("%d",&t);
k=t;
while(t--)
{
count=0;
scanf("%lld %lld",&a,&c);
for(i=a;i<=a+c;i++)
temp[i-1]=dp[i-1];
if(c==0)
printf("Case %d: %d",k-t,dp[a-1]);
else
{
mergesort(temp,a-1,a+c-1);
printf("Case %d: ",k-t);
for(i=a;i<=a+c;i++)
{printf("%d ",temp[i-1]);count++;if(count==100)break;}
}
printf("\n");
}
return 0;
}