Surya said:
I am new to solving programming puzzles in contests like SPOJ
where I thought to use C a while..
Often these puzzles throw very large numbers -- of order 1000000
digits which gets me crazy. When constructing algorithms I face
trouble with handling these datasets and manipulating them.
It would be very nice if you can give me some pointers, tips or
links for handling such situations.
Most likely the problems you're looking at don't require the
full generality of arbitrary precision arithmetic. I suspect in
fact that is part of the point of the puzzle - to figure out how
to deal with limited operations on large integers, especially if
all the numbers involved are non-negative.
For example, here is one way to define a simple structure for
holding large non-negative integers:
typedef unsigned long Index;
typedef struct {
Index top_index;
unsigned digits[ 334000 ]; /* in 1,000's */
} LargeNumber;
This structure will hold numbers up to one million digits
(or just slightly larger), and on a typical implementation
where unsigned ints are four bytes will occupy approximately
1.34 MB. With these definition in hand, we could then write
static LargeNumber factorials[101];
static void
compute_factorials_up_to_100(){
Index i;
factorials[0].digits[0] = 1;
factorials[0].top_index = 0;
for( i = 1; i <= 100; i++ ){
factorials
= factorials[i-1];
multiply_by( &factorial, i );
}
}
If you can now write the 'multiply_by()' function, which
multiplies a LargeNumber by a small integer argument (it should
be easy if the multiplier is less than 1000) -- and in the
process adjusting elements of the digits[] array member and
sometimes also the top_index member -- at that point it should be
easy to solve the "Small factorials" problem at SPOJ. Having
computed the table of factorials, for each input simply index
the pre-computed table and print out the answer.
Note that the numbers here are represented in units of 1,000's,
so three decimal digits per array element, and with the low
order digits having smaller indices. So to print out the
number you would first print the value for the element at
the high end, eg, if we are working on factorials[k], we
would start with
factorials[k].digits[ factorials[k].top_index ]
and work down from there, until we get to factorials[k].digts[0].
Hopefully this is about the right level of detail so you can
fill in the rest.
Incidentally, having a million digits available is way more than
is needed to deal with numbers only as large as 100 factorial.
But the amount of space used and the time needed should be well
within the limits of the SPOJ problems. (Disclaimer: I have no
experience submitting anything to SPOJ, so this remark may
reflect unrealistic assumptions on my part as to what is being
measured by the limits SPOJ states.)
Other large number problems may very well need different
representations. Figuring out which representations are
suitable for which problems is an important part of solving
the problem.
