very tight timelimit

General topic about Valladolid Online Judge

Moderator: Board moderators

Post Reply
jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

very tight timelimit

Post by jah » Sun Jul 29, 2007 12:14 am

I believe the timelimit for some of the new problems is very tight.

For problem 11250, I am running my programs in a P3 800MHz and I get the answer for m = 1000000000 n = 1000000000 in 0.024 secs (obviously for 2000 cases it's not enough).

Probably I should write a new optimized BigInt library which is something I don't want to do right now.
Last edited by jah on Sun Jul 29, 2007 12:29 am, edited 3 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jul 29, 2007 12:22 am

I have the same complain. 11248, 11250. Too tight time limits. About 11248, I believe the judge code would get TLE, too.
Ami ekhono shopno dekhi...
HomePage

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Sun Jul 29, 2007 2:05 am

Jan wrote:I have the same complain. 11248, 11250. Too tight time limits. About 11248, I believe the judge code would get TLE, too.
For 11250 I wouldn't say that. I've solved that problem only in 0.113 sec. ( after the contest).

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Jul 30, 2007 5:12 am

i get TLE with 11250
I'm pretty sure my bigint is too slow, because all I do is to calculate the closed form solution. It would be nice to double the time limits.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Mon Jul 30, 2007 6:14 am

The time limits and data were prepared for faster server at WACO. Once the UVa is shifted to faster server this problem will no longer be there.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Avoid Division

Post by baodog » Mon Jul 30, 2007 11:39 am

Most likely your division is slow for reducing the fraction.
You can avoid long division using binary gcd, where
you only have to do shift operations.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Jul 30, 2007 12:01 pm

I was too lazy to use binary gcd, but I should've tried.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Mon Sep 17, 2007 1:59 pm

I have similar problem with 11218 ("Flipull"). Time limit is 3 seconds, but if you see on statistics -- all existing solutions take more than 3 seconds.
This is very confusing. How to know whether the time limit is OK and there are no problems related to outdated data?
@+!
DitriX

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Mon Sep 17, 2007 9:15 pm

ditrix wrote:I have similar problem with 11218 ("Flipull"). Time limit is 3 seconds, but if you see on statistics -- all existing solutions take more than 3 seconds.
This is very confusing. How to know whether the time limit is OK and there are no problems related to outdated data?
And if you see the submission times you will observe that all of them done on the previous judge, and that was about 10/3 times slower. That's why the previous time limit was 10 sec. but now on the faster judge the new time limit is 3 sec.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Sep 17, 2007 11:14 pm

By the way, 11218 is not "Flipull". Flipull is 11213 and it isn't that easy to get AC on the old judge (the guys that solved it is one of the best around here), and I actually don't know if it is possible to get AC on the new judge.

However, anyone with an reasonable algorithm for 11218 "KTV" should be able to solve it in time. Mine was quite slow and it still around 0.8 secs on the old judge.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Tue Sep 18, 2007 9:03 am

Thanks for your answers. Indeed, I meant the problem #11213 (Flipull). And actually I expected the submission times should be different...
So, is it correct to say, that if the submission is old, it would be 3/10 faster on the new judge?

And regarding old time limits. I am still confused about statistics for problem #11213 (Flipull): there is solution which runs in 12 secs... And I don't see indications about time limit in the problem description. May be it was 30 secs? And in this case, now it should be 9 secs and not 3 secs...
@+!
DitriX

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Thu Oct 04, 2007 7:15 am

It was 30 seconds... I don't know how soon they will
fix the time limits. Maybe not for awhile ... possibly until
they rejudge each problem one by one.

Post Reply

Return to “General”