10837 - A Research Problem

Observer · Post by **Observer** » Tue Mar 22, 2005 8:33 pm

Hi,

I can't get accepted for this problem. I've written a slow brute-force to check against my WA code, and they give the same answer for every random input I generated.

It's interesting to see that my code dies for exactly one input case at the judge! (By "die" I mean it fails to give a matching n. I've put loops in my code to verify this

) So could anyone please give me some good input/output? Thanks very much.

- EDIT -

Found a pretty stupid flaw... Will try to fix that tmr~

- EDIT -

Fixed. Got AC. Some I/O here:

Code: Select all

Code: Select all

Case 1: 10000000 10165751
Case 2: 100000000 100064101
Case 3: 99450756 99460729
Case 4: 99038478 99252847
Case 5: 993012 994009
Case 6: 800000 1000625
Case 7: 8000000 10000625

ardiankp · Post by **ardiankp** » Wed Mar 23, 2005 4:37 am

Hehe.. the interesting is.. how do you know that the judge output didn't match with your output? :S

Sorry, newbie here :$:$

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Mar 23, 2005 4:47 am

What he means with "matching n" is, that he didn't found a n such that phi(n) = number given in input. It is easy to check if you found a solution on every judge input or not.

Sedefcho · Post by **Sedefcho** » Wed Apr 20, 2005 12:31 am

Can someone who has an ACC program
post some sample I/O on this problem ?
This could be useful to me.

I have some bug in my program
as for some values of PHI_N my program
generates correct answer but for others does not.

For instance on the sample I/O it only fails for
PHI_N = 5 000 000.
Which is quite interesting to me.
Apparently my algorithm works for many test case
but also fails on some ( maybe less ) test cases.
Apparently I miss something special here.

Thanks in advance.

Here is some I/O from my program which currently gets WA.

INPUT

Code: Select all

OUTPUT

Code: Select all

Case 1: 12 13
Case 2: 24 35
Case 3: 10 11
Case 4: 8 15
Case 5: 1000 1111
Case 6: 2000 3333
Case 7: 1500 1661
Case 8: 2500 2761
Case 9: 10000 10201
Case 10: 22000 22339
Case 11: 40000 40501
Case 12: 100000 100651
Case 13: 101010 0
Case 14: 2200000 2205901
Case 15: 2200050 0
Case 16: 2280960 2283989
Case 17: 2400000 2400001
Case 18: 2500000 2560451
Case 19: 3000000 3004751
Case 20: 5000000 7681353
Case 21: 70000000 70280251
Case 22: 70000505 0
Case 23: 90000000 90026501
Case 24: 90003003 0
Case 25: 100000000 100064101

Who can tell me in which test cases I have erros and in which
I give correct answers.

I assume that I print 0 if and only if the number given
is not equal to PHI_N for any N ?!
Well, this could be one of the weakest points in my program.

Does someone have such values for PHI_N for which for sure
exists N such that PHI ( N ) = PHI_N ? it would be interesting
what my program will print for them...

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Apr 20, 2005 6:53 am

I deleted the inputs for which there exists no solution.
My output for the others is:

Code: Select all

Case 1: 12 13
Case 2: 24 35
Case 3: 10 11
Case 4: 8 15
Case 5: 1000 1111
Case 6: 2000 2525
Case 7: 1500 1661
Case 8: 2500 2761
Case 9: 10000 10291
Case 10: 22000 22339
Case 11: 40000 40501
Case 12: 100000 100651
Case 13: 2200000 2205901
Case 14: 2280960 2283989
Case 15: 2400000 2400001
Case 16: 2500000 2562541
Case 17: 3000000 3004751
Case 18: 5000000 6265625
Case 19: 70000000 70280251
Case 20: 90000000 90026501
Case 21: 100000000 100064101

Btw, don't try to look for a pattern or something, I would be astonished if there is one. A search is ok for this problem (of course not a naive search).

Observer · Post by **Observer** » Wed Apr 20, 2005 7:42 am

Sedefcho, please tell us your algorithm to this problem.

If you're using a search, then most probably your search isn't deep enough (i.e. you end your search too soon). That's my mistake in my old code.

P.S. It's too bad that my I/O above doesn't help...

Sedefcho · Post by **Sedefcho** » Wed Apr 20, 2005 10:40 am

Adrian, thanks for the I/O.

Observer,
My algorithm is as follows. I have a function called
calc_N_from_PHI_N(long long num). It is a recursive function.

Suppose we are given the value PHI_N = num. Now we
want to know the minimal N such that PHI (N) = num.

0) I check if num==1 and in that case I return 1.

