10914 - Abundance and Perfect Numbers

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

Moderator: Board moderators

EfEr
New poster
Posts: 5
Joined: Thu Sep 22, 2005 8:56 pm
Location: Bucuresti, Romania
Contact:

Post by EfEr » Fri Sep 23, 2005 6:47 pm

instead of keeping a huge array for those numbers, try storing them in a balanced binary search tree (you can use map in C++) there are only about 700000 of them or so... then do a binary search when computing the result

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

problem again with java code

Post by Sedefcho » Thu Dec 15, 2005 6:02 pm

Can someone who knows java very well suggest a way to avoid the compile error I get while submitting the code below? The code is perfectly legal java code but apparently the compilator used by the online judge supports just a subset of the java language and unfortunately it is a not a very well defined subset.

I already wrote about that in some thread a lot of time ago or ... I think I even sent a mail to the administrators of the ACM UVA site. No progress though. So if someone has a workaround solution any ideas are welcome.

And as I stopped getting mails from Judge after each submission (when did the judge stop sending e-mails? ) I can really do nothing about my problem :)

The code below is rubbish I know it is full of old methods which are not called any more and so on. I am just experimenting. But it works on my machine. And if I optimize it a bit it will get ACC. Of course first I have to get rid of the "Compile Error"

Code: Select all


import java.util.Hashtable;
import java.util.StringTokenizer;

interface Entry {
	Entry findFisrtNotGreaterThan(int N);
	void add(int v, int ind);
	void print();
	void accumulateSum(int limitNumber, long[] Sum);
}

class BST_Entry implements Entry {

	public int value = -1;
	public int index = -1;
	
	public Entry[] children = new Entry[2];
	
	BST_Entry(){
		super();
		this.value = -1;
	}
	
	public Entry findFisrtNotGreaterThan(int N){
		if (this.isEmpty()) return null;
		
		if (this.value == N) return this;
		
		if (this.value < N){
			// (this.value < N)
			return this;
		}else {
			// (this.value > N)
			if (this.children[0]==null) return null;
			else return this.children[0].findFisrtNotGreaterThan(N);
		}
	}
	
	public void add(int v, int ind){
		if (isEmpty()){
			this.value = v;
			this.index = ind;
		}else{
			if (this.value>v){
				if (this.children[0]==null){
					this.children[0] = new BST_Entry();
				}
				this.children[0].add(v, ind);
			}else if (this.value<v){
				if (this.children[1]==null){
					this.children[1] = new BST_Entry();
				}
				this.children[1].add(v, ind);
			}
		}
	}

	public void print(){
		if (this.children[0]!=null){
			this.children[0].print();
		}
		if (!isEmpty()){
			System.out.print(this.value + " ");
		}
		if (this.children[1]!=null){
			this.children[1].print();
		}
	}
	
	public boolean isEmpty(){
		return this.value == -1;
	}
	
	public void accumulateSum(int limitNumber, long[] Sum){
		if (!this.isEmpty()){
			if (this.value <= limitNumber){
				int i = this.index;
				Sum[0] += 
					( (2*Main10914.almost_odd_d[i]-1)*(Main10914.almost_odd_p[i]+1) - 2*Main10914.almost_odd_primes[i] );				
			}
		}
		if (this.children[0]!=null) this.children[0].accumulateSum(limitNumber, Sum);
		if (this.children[1]!=null) this.children[1].accumulateSum(limitNumber, Sum);
	}
}


class Main {

	public static final int INPUT_MAX = 10000000;
	public static final int N_MAX = 5000000;
	public static final int COUNT_PRIMES_TO_N_MAX = 2000000;
	
	public static byte[] ind_prime = new byte[N_MAX+1];
	public static int[] primes = new int[COUNT_PRIMES_TO_N_MAX+1];
	public static int count_primes = 0;
	
	public static Hashtable answersHT = new Hashtable();
	
