305 - Joseph

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Nice :)

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

Darko

AdamWG
New poster
Posts: 3
Joined: Sun Jul 16, 2006 7:32 pm

Post by AdamWG »

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:

Post by mf »

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).

AdamWG
New poster
Posts: 3
Joined: Sun Jul 16, 2006 7:32 pm

Post by AdamWG »

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
Location: Nova Scotia, Canada
Contact:

305 .. Cheating judge?

Post by LithiumDex »

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?
- Chris Adams

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari »

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

Post by mmonish »

>>>LithiumDex
U should remove ur code from the post. Otherwise spoilers can take the chance.

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

305 WA

Post by Suyash.Upadhyay »

hello all,
I have solved this problem and getting correct output but still WA.
I am unable to understand, please help me.

Code: Select all

#include<iostream>

}
Thanx in advance.

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

Post by mmonish »

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].

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

@mmonish

Post by Suyash.Upadhyay »

Thanx
I got AC

Unioeste_Brazil
New poster
Posts: 2
Joined: Tue Aug 21, 2007 4:09 am

Post by Unioeste_Brazil »

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

For k = 1 the answer should be 2. And don't forget to remove your code after getting accepted.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 3 (300-399)”