OJ Board

Posted: **Tue Apr 11, 2006 7:47 am**

you can alse speed it up with this code:

for(num=5,f=2;num<REMAX;num+=f,f=6-f)

You should handle 3 separatly. It is faster than yours by 33%.

Posted: **Wed Apr 12, 2006 7:58 pm**

After skipping TLE and getting 5 consecutive WA, this frail vessel being emptiest again and again, is fillest ever with fresh life~!

I got accepted!

Thanks a looooooot moha! thanks a loooooooooooooot!

Posted: **Sun May 07, 2006 1:23 pm**

Hi all!

Well, I was searching around for sieve optimisation, and i was found it here:
http://online-judge.uva.es/board/viewto ... ight=#6457

I implemet this, but I got TLE (> 30sec). It works perfect at me.

Here is the code:

Code: Select all

#include <cstdio>
using namespace std;

#define MAX	100000000
#define HALF	50000000
#define SQRT	5000
#define SIZE	MAX / 16 + 2

char SITO[SIZE];

#define NTH(n)           ((n) & 7)
#define ISPRIME(n)    SITO[n >> 4] & (1 << NTH (n >> 1))

bool isprime (int n)
{
	if (n == 2) return true;
	else if (!(n & 1)) return false;
	else return ISPRIME (n);
}

void init (void) 
{
	memset (SITO, 0xff, sizeof SITO);		
	SITO[0] = 0xFE;
	for (int i = 1; i < SQRT; i++)
		if (SITO[i >> 3] & (1 << NTH (i)))
			for (int j = 2 * i * (i + 1); j < HALF; j += 2 * i + 1)
				SITO[j >> 3] &= ~(1 << NTH (j));
}

/*** CUTTED ***/

Thank you in advance!

PY

Posted: **Sun May 07, 2006 2:36 pm**

Your program takes more than a second to find answer to 99999999 (after preprocessing).
You have to solve such tests (when n is odd) much faster.

Also, your program can produce wrong answers -- read the last paragraph of the "Output" section of the problem statement.

Posted: **Sun May 07, 2006 4:17 pm**

Hello, mf!
Thank you for the reply. I fixed my main function, but it's still TLE.
I tested big integers now, it's secondary fast.

Code: Select all

/*** CUTTED ***/

Any ideas?

Posted: **Sun May 07, 2006 8:43 pm**

Code: Select all

if (!(n & 2))

What is this line supposed to do?

Posted: **Mon May 08, 2006 9:23 am**

Thank you, mamun. I fix that, but it is still TLE.

I tested it on input 99999999, it gets immediatly the result.
Sieving takes about 3-4 secs at me (2.8GHz).

Can sieve be faster?

Regards,
PY

Posted: **Mon May 08, 2006 11:14 am**

Seive may be faster but that is not the major problem here. Post your modified code. You'll get enough informartion if you search the forum for this problem.

Posted: **Mon May 08, 2006 2:27 pm**

My modified code:

Code: Select all

/*** CUTTED ***/

Posted: **Mon May 08, 2006 3:09 pm**

Try with an even number say 100000000. Since your machine is very fast, so you may not understand the delay unless you give a lot of inputs of such.

You must understand that if an odd number is to be sum of two primes then one of them has to be 2, otherwise not. So avoid calculation involving odd numbers.

Code: Select all

for (int i = n / 2 - 1; i >= 0; i -= 2)

i can be even here for some even n and continues to be even.

Posted: **Mon May 08, 2006 6:26 pm**

Thank you for reply!

If I understood You, Mamun, here

Code: Select all

      if (n % 2 == 1 && isprime (n - 2))
      {
         printf ("%d is the sum of %d and %d.\n", n, 2, n - 2);
         goto end;
      }

I check wheter is number is odd, and if it is odd hen I do what You said.

i can be odd here for some even n and continues to be odd.

I assumed it must be odd because the even number must be of two odd numbers. Now I'm a little bit confused. I can't remember other way for finding is the number sum of two primes.

Posted: **Tue May 09, 2006 9:22 am**

Sorry, I was little wrong, I've corrected my previous post's last line.

What I actually wanted to mean is

Code: Select all

for (int i = n / 2 - 1; i >= 0; i -= 2)

value of i can be even for even n like 99999998 and continues to be even. So your loop runs to the end and consumes time.

You'll get wrong answer too.

Code: Select all

if (n % 2 == 1 && isprime (n - 2)) 
{ 
   printf ("%d is the sum of %d and %d.\n", n, 2, n - 2); 
   goto end; 
}

What if n is odd and (n-2) is not prime?

Posted: **Tue May 09, 2006 4:05 pm**

Mamun, thank You very much. I finnaly got AC (about 7.8 sec). :D

The problem was in 9999998. Anybody who stuck in TLE and has got fast sieve should try this input.

Thank you again!

Posted: **Thu May 25, 2006 10:32 pm**

Hi fellows!

I need to hold a variable balance in my balanced search trees, but to make it int or even signed char would be no good - I read in my book that I can make it "bit field with sign".
Please, tell me how to do it.
I know now (thanks mf

) how to make that kind of thing with arrays (for Seat of Eratosphean

), but whaT is "signed bit field"?

Thank you.

Posted: **Fri May 26, 2006 7:52 pm**

Hi everyone!

My definition of bitfield:

Code: Select all

typedef struct{
	signed char s:1;
}bit_field;

int main(){
	bit_field  sign;
	return 0;
}

How to assign to sign variable 0 and 1?

OJ Board

10311 - Goldbach and Euler

10311 TLE with optimized sieve

Fix