	// The number 737058 is the count of all 
	// almost odd primes which are <= 10 000 000
	public static int[] almost_odd_primes = new int[737058];
	public static int cnt_almost_odd_primes = 0;
	
	public static int[] almost_odd_d = new int[737058];
	public static int[] almost_odd_p = new int[737058];
	
	public static Entry tree = new BST_Entry();
	
	public static void main(String[] args) {
		sieve();
		
		int N = 0;
		long S = 0;
		long[] arr_deg2 = new long[1];
		long[] arr_prime = new long[1];
		long p;
		long degree_of_two;
		String answer = null;
		
		int m = 0;
		for (int n=3; n<=INPUT_MAX/2; n++){
			if (isPrime(n)){
				m = n;
				while (2*m <= INPUT_MAX){
					m *= 2;
					tree.add(m, cnt_almost_odd_primes);
					almost_odd_primes[cnt_almost_odd_primes] = m;
					almost_odd_d[cnt_almost_odd_primes] = m / n;
					almost_odd_p[cnt_almost_odd_primes] = n;
					cnt_almost_odd_primes++;
				}
			}
		}
		
		// System.out.println();
		// tree.print();
		// System.out.println();
		
		// System.out.println("Count Almost Odd Primes = " + cnt_almost_odd_primes);
		
		// quickSort(almost_odd_primes, cnt_almost_odd_primes ); // , almost_odd_d, almost_odd_p);
		
		while (true){
			N = Integer.parseInt(getNextToken());
			if (N==0) break;
			answer = (String)answersHT.get(new Integer(N));
			if (answer!=null){
				System.out.println(N + " " + answer);
				continue;
			}
			
			S = 0;
			BST_Entry ptr = (BST_Entry)tree.findFisrtNotGreaterThan(N);
			long[] Sum = new long[1];
			ptr.accumulateSum(N, Sum);
			System.out.println(N + " " + Sum[0]);
			answersHT.put(new Integer(N), Sum[0] + "");
			/*
			for (int i=0; i<cnt_almost_odd_primes; i++){
				if (almost_odd_primes[i]<=N){
					S += 
					( (2*almost_odd_d[i]-1)*(almost_odd_p[i]+1) - 2*almost_odd_primes[i] );
				}
			}
			*/
			// answersHT.put(new Integer(N), S+"");
			// System.out.println(N + " " + S);
		}
		
		// System.out.println("Count Primes = " + count_primes);
		// System.out.println("SIEVE FINISHED!");
	}

	static boolean isAlmostOddPrime(int n, long[] arr_deg2, long[] arr_prime){
		if (n % 2 == 1) return false;
		int deg2 = 0;
		long deg_of_two = 1;
		while (n % 2 == 0){
			deg2++;
			n /= 2;
			deg_of_two *= 2;
		}
		if (!isPrime(n)) return false;
		
		arr_deg2[0] = deg_of_two;
		arr_prime[0] = n;
		
		return true;
	}
	
	static boolean isPrime(int n){
		if (n<=N_MAX){
			return ind_prime[n]!=0;
		}
		for (int k=1; primes[k]*primes[k]<=n; k++){
			if (n % primes[k] == 0) return false;
		}
		return true;
	}
	
	private static void sieve(){
		int cnt_primes = 0;
		for (int i=1; i<=N_MAX; i++){
			ind_prime[i] = i % 2 == 0 ? (byte)0 : (byte)1;
		}
		ind_prime[1] = 0;
		ind_prime[2] = 1;

		primes[1] = 2;

		cnt_primes = 1;

		int k = 3;

		while (true)
		{
			while (k<=N_MAX && ind_prime[k]==0) k++;
			if (k>N_MAX) break;
			cnt_primes++;
			ind_prime[k] = (byte)1;
			primes[cnt_primes] = k;
			int t = k + k;
			while (t<=N_MAX){
				ind_prime[t] = 0;
				t += k;
			}
			k++;
		}
		count_primes = cnt_primes;
	}
	
	
	
