11353 - A Different Kind of Sorting

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

Moderator: Board moderators

armansuleimenov
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

11353 - A Different Kind of Sorting

Post by armansuleimenov » Sat Nov 24, 2007 4:10 pm

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Nov 24, 2007 5:19 pm

use seive like method and dont sort them explicitly.
Self judging is the best judging!

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sat Nov 24, 2007 5:23 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sat Nov 24, 2007 8:42 pm

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

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sat Nov 24, 2007 8:50 pm

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.. :D thanks.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Sat Nov 24, 2007 8:53 pm

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.
Last edited by srrajesh on Sun Nov 25, 2007 2:16 pm, edited 1 time in total.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Sat Nov 24, 2007 9:37 pm

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.
Last edited by srrajesh on Sun Nov 25, 2007 2:17 pm, edited 1 time in total.

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

Post by helloneo » Sat Nov 24, 2007 10:22 pm

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Sat Nov 24, 2007 11:03 pm

Some input/output:

Code: Select all

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

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Sun Nov 25, 2007 2:16 pm

helloneo wrote: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
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's » Wed Jan 16, 2008 4:58 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Jan 16, 2008 5:54 pm

RC's wrote: 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
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's » Wed Jan 16, 2008 6:07 pm

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
Last edited by RC's on Sun Sep 11, 2011 11:56 am, edited 1 time in total.

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

Post by Sedefcho » Sat Feb 09, 2008 5:51 pm

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)

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

some thoughts

Post by Sedefcho » Sun Feb 10, 2008 2:30 pm

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.

Post Reply

Return to “Volume 113 (11300-11399)”