10914  Abundance and Perfect Numbers
Moderator: Board moderators
problem again with java code
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 emails? ) 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"
[/b]
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 emails? ) 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 = l1;
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));
}
}
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:
Darko
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:
Of course, you have jdk 1.1 docs, right?if (this.children[0]!=null) this.children[0].accumulateSum(limitNumber, Sum);
Darko
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
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
could also cause problems. Pitty that I don't get even an email
to see what my compile error is.
Thanks anyway and if you have any other ideas just let me know.
Regards.
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 ...
}
Nothing works
I didn't know chains of references like
Code: Select all
a.b().c.d()
to see what my compile error is.
Thanks anyway and if you have any other ideas just let me know.
Regards.
I got a CE last night for this line:
It compiled the long version:
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
Code: Select all
while((line = readLine()).length() == 0);
Code: Select all
while(true){
line = readLine();
if(line.length() > 0) break;
}
Darko
..
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 ;
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)) {
...
...
}
helloneo wrote:
My approach is not the fastest (works about 3.460 secs).
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.anybody would tell me how to get "almost odd prime numbers" up to 1000000 fast..?
My approach is not the fastest (works about 3.460 secs).
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;
}
}
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 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.
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.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.
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.
I had some trouble with this problem, maybe this I/O can help someone:
Darko
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

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
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.
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?