	/*** QUICK SORT METHODS ***/
	private static void quickSort(int[] arr, int cnt){
		quickSortAsc( arr, 0, cnt - 1 );
	}

    private static int x = 0;
    private static int t = 0;

	static void quickSortAsc(int[] arr, int l, int r)
	{

	       int i, j;

	       i = l-1;
	       x = arr[r];
	       for (j=l; j<=r; j++){
	       	if (arr[j]<=x){
	               i++;
                   // Swap the elements
                   // arr[i] and arr[j]
	               t = arr[i];
	               arr[i] = arr[j];
	               arr[j] = t;
	           }
	       }

	       if (i==r) i--;
	       if (l<i){

	            quickSortAsc( arr, l, i);
	       }
	       if ( (i+1) < r){

	            quickSortAsc( arr, i+1, r);
	       }
	}
    /*** END - QUICK SORT METHODS ***/

	
	// I/O - RELATED METHODS
	static String line = null;
	static StringTokenizer st = null;
	
	static String getNextToken(){
		while (st==null || !st.hasMoreTokens()){
			line = readLn(80);
			if (line==null) return null;
			st = new StringTokenizer(line);
		}
		return st.nextToken().trim();
	}
	
	public static String readLn (int maxLg){
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        try{
            while (lg < maxLg){
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }catch (java.io.IOException e){
            return (null);
        }
        if ((car < 0) && (lg == 0)) return (null);
        return (new String (lin, 0, lg));
    }
	
}


[/b]

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

Post by Darko » Fri Dec 16, 2005 12:03 am

I can't see anything wrong there... Have you tried it without the interface? Or maybe moving the BST class to the end of file (because there is no public class, maybe it's confused by something or other).

I highly dislike their compiler. Especially when using Vectors and I type add() instead of addElement() and spend half an hour trying to figure out what that thing didn't like.

Oh, I didn't see anything like this in your code, I think, but sometimes things like tree.root.add() stuff doesn't work, you have to do something like - Node root = tree.root; root.add();
Maybe try splitting this up a bit, I really don't know:
if (this.children[0]!=null) this.children[0].accumulateSum(limitNumber, Sum);
Of course, you have jdk 1.1 docs, right?

Darko

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Dec 16, 2005 10:46 am

Well, using Vector.add() is forbiden and this makes sense as actually this method did not exist in JDK 1.1. I have the JDK 1.1. docs that's not a problem.

The interface, yes, I first did not have an interface but I think the judge does not like code like

Code: Select all

class A { 
   private A refA = null;
   // ... more ...  
}
I mean it does not like when a class definition contains instance variables of the same class. That's why I introduced this interface trying to find a workaround for this situation. And ;) yes, in my first attempts to submit the code the helper classes were after the Main class.
Nothing works :)

I didn't know chains of references like

Code: Select all

a.b().c.d() 
could also cause problems. Pitty that I don't get even an e-mail
to see what my compile error is.

Thanks anyway and if you have any other ideas just let me know.

Regards.

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

Post by Darko » Fri Dec 16, 2005 6:21 pm

I got a CE last night for this line:

Code: Select all

while((line = readLine()).length() == 0);
It compiled the long version:

Code: Select all

while(true){
    line = readLine();
    if(line.length() > 0) break;
}
I know that add() wasn't there in 1.1, but is easy to miss that one. Oh, and they said they supported 1.2 (add() was.. err.. added in 1.2) which is BS.

Darko

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

..

Post by helloneo » Sun Dec 18, 2005 8:34 am

anybody would tell me how to get "almost odd prime numbers" up to 1000000 fast..?

my code is like this.. so slow.. i can't pass TLE ;

