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

My trouble with Cats

I've struggled a lot with Cats, with multiple codes and submits, across a huge time period, with a wide range of WAs and TLs. The latter is the major part of the problem, that needed a different approach to solving. After getting value of n, my code is pretty simple. I tried getting n by:

• pow(): this failed since pow(5, 2) gave me 24 and I got a shock of my life... great learning though. :)
• multiple loops: w and h are worker cats and height of initial cat given in input. tempW and tempH are temporary copies of these to work with in the loop. Outer while loop checks that both w and n are divisible by "potential" n & n+1 respectively. If they are, then the inner two for() loops check that w is the same power of "potential" n as h is a power of "potential" n+1. This check is by i == j at the end of the following code, meaning both have same depth (so that when the height of cats reduces to one from given height, the cats would have reached the given number of worker cats). As simple as that. It all works fine with all the test cases I could find online. Unfortunately, I didn't generate the highest number that int can go to, to test, perhaps thats why I get a TL! Commented it out.
  

 /*            while(n++) {
                if(w%n || h%(n+1))
                   continue;
                //cout << "n= " << n << endl;
                m = 2;
                tempW = 1;
                for(i= 0; tempW < w; i++) {
                    tempW *= n;
                }
                if(tempW != w)
                    continue;
                tempH = 1;
                cout << i << endl;
                for(j = 0; tempH < h; j++)
                    tempH *= (n + 1);
                if(tempH != h)
                    continue;
                //cout << j << endl;
                if(i == j)
                    break;
            }
*/

• logarithms: I gave up the above and went exponential via logarithms. :) Now, I am bad at math... so, I'd to read up how logs work and look into some code. I worked the below given beautiful three line code manually through a calculator understanding how it works... and then, voila, Judge gave an AC!! This simple method of using the loghw, "logarithmic ratio of h to w" as a perfect guide for the ratio of their respective factors n+1 and n to have, is sheer beauty! You just have to see that the difference between the two ratios is 0 (or so close to zero, as in < 1^-10). I have worked through some examples of n w.r.t. loghw, and saw that as the "potential" n changes from "real" n, (whether one lesser or one higher than needed), the difference in the mentioned logarithmic ratios is enormous (here, > 1^ -10). Its so simple, yet so powerful; I am happy to learn. :)
  

            double loghw = log (h) / log (w);
            while (fabs(log(n + 1)/log(n) - loghw) > 1e-10)
                n++;

The remaining part of the code is to calculate nw, non-working cats and th, total height of all cats. I use tempN and tempH as copies of n and h for the loops. Since the depth for h to reach 1 is same as 1 cat to become w:

for tempH:= h to 1

• Reduce tempH by a factor of n+1
• Increase tempN:= 1 by a factor of n (no. of cats will automatically reach w). 
• Increase nw:= by tempN, the no of cats at each depth. (I remove no. of cats at the last depth from this after the loop since they are working ones, to get non-working cats)
• Increase th, total height:= by height x no. of cats at each depth. (Since I started with value of h for th in the beginning, I knock it off in the end. Might work if start with 0 for it and not remove h off it in the end).

Simple enough, I guess.
        nw = 1;
        tempN = 1;
        tempH = h;
        th = h + w;
        for (i = 0; tempH > 1; ++i) {
            th += tempH * tempN;
            tempN = n * tempN;
            nw += tempN;
            tempH /= (n+1);
        }
        nw = nw - tempN;
        th -= h;

        cout << nw << " " << th << endl;

    }
}

Looks like all "worked hard like a dog" chasing the "cats in the hat". :)