367 - Halting Factor Replacement Systems

PdR · Post by **PdR** » Wed Aug 20, 2003 4:03 pm

After rejudge...

I tried to find some errors on my code, and after fixing some minor errors (negative numbers in input)... and getting WA again several times, I must ask:

What changed?

I find it really strange as several of us use bignumbers functions that have been tested countless times... and yet only one got AC.

Maybe some error have been introduced in the input? (before rejudging?)

potato · Post by **potato** » Wed Aug 20, 2003 5:32 pm

After rejudgment, I got WA, too.
And I fixed some problem in my problem, and got TLE......
I am quite puzzled now......

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Aug 21, 2003 3:10 pm

After rejudgement I got TLE ... I use own BigInteger class ... Maybe exist case in which computation in very expensive ??

Best regards
DM

Per · Post by **Per** » Fri Aug 22, 2003 8:21 am

I've tried to solve the problem with bigints, which gave TLE, long longs which (unsurprisingly) gave WA, and by not doing the arithmetic at all, just increasing/decreasing exponents of the prime factors involved (a lot faster for at least some test cases), which also gave TLE.

The accept-rate has turned really low, so I wonder if there isn't something weird with the judge's new input file.

little joey · Post by **little joey** » Fri Aug 22, 2003 1:39 pm

I turned from AC to TLE too.
After thinking a lot about it, I came up with special cases that require millions of iterations before halting at the correct answer. I guess they put these kind of cases in. They can't be solved in the 'normal' way (by doing the iterations, but have to be 'short circuited' first. But I have no idea how to do the short circuiting...

Code: Select all

10
1977326743 11
1220703125 21
1162261467 10
2147483648 6
22 11
33 11
55 11
2 4
3 9
5 25
1
2
0

Takes several seconds to complete on my machine (which is much faster than the judge's). It is not too difficult to see the correct answer (11) for an intelligent human being, but putting that intelligence into a program is another thing.
So, if you find a way around, please let us know...

-little joey

windows2k · Post by **windows2k** » Wed Jun 23, 2004 12:31 pm

little joey wrote:I turned from AC to TLE too.

Hello Little Joey, I saw you have solved the problem.
Could you say what's the trick of the problem?
Thx

windows2k · Post by **windows2k** » Sat Jul 23, 2005 4:09 am

windows2k wrote:
little joey wrote:I turned from AC to TLE too.
Hello Little Joey, I saw you have solved the problem.
Could you say what's the trick of the problem?
Thx

Hello, could some one give me some input/output?
I got WA all the time

little joey · Post by **little joey** » Sat Jul 23, 2005 9:52 am

Numbers can get quite big. I use 9*32 decimal digits, and I just verified that 9*16 digits is not enough.

windows2k · Post by **windows2k** » Sun Jul 24, 2005 8:32 am

little joey wrote:Numbers can get quite big. I use 9*32 decimal digits, and I just verified that 9*16 digits is not enough.

My BigNumber is up to 500 digits.
And I factorize all the numbers and save it.
repeat find the pattern and modify it.
so I don't need BigNumber division,but still get WA.

little joey · Post by **little joey** » Sun Jul 24, 2005 10:17 am

It seems to me that factorisation is a lot more work than straight forward mul and div functions on bigints, but it should also give the correct results.
I use 32 bits unsigned integers, but I don't know if that is essential. Anyway, you can try this I/O:

Code: Select all

2
4 5
2 3
11
1
2
4
8
16
32
64
128
256
512
1024
3
4000000000 7
9 2000000000
3 1000000000
6
3
9
27
81
243
729
0

Code: Select all

FRS #1:
     1 becomes 1
     2 becomes 3
     4 becomes 5
     8 becomes 15
     16 becomes 25
     32 becomes 75
     64 becomes 125
     128 becomes 375
     256 becomes 625
     512 becomes 1875
     1024 becomes 3125

FRS #2:
     3 becomes 1000000000
     9 becomes 2000000000
     27 becomes 3500000000
     81 becomes 7000000000
     243 becomes 12250000000
     729 becomes 24500000000

windows2k · Post by **windows2k** » Sun Jul 24, 2005 4:51 pm

little joey wrote:It seems to me that factorisation is a lot more work than straight forward mul and div functions on bigints, but it should also give the correct results.
I use 32 bits unsigned integers, but I don't know if that is essential. Anyway, you can try this I/O:

I passed all the input above,but still get WA.
Maybe there exists something I miss.
Could you give more input/output? Thx

little joey · Post by **little joey** » Mon Jul 25, 2005 9:13 am

Hmm. I can't think of any more special cases.
Are you sure your bigint routines are correct?

Code: Select all

9
3 3999999979
5 3899999977
7 3799999969
11 3699999967
13 3599999933
17 3499999927
19 3399999923
23 3299999921
2 3199999909
1
2230928700
0

Code: Select all

FRS #1:
     2230928700 becomes 1238334030415726211389803597948181596613864974230560058715783575024329812254333037530542839654194687491949

You don't forget to print a blank line after each data set, even the last one?

windows2k · Post by **windows2k** » Mon Jul 25, 2005 1:48 pm

little joey wrote:Hmm. I can't think of any more special cases.
Are you sure your bigint routines are correct?
You don't forget to print a blank line after each data set, even the last one?

Thx...I found I foget replace all int to unsigned int , that results WA