1) I check if (num+1) is prime. In that case the
value I return for calc_N_from_PHI_N(num) is num+1.

2) If (num+1) is not prime I do the following.
Firstly, I find jMax = sqrt(num). Then in a cycle for all j = 2,3,...,jMax
I do the following: IF ( num % j == 0 )
THEN I calculate ( via a recursive call ) the
value

Code: Select all

res(j) = calc_N_from_PHI_N(j) * calc_N_from_PHI_N(num/j)

3) I then chose the mininal resMin of all these res(j) and that is the
return value of calc_N_from_PHI_N(num).

4) If my resMin variable remains unchanged in the cycle I do for j
/ see step 2) / then I simply return 0.

That is my algorithm.
There's some logical problem with it , that's obvious
from Adrian's I/O.

Observer · Post by **Observer** » Wed Apr 20, 2005 3:22 pm

Hi, Sedefcho.

Sedefcho wrote:2) If (num+1) is not prime I do the following.
Firstly, I find jMax = sqrt(num). Then in a cycle for all j = 2,3,...,jMax
I do the following: IF ( num % j == 0 )
THEN I calculate ( via a recursive call ) the
value
Code: Select all
res(j) = calc_N_from_PHI_N(j) * calc_N_from_PHI_N(num/j)

This process has some mistakes. I believe that the line you quoted may make your program give incorrect calc_N_from_PHI_N(num) for some simple cases. Here's one wrong output of yours:

Code: Select all

Case 9: 10000 10201

Note that 10201 = 101 * 101, thus phi(10201) = 100 * 101 = 10100...

Sedefcho · Post by **Sedefcho** » Wed Apr 20, 2005 3:34 pm

Yes, OK

This is exactly the test case I also payed most attention to.

The question is : is there a relatively easy way to correct
this algorithm ?
I am asking this as it runs quite fast in my opinion.

The only problem is it produces wrong results
for some test cases

Observer · Post by **Observer** » Wed Apr 20, 2005 4:20 pm

That means, your program should NOT split 10000 into 100 * 100 (product of identical numbers) in that case... It isn't very hard to fix this, is it?

(Think: how about spliting it as 10 * 1000? Does this "N" we get satisfy phi(N) = 10000?)

Sedefcho wrote:The question is : is there a relatively easy way to correct this algorithm ?

Yes there is. And I guess you basically know how

Sedefcho · Post by **Sedefcho** » Wed Apr 20, 2005 4:56 pm

Observer,

I changed it this way:

res1 = calc_N_from_PHI_N(j) ;
res2 = calc_N_from_PHI_N(num/j);

if (res1,res2)=1 / if they are relatively prime /
then res(j) = res1 * res2;
else res(j) = 0;

This way I managed to fix mistakes resulting in finding
an answer (an output number) which is
smaller than the real answer(the correct output number).

For instance, now for input = 10000
my program gives output = 10291
and not like before output = 101 * 101 = 10201

But I have also cases where I miss solutions ?!
I mean cases in which my output is a bigger
number than the correct number which should be
outputed.

I just don't find 2525 for input=2000 let's say.
For input=2000 now my program prints 3333.
Same with input=20. In this case my program
prints 33 and not 25 as it should.

I think I do not handle correctly just one case now - when the
input number has the form (P-1) * (P^k ) where P is prime.
In that case I should directly return ( P^(k+1) ).

I wouldn't mind some more hints from you though

Sedefcho · Post by **Sedefcho** » Wed Apr 20, 2005 5:04 pm

Well ...

Code: Select all

I think I do not handle correctly just one case now - when the 
input number has the form (P-1) * (P^k ) where P is prime. 
In that case I should directly return ( P^(k+1) ).

That is also not true.

Counter example: input number = 32 = (2-1) * 2^5

I should not print 64 because 51 is a smaller number
whose PHI equals 32. I don't know if it is the smallest.

domino · Post by **domino** » Thu Apr 21, 2005 12:58 pm

Is there any solution for this input

Code: Select all

16842752
0

My program works for all test cases posted here, but i still receive Wrong Answer. I believe the above is in the judge's input, but my program says there is no solution for it. Any help would be great!

Sedefcho · Post by **Sedefcho** » Thu Apr 21, 2005 1:55 pm

My "WA" program also says there is no solution for
this input number. If that could be of some help to you

domino · Post by **domino** » Thu Apr 21, 2005 2:09 pm

The output for that case is 33817088 , check it out because it is worth it. My algorithm is very similar to yours (actually i started solving this task after reading your posts) and i finally got accepted after fixing my program to work for this case (although it was pure luck, i don't know how to prove that the changes i made cover all possible cases). Good luck!