11353 - A Different Kind of Sorting

[armansuleimenov]

Here is the problem: http://icpcres.ecs.baylor.edu/onlinejud ... 11353.html

I got TLE twice. But I don't see how I can optimize my solution. Could you please help me with this. Here is my code (w/o includes and other formal things):

Code: Select all

#define Fori(i,a,b) for(int i = a; i < (int)b; ++i)
#define M 2000001
int a[M];
int b[M];

int f(int x)
{
	int res=0;
	int xx=x;
	while(!(xx%2))
	{
		++res;
		xx/=2;
	}
	int lim=(int)sqrt((double)x)+1;
	for(int f=3;f<=lim && xx>1;f+=2)
	{
		while(!(xx%f))
		{
			++res;
			xx/=f;
		}
	}
	if(xx!=1) ++res;
	return res;
}

bool cmp(int x,int y)
{
	if(b[x]!=b[y])
		return (b[x]<b[y]);
	else
		return x<y;
}

int main ()
{
  a[0]=0;
  Fori(i,1,M) a[i]=i;
  b[0]=0;
  Fori(i,1,M) b[i]=f(i);
  int n;
  int c=1;
  sort(a,a+M,cmp);
  while(cin >> n)
  {
		if(n==0)break;
		printf("Case %d: %d\n",c,a[n]);
		c++;
  }
  return 0;
}

Title editied by Moderator

[shanto86]

use seive like method and dont sort them explicitly.

[sonyckson]

Well, i got a TLE coding the same, so i tought a way to obtain first all the primes ( using sieve ), and after that, knowing all the primes between 2 and 2*10^6 in an array, looking for the quantity of primes in each descomposition. Anyway, my code runs in 4.5 sec... and if my memory dont fail, the limit is of 5.0... can anyone tell a better solution?

[helloneo]

I precalculate the number of prime factors for [1 ~ 2000000] (something like seive approach) and do quicksort..
It runs under 1 sec..

[sonyckson]

I see.. i suppose my problem is that i look for the quantity of primes ( in the descomposition ) after running sieve... now i realize everything can be done "on the fly" of sieve.. thanks.

[srrajesh]

I use "sieving like method" to solve the problem. I think it takes less than 2 seconds to construct the number of prime factors of all the numbers. But I am getting TLE, probably because I search the whole list of numbers from 1 to 200000 for each input case. Is there any good approach to solve the problem?
Here is my code:

Code: Select all

Code removed.

Please help me!
Thanks in advance for your help.

[srrajesh]

haha, I find that, when I put,
char arr[MAX];
int s[MAX];
globally, then there is no run time error! Really strange. But I get WA!
I think there must be some problem with the logic I use.
Can anyone tell me, what is the output for the following inputs?
2000000
1999999
And I want to know for input case we have the output as 4, and 8.
I guess it is 148935 for 4, Am I right?

If there is any tricky input, let me know.
Thanks in advance for your reply.

Here is my code:

Code: Select all

Code removed.

[helloneo]

Well.. you have a minor mistake..
Try this case..

10
100
1000
0

My output is..

Case 1: 23
Case 2: 523
Case 3: 7907


PS. remove your code after AC ..

[Robert Gerbicz]

Some input/output:

Code: Select all

148935
556219
1999999
2000000
0
Case 1: 4
Case 2: 8
Case 3: 1048576
Case 4: 1572864

[srrajesh]

Well.. you have a minor mistake..

Thank you very much. Indeed, it was a minor mistake!
I should have read the problem statement properly.
Anyway, I got AC now.

[RC's]

hm... Does the judge rejudge the submissions for this problem ?
I saw my code was AC but I wonder why it now get WA...

Can anyone help me with sample I/O ? I have tried all sample I/O posted above...

in the following input :

Code: Select all

123456
234567
345678
456789
567890
0

my program gives

Code: Select all

Case 1: 1632893
Case 2: 216267
Case 3: 585079
Case 4: 120433
Case 5: 497108

Is my output wrong ?

[helloneo]

in the following input :

Code: Select all

123456
234567
345678
456789
567890
0

my program gives

Code: Select all

Case 1: 1632893
Case 2: 216267
Case 3: 585079
Case 4: 120433
Case 5: 497108

Is my output wrong ?

Well.. My AC program gives..

Code: Select all

Case 1: 1632893
Case 2: 390713
Case 3: 934571
Case 4: 1492761
Case 5: 45546

Hope this help..

[RC's]

hm... i still don't know why my code gets WA

First, I generate prime numbers and then use a sieve-like method to generate sorted array.. And I wonder why my program gets wrong output after a big number of input (compared with helloneo)

this is my program

Code: Select all

removed after AC

[Sedefcho]

RC, your program doesn't generate the numbers in the right order.

Your program stores the following data
( after the precalculation step):

array[148935] = 4
array[148936] = 6
array[148937] = 10
array[148938] = 14

Where is number 9 ? It should come before 10. That's because
9 is smaller than 10 although both 9 and 10 have 2 prime factors:
10 = 2 * 5,
9 = 3 * 3.

Think about the exact order in which you generate
the numbers in the array, this order is not correct.

So your problem is not related to big numbers only.

Regards,
Peter Petrov
(Sedefcho)

[Sedefcho]

Although I know what RC's problem is, I myself still cannot figure
out a way to generate the numbers in the right order.

What is my idea? Well, firstly let's suppose we know
all the primes up to 2,000,000. Generating them is an easy task.
Secondly, let's suppose we know all the numbers in the set S[k]
where by S[k] I denote all the numbers which have exactly k
prime factors. Also let's suppose the numbers in the set S[k] are
in the right order (as defined by the problem statement).
Now it is obvious that the numbers in the next
set S[k+1] can be generated using this formula:
S[k+1] = { x * y | x belongs to S[k], y is prime} (!!!)
So it is easy to generate the set S[k+1] but the problem is that
it is not easy to generate the numbers in this set in the right order.

Here I don't see any law for generating the numbers
from S[k+1] in the right order. What do I mean?

In the formula (!!!) given above, we can start using the
number 2 as a prime (y=2) and we can generate some numbers
from S[k+1] of the form 2 * x (x belongs to S[k]).

But we don't know how many numbers x (and which) to
use from S[k] before taking another prime (for example y=3)
and generating some more numbers from S[k+1] using the
formula 3 * x (again x belongs to S[k]).

Then again we don't know how many numbers to generate this way,
before taking the prime 5 and generating some more numbers
of the form 5 * x (x belongs to S[k] ).

Also I noticed that from time to time we need to go back i.e.
change a bigger prime (for example 3) with a smaller one (2).
Example: In the process of generating S[2] (i.e. all numbers
which have exactly two prime factors) after we have
generated the number 3 * 3 = 9 we need to go back one
step (so to say) and pick up the prime 2 and generate
the number 2 * 5 = 10. Both 9 and 10 belong
to S[2] but 9 should come before 10.

And so on.

I also tried another approach - first precalculate the number
of prime factors of each number from 1 to 2,000,000
(I do this step pretty efficiently). Then I just store the numbers
from 1 to 2,000,000 in an array and just sort the array
(the comparison logic is described in the problem statement)
using quick sort or heap sort but this seems to take too
long and won't pass the time limit for sure.

So any hints (even on abstract level) for generating the
numbers in the correct order are highly welcome.

Thanks in advance.