Code: Select all

        for (i = 6; i <= 10000000; i += 2) {
                if (is_almost(i)) {
                        ...
                        ...
                }
 

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Dec 18, 2005 7:09 pm

helloneo wrote:
anybody would tell me how to get "almost odd prime numbers" up to 1000000 fast..?
I use a kind of sieve to get all "almost odd prime numbers" up to 10000000. Then I precalculate the sum (to speed this I precalculate all divisors of all power of two in the rank [1..10000000]), then binary search.

My approach is not the fastest (works about 3.460 secs).

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Dec 18, 2005 9:54 pm

Emilio wrote: I use a kind of sieve to get all "almost odd prime numbers" up to 10000000. Then I precalculate the sum (to speed this I precalculate all divisors of all power of two in the rank [1..10000000]), then binary search.

My approach is not the fastest (works about 3.460 secs).

thanks for help..
i finally got AC.. in 4.504 secs..
but i failed to use sieve to get almost odd prime numbers..
i got memory limit exceeded for that..

Code: Select all

        bool is_almost[10000001];
        memset(is_almost, false, sizeof(is_almost));
        for (i = 1; i < cnt_prime; i++) {
                j = prime[i];
                j <<= 1;
                while (j <= 10000000) {
                        is_almost[j] = true;
                        j <<= 1;
                }
        }

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Dec 27, 2005 3:00 am

MLE, why?
Your bool array is 10^7 size, and this don't give MLE.
To make a good sieve think about that an almost odd prime number have only an odd prime factor.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Tue Dec 27, 2005 1:27 pm

Emilio wrote:MLE, why?
Your bool array is 10^7 size, and this don't give MLE.
To make a good sieve think about that an almost odd prime number have only an odd prime factor.
I'm too lazy to check whether I'm right, but probably the compiler didn't do any "bit packing", thus the array of 10^8 bools is equally big as an array of 10^8 ints, which makes it approximately 40MB.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Wed Dec 28, 2005 3:02 am

The size is 10^7, and I'm sure is approximately 10MB.
bool type is processed a byte like.
By other hand 10^8 ints is about 400MB.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Dec 28, 2005 11:07 am

Emilio wrote:The size is 10^7, and I'm sure is approximately 10MB.
bool type is processed a byte like.
By other hand 10^8 ints is about 400MB.
Yeah, you are right. The 10^8 was a typo, it should've been 10^7, as you say. I checked it and you are right, the array size is about 10 MB.

The code snippet above makes the impression that the array is_almost is a local variable in some function. However, in this case the program would immediately end with a segmentation fault, as the default stack size is only 8 MB. Maybe the UVa judge can detect and report this as a MLE, but if this is the case, the program should behave in the same way (i.e., crash) on your computer.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Thu Dec 29, 2005 11:17 pm

I thought 10^8 was a typo :D
But really is strange that MLE, how you say would must be RE.
Maybe I'll test the judge behaviour with a similar case, but now I'm lazy too :wink: .

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

Post by Darko » Tue Jan 10, 2006 6:53 am

I had some trouble with this problem, maybe this I/O can help someone:

Code: Select all

1
5
6
7
10
20
27
28
29
1000000
9999990
9999992
9999994
9999996
9999998
10000000
0

Code: Select all

1 0
5 0
6 0
7 0
10 -2
20 0
27 -6
28 -6
29 -6
1000000 -13478901222
9999990 -1136675933068
9999992 -1136677183052
9999994 -1136677183052
9999996 -1136677183052
9999998 -1136682183048
10000000 -1136682183048
Darko

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sat Jan 14, 2006 9:27 pm

I got AC in about 2 seconds, but in the ranklist I saw quite a few ppl solving it in less than 1 sec. Can anyone give me a hint on the better solutions? I am unable to find a trick myself :(

My approach to the problem is as follows:

1. Generate all primes upto 5000000
2. Getting the almost prime numbers. (Each almost prime no is of the form 2^n * primeNumber)
3. Sort the numbers
4. Run a loop through the array to precalculate the abundance value.
5. Binary search to get abun(n) for any given n

I will be very happy if anyone gives me a hint about his/her better solution. Thanks in advance.
Where's the "Any" key?

Post Reply

Return to “Volume 109 (10900-10999)”