10311 - Goldbach and Euler

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

Moderator: Board moderators

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

hi serur,
once i waste a lot of time working bit field in this way... but i couldnt make it working... then for a while i used to remember the way mf described about changing value... then when i read the bit field things well in a language book, i became clear.
if you dont mind, in my humble opinion, it would be much wiser to read the basic works of bit field, then look at what mf tried to tell. Then go ahead and work on simple bit fields...

you can also have a look here ... http://online-judge.uva.es/board/viewtopic.php?t=10418

i dont know well about balanced search trees, but i think 'bit field with sign', here sign means for flagging... not anything other... and chars are signed by default...
fahim
#include <smile.h>

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Code: Select all

struct{ 
   signed char s:1; 
}bit_field;
Don't you think here bit_field takes just 1 bit of memory but the whole word which maybe 4 bytes. Assigning value to this bit_field is just like struct structures.

Code: Select all

bit_field  sign;
sign.s=1;
But I'm sure you want memory efficiency. Try to understand what mf has written. Read more about low level programming to clear yourself.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Hi fellows!

Thank you smilitude and mamun for sympathy :)

mamun wrote:

But I'm sure you want memory efficiency

Yes, all I want is memory efficiency

but:

mamun wrote:

Don't you think here bit_field takes just 1 bit of memory but the whole word which maybe 4 bytes

Yes, you are right, and I WANT ONLY 1 BIT MEMORY FOR SIGN AND NO MORE!
Also, I'd like to use int as base instead of char.

Well, UNIX is only 10% assembly and 90% in C! So I'll work hard to understand these low-level stuffs. But a tiny hint is welcome, all the same :)
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 »

please i got many wa.......
This is my even part is it wrong

Code: Select all

		if(n % 2 == 0)	//So even //Test all possiblities eficiently
		{
			bool flag = false;
			int mid = n / 2;	//Any number is divided to 2 sides 
			
			if(mid != 2 && mid % 2 == 0) 
				--mid;	//Start from odd and use -=2 Optimization
			
			for(int k = mid; k > 0; k -= 2)//(p2-p1) is positive and minimized
			{
				if(isprime(k) && isprime(n - k))
				{
			//		if(k < n-k)
						possible(n, k, n - k);
			//		else
			//			possible(n, n - k, k);
					flag = true;
					break;
				}
			}
			if(!flag) 
				cout<<n<<" is not the sum of two primes!"<<"\n";
}

Please i need some test cases
also what is the output for

Code: Select all


1
2
3
4
5
6
7
8
9
10
11
12
Sleep enough after death, it is the time to work.
Mostafa Saad

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

Post by Darko »

In my solution I would check if mid is even, and if yes do mid--, if not mid-=2. (without that mid != 2 part)
And my loop would go down to 3 (not to 1).

For that input:

Code: Select all

1 is not the sum of two primes!
2 is not the sum of two primes!
3 is not the sum of two primes!
4 is not the sum of two primes!
5 is the sum of 2 and 3.
6 is not the sum of two primes!
7 is the sum of 2 and 5.
8 is the sum of 3 and 5.
9 is the sum of 2 and 7.
10 is the sum of 3 and 7.
11 is not the sum of two primes!
12 is the sum of 5 and 7.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 »

THANKS THANKS THANKS THANKS THANKS THANKS
THANKS THANKS THANKS THANKS THANKS THANKS

I got accepted NOWWWWWWWW FINALYYY

http://acm.uva.es/problemset/usersjudge.php?user=8957
Sleep enough after death, it is the time to work.
Mostafa Saad

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

why getting MLE??

Post by kolpobilashi »

plz tell wht this code's giving me MLE??? :(

Code: Select all

cut
thanx in advance..
Last edited by kolpobilashi on Wed Oct 25, 2006 11:27 am, edited 2 times in total.
Sanjana

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

isn't it very simple? ur prim[] array is taking more than 47MB, where the judge memory limit is 32MB
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

:( yes i understood the problem...but the thing is what should i do then.??
if i don't generate the primes before.....and each time check... that will certainly give TLE.
plz suggest me..
Sanjana

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

kolpobilashi wrote::( yes i understood the problem...but the thing is what should i do then.??
if i don't generate the primes before.....and each time check... that will certainly give TLE.
plz suggest me..
use bits. here is a sample if u want 2 access the X'th bit of a char array.



Code: Select all

#define MAX 100000000 
char  flag[MAX/8]; 
#define SETBIT(X) (flag[X/8]|=1<<(X%8)) 
#define GETBIT(X) ((flag[X/8]&(1<<(X%8)))?1:0) 

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

if you know bitwise operation in C, it will be rather easy using char array as sunny said. better process is using char array of size[MAX/16]. it deals with only odd numbers, as you know even numbers are not prime(except 2). 1st character of the char array represents whether 1, 3, 5, 7, 9, 11, 13, 15 are prime or not, 2nd character represents 17,19,...,31, etc. you can have a look at http://www.shygypsy.com/tools/number.cpp to get the C code
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

thanx sunny & ayon...this bitwise operation seems much complicated but it really works :)
Sanjana

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm

10311-GOLBACH AND EULER!!! PLZZ HELP!

Post by <:3)~~ »

I am using Miller's Primality test even then its TLE!!! And when i used sieve its MLE!! I read previous posts but i cant understand how they r managing not to MLE!! some one plzz help!
Last edited by <:3)~~ on Wed Dec 27, 2006 6:33 pm, edited 1 time in total.

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm

Post by <:3)~~ »

why isnt any one replying!!!!!! :cry:

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

Post by Jan »

Dont open a new thread unless there is none. First search your problem. And when creating a new thread try to write the subject like '10311 - Goldbach and Euler'.

Remember that you can use bitwise sieve.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 103 (10300-10399)”