305 - Joseph

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Nice

Note that m%(n+1) is either 0 or 1 (roughly 6 times faster?)

Darko

New poster
Posts: 3
Joined: Sun Jul 16, 2006 7:32 pm
mf wrote:Actually there is a way to solve this problem without precalculation!

Here's how I've solved it, but I'm too lazy to re-derive my solution now.
The code solves the case k=13 in less than a second.
<snip>
My solution is very similar to this, although slightly more optimized (since it eliminates many m values in advance). I compiled and ran both your version and my version on my machine, and mine was about .1 second faster (0.5 seconds vs. 0.4 seconds, roughly), to compute all cases (1 through 13).

However, when I upload my code to the online judge, it exceeds the time limit. Anyone else having the same problem?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Input may contain repeated values of k, and if your code recomputes output every time then it'll easily time-out. (Just imagine a file with, say, a thousand of 13's).

New poster
Posts: 3
Joined: Sun Jul 16, 2006 7:32 pm
mf wrote:Input may contain repeated values of k, and if your code recomputes output every time then it'll easily time-out. (Just imagine a file with, say, a thousand of 13's).
Aha, I hadn't thought of that. I'll try this.

Thanks.

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Contact:

305 .. Cheating judge?

The following code:

Code: Select all

``````#include <iostream>
using namespace std;

int main (void)
{
int k;
while ((cin>>k)&&k)
{
int p = k*2;
int m;
for (m=k; ; m++)
{
int x=p;
int y=(m-1)%x;
while (y>=k && x>k)
{
x--;
y = (y-1+m)%x;
}
if (x==k)
break;
}
cout << m << endl;
}
}``````
Solves all possible cases in <3 seconds on my computer, and get's TLE

I used a lookup table, and got AC... But that's not why I'm posting... Is the judges computer that much slower, or is there repeating test cases in the judge's input file?

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
as judge input consists of many repeating test cases so you need to store the result in a table otherwise you will be definately get TLE due to repeated computation....

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
>>>LithiumDex
U should remove ur code from the post. Otherwise spoilers can take the chance.

New poster
Posts: 5
Joined: Sat Jun 02, 2007 6:03 pm

305 WA

hello all,
I have solved this problem and getting correct output but still WA.

Code: Select all

``````#include<iostream>

}``````

Suyash
Last edited by Suyash.Upadhyay on Sun Jun 03, 2007 1:09 pm, edited 1 time in total.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Code: Select all

``long int p[13];``
This portion of ur code is not correct. If u decleare an array of size 13 u can't access index arr[13].

New poster
Posts: 5
Joined: Sat Jun 02, 2007 6:03 pm

@mmonish

Thanx
I got AC

Unioeste_Brazil
New poster
Posts: 2
Joined: Tue Aug 21, 2007 4:09 am
accepted
Last edited by Unioeste_Brazil on Wed Oct 03, 2007 8:47 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm