algorithm
I think that answer is amount of digits |A+B-C|
Sorry, it's incorrect
Edited by author 03.01.2007 23:51
Re: algorithm
Posted by
svr 24 Jan 2007 11:02
It's impossible to know all nice formulas.
I used DIVIDE AND CONCURE for which problem is excellent
but Challenge-team don't allow us recursion
and converting the algorithm to iteration made it less clear.
Re: algorithm
Posted by
svr 24 Jan 2007 11:26
To compare different algo
some test using my Ac program here:
99
1
300
2
1111
66
7777
12
1111
66
77777
46
100
1
9999
61
99
99
1000
-1
1
80
201
12
4
8
99
15
345321543
123215642
876543129
21
Re: algorithm
Posted by
Lomir 24 Jan 2007 19:41
My program pass all this tests. However i got WA6... :(
Re: algorithm
Posted by
svr 24 Jan 2007 23:09
Be must careful with first digits.
They can't be =0.
But if digit only one?
Acording to problem statement it also <>0 because it also first.
But I gueesd that for 1 digit it can be =0 and have AC.
Re: algorithm
Can anybody give me a hint how to solve it?
Re: algorithm
Posted by
svr 24 Jan 2007 23:41
Most simple to understand- use Divide and concure method.
You solve the problem separetely for 1 and 2 halfs
of strings and add optimal results.
Blocs must be agreeed by means of common Carry
fron 2 to 1.
Exit from recursion when size of block=1,or only one digit.
It this case use optimization by full search.
Shortly to say it is problem from positioning number systems.
Re: algorithm
Posted by
svr 25 Jan 2007 00:14
Continuation.
Alternative method- dynamic programming.
We start witn 1-digits blocs. Let N- numder of them.
We solve the problem for each one and store result in array.
After we buld N/2 blocs with size 2 using array for 1-blocs. Result write to the same array.
And so on: building blocs, containing 4,8,.. digits.
Finally we will have one block with size N and array[0]- the
answer. To agreed blocs on each stage array must depend
also on in and out carries of each block.
Edited by author 25.01.2007 00:15
Edited by author 25.01.2007 00:15
Re: algorithm
Thank you for explanation!
Re: algorithm
Or this problem can be solved using DP digit by digit, without any blocks)
Re: algorithm
Posted by
Fox 10 Apr 2008 20:32
=) very thanks to all who give sample tests and explain recursive algorithm!!! At last I've got AC
Re: algorithm
345321543
123215642
876543129
21
that test is wrong.
correct answer is 20.
Re: algorithm
svr, thanks for your tests! They helped me to find a bug :)
(I could allow leading zero for the 3rd number)
Re: algorithm
My AC solution never allows first digit to become zero, even for one-digit-long numbers.
Also, BE AWARE that there are test(s) with leading zeroes, at least test #15.
Re: algorithm
My AC solution gives 21 as well. Check if you do not allow carryover past leading digit, leading zero, etc...