Page 1 of 1
367 - Halting Factor Replacement Systems
Posted: Wed Aug 20, 2003 4:03 pm
by PdR
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?)
Posted: Wed Aug 20, 2003 5:32 pm
by potato
After rejudgment, I got WA, too.
And I fixed some problem in my problem, and got TLE......
I am quite puzzled now......
Posted: Thu Aug 21, 2003 3:10 pm
by Dominik Michniewski
After rejudgement I got TLE ... I use own BigInteger class ... Maybe exist case in which computation in very expensive ??
Best regards
DM
Posted: Fri Aug 22, 2003 8:21 am
by Per
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.
Posted: Fri Aug 22, 2003 1:39 pm
by little joey
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
Posted: Wed Jun 23, 2004 12:31 pm
by windows2k
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
Posted: Sat Jul 23, 2005 4:09 am
by windows2k
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
Posted: Sat Jul 23, 2005 9:52 am
by little joey
Numbers can get quite big. I use 9*32 decimal digits, and I just verified that 9*16 digits is not enough.
Posted: Sun Jul 24, 2005 8:32 am
by windows2k
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.
Posted: Sun Jul 24, 2005 10:17 am
by little joey
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
Posted: Sun Jul 24, 2005 4:51 pm
by windows2k
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
Posted: Mon Jul 25, 2005 9:13 am
by little joey
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?
Posted: Mon Jul 25, 2005 1:48 pm
by windows2k
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