ACM UVa 369 Combinations

I was looking into this 369: Combinations problem where very very large integer is being used for you have to get combinations C by solving n choose m, where largest n = m= 100. Approximately, we know that the largest no. of digits occur at around 100 choose 50. However, there's a tricky line that says that the value of C will not cross 32-bit long int! That means that such input cases will not exist which will cause a final overflow of long int. However, there is no saying that the intermediate numbers that you use, rather, the numerators and denominators as below won't cross 32-bit. The formula is already given to be:

C = n! / ( (n-m)! x m!)

At first instance it seems scary, but if you recall that each factorial starts with 1 x 2 x 3 x... x n or m or (n-m), then we can put together simple high school math and see that the common numbers from numerator and denominator get cancelled out! (By the way, that last one isn't out factorial. :-P)

If we write the above another way,

C = (n! / m!) / (n-m)!

Clearly, all terms from n! upto m! can just get cancelled out right away. Now, lets see them separately as numerators and denominator so:

num = n! /m! and den = (n-m)!

Taking an example of n = 10, m = 6:

num = (1x2x3x4x5x6x7x8x9x10) / (1x2x3x4x5x6)
= 7x8x9x10
= (m+1) x (m+2) x ... x n

den = 1x2x3x4
= (n-m)!

As we can see, we don't need to deduce both multiplications as of yet, since there are many more reductions in numerator to happen. Moreover, for small nos, there won't be any overflow, but for larger ones there will be. That is, instead of multiplying first, we could see if we can divide individual terms first. Here come the vectors to hold individual terms.

Now, we could use two vectors of long long int for num and den. Then, although its a lot more times than perhaps needed, the following reduction helps:

• For each term i of num
• For each term j of den
• If i is divisible by j
• replace i from num by i/j
• erase j from den
• if i is 1, erase i

Just to see how good it works, lets take our 100 choose 50 example:
Before:
num = 51x52x53x54x55x56x57x58x59x60x61x62x63x64x65x66x67x68x69x70x71x72x73x74x75x76x77x78x79x80x81x82x83x84x85x86x87x88x89x90x91x92x93x94x95x96x97x98x99x100

den = 2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23x24x25x26x27x28x29x30x31x32x33x34x35x36x37x38x39x40x41x42x43x44x45x46x47x48x49x50

After:
num = 2x53x3x2x59x6x61x2x9x8x65x3x67x2x3x2x71x6x73x2x5x2x77x3x79x5x3x2x83
x4x85x2x87x2x89x5x91x2x93x2x95x4x97x2x3x5

den: 25x28x30x32x36x39x40x42x45x48x50

Possibly the numerator spills over a long long int, but such a test case won't exist in the input. You get the idea here that the numerator has terms that divides the denominator, those can go too if you check for the divisibility other way round.

Cheers!

ACM UVa runtime

Its been a long time, over 10 years, since I first came to know of ACM UVa and solved 100: 3n +1 problem. Of course, as its easy to recall now, those were the days when I was a novice is programming, even with NCST's MGPTs. (BTW, sadly I didn't know of ACM UVa back when in NCST and struggled much with MGPTs). I am still learning, and will always be, but I've come a long way from then. In this current streak of UVa madness, I solved over 50 problems and didn't just solve it the way I used to earlier. Instead, I focused on bettering the runtime. Solving it is one thing, solving it well is quite another.

Now that the solved numbers are up in a short time, I could also look back and resolve the ones that had taken longer to solve. I decided to check whatever has taken over a second of runtime and see if I could improve those. 3n+1 was one, Cats was another and so was Software CRC too. I knew Cats is a little difficult to revisit now, having solved it only in this streak, so I decided to redo the others. 3n+1 had taken over 3.268s, while Software CRC was timed at 1.391s!! On recoding and resubmitting, the improved timings are 0.052s and 0.082s, respectively. These are pretty satisfying values and the ranking improved, thereby. Someday, I might improve slightly over a sec taken by Cats.

Its been fun and I hope to keep this streak going as long as I can.

ACM UVa 673 Parenthesis Balance

The Parenthesis Balance problem, though a simple one to solve, gave me lot of WAs. I wanted to solve it without using a stack at first, using the same input string that the parenthesis is scanned into. After 6-8 WAs, I finally gave up and wrote a stack using an array. I still got a WA! Now, this is something I'd suspected earlier on, but lazed about fixing it. Finally, the fix was simple and I tried to post this onto the UVa forum, but the forum is refusing to log me in for some reason.

Although the problem statement says that the we can assume that the string size will not exceed 128, we ought to consider that there may be trailing spaces exceeding 128 after the no of test cases are given! Now this seems like a deliberate thing that the UVa guys have done as one of their tricks. :) Of course, this is not an issue if you're using C++ I/O calls and cin.ignore(), but for C I/O calls, most likely you're using gets(), getline() or the safer, fgets(), unless, worse yet, you used a getchar()! In any case, if you're lazy like me, you'd be using the same character array that you've reserved for reading the input parenthesis string. And if that, the size needs to be more than 129 (one that you will have definitely added for newline character). After multiple failures, I changed the size to 1024 and both, the stack as well as non-stack version got AC. :)

Cheers! C++, ... er, C you around. :P