367 - Halting Factor Replacement Systems

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

Moderator: Board moderators

Post Reply
PdR
New poster
Posts: 24
Joined: Mon Dec 30, 2002 4:27 am

367 - Halting Factor Replacement Systems

Post 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?)

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

Post by potato »

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post 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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post 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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post 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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post 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 :)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post 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 :(

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post 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.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post 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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post 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


windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post 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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post 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?

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post 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

Post Reply

Return to “Volume 3 (300-399)”