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". :)

How to brick your SE X8 (E15i)... and recover it.

Obviously, how-to for bricking your Android phone is meant as an unintentional happening here, but it helps to know what kind of stupidity leads to such disastrous effects. I could give many reasons as to how I managed to do so, such as being sleepy, unalert, whatever, but the fact remains that I was stupid enough to click a wrong version of ROM to download for my kernel. To be specific, I downloaded GingerDX v029 (to upgrade from my earlier v028) meant for Alfs/nAa kernel than my stock SEMC kernel. For one, I didn't know that there are two different versions (my ignorance) and for another, the fellows who named the file, in their wisdom, decided that one file should be called GingerDX-v029-shakira.zip and the other as GingerDX-v029-shakira-stock.zip (a nomenclature mistake, I must say). Of course, I accept all the blame for being unalert, yet I wish to point out that if a person were to use the file looking at its name, maybe years later, still he should know that just shakira means Alfs/nAa! Thats very unlikely. Be it as it may, lets just say that I bricked the X8 when I loaded the shakira ROM instead of shakira-stock ROM onto my SEMC stock kernel.

For those who don't know what a (soft) bricked phone looks like, it looks just like an X8 (no, really, it doesn't look like a brick :P) which shows a Sony Ericsson logo that comes up during the boot cycle and just that. It hangs in there, without even the power off working. You ought to remove the battery to let it power down. For all practical purposes, its a brick.

The options available for you to unbrick the X8 (using "Windoze") are:

(If you have Sony PC Companion installed, try Option 2 directly).

1. Flashtool: 
1. Download Flashtool (107MB) (or a newer available version) & install it.
2. Download stock ROM E15i_X8i_2.1.1.A.0.6_Baseband_015.7z (or your E15a, etc, version of X8 or a valid custom ROM such as shakira-stock) and unzip it, getting its ftf file.
3. Copy/move that file to Flashtool's /firmware folder.
4. Run Flashtool/drivers/Flashtool-drivers.exe, choose your X8 phone drivers and install them.
5. Run Flashtool.
6. Choose to flash, selecting X8. Follow Flashtool instructions on when to power off X8/connect/unplug USB cable/hold back button of X8/plug USB cable, etc.
7. If this works, well and good, unplug USB cable, power up X8 and you're done (Note: First boot takes a long time, giving symptoms similar to a bricked phone!
8. If it doesn't boot up even after a long time or Flashtool gave an error at step 6 above as to drivers not being found, USB debugging being off, 2011 mode blah-blah or whatever, follow next set of instructions below.
2. Sony PC Companion (PCC):
1. If you don't have it already, download PCC (26MB) & install it
2. Run it & try its update/ repair options.
3. If that doesn't unbrick the X8, move on reading below to last option that worked for me.
3. Sony Upgrade Service:
1. Download Update Service (38.1MB) or later version & install it. Takes a while if the service app itself has another update due.
2. Run Update Service application, selecting the device as X8 from many SE phones listed. Connect the X8 device via USB cable following instructions on when to power off, hold the back button, etc.
3. Let it install drivers.
4. Now, you have a choice to go back to option 1 of Flashtool and burn available stock or custom ROM, or continue with this service and let it update the X8 after downloading 120MB stock ROM.
5. If you go with latter, let the update download finish and flash your connected X8.
6. Unplug the USB cable, power up X8 and wait long for first run. You'd be back with factory X8 settings.

Hope this blog entry helps some other sleepy head like me, who'd rather have postponed upgrading his X8 to a day when he felt more wakeful! :)

Happy unbricking! Cheers!!

Sony Ericsson X8

Be it after a long delay, I finally did catch up with Android by getting myself a Sony Ericsson X8 phone. Why X8, some may ask? I want to start by saying that I've a bias towards Sony devices. I like their sound quality more than anything else. I've used an SE phone before, a T610 and except for the battery, it was simply great. On Android, I do know that SE has been crawling releasing 2.1 Eclair on new launches, when the competition has moved beyond 2.2 Froyo onto 2.3 Gingerbread. X8 specifically has a low memory with its standard release giving only 128MB, while even LG's Optimus gives 512MB in a similar pricing! Then again, as they say... its a Sony! :) Worse yet, unless one gets a newer manufacture, 2.1 is available only as an upgrade to 1.6 Donut.

That said, I still chose SE X8 because it is a good phone and although SE has officially announced that there shall not be further upgrades to X8, XDA forum currently has both Froyo and Gingerbread releases for X8! There are many other flavours also, including one in between, called FroyoBread. The last one is supposed to be a well-tested release with Froyo's stability and Gingerbread's features. In this blog, I wish to mention some of the features of the standard SE release with the requirements to hack the phone for non-standard upgrades. Mind you, this voids the warranty [unless you can get the phone back to factory release before claiming warranty ;) ] I've bought an additional warranty of another 12 months from the seller beyond the standard 1 year by SE.

Initially, I liked the SE X8, with a decent 3" screen. Both GSM Edge as well as WiFi worked just fine. The still as well as video camera is great. One issue with 2.1 is that its applications soon fill up the memory and since Android has its own memory management, with hardly any applications having an "exit", Advanced Task Killer is necessitated as a first install from Android's market. Yet another hurdle with enjoying more apps on 2.1 is that it doesn't allow moving apps to SD card. So my buying a 16GB card didn't turn out much useful yet. Having seen my 2.3 GingerBread on my brother's HTC Wildfire S, I couldn't wait to root the phone. Further, I found out that Quadrant Advanced clocks 440 as a benchmark with SE Eclair. This is expected to turn out to be rock-bottom with other releases, which I'll talk of in upcoming posts.

MAC cloning

I never thought that cloning MAC addresses was so simple, especially in Linux. But first I will digress as usual and start off as to what led me to cloning the MAC address. To skip all the blabber, goto to the bullets where it says skipblabber. :) Since my Toshiba laptop went out for service, it has started giving many problems in a row. First the heating issue led to a shutdown problem, then I messed up the alcohol used to clean the chips' heatsinks and conked my display off. The service guys fixed that but damaged all the navigation keys which almost need me to stand on them to move intermittently. With so many problems, how would I not suspect the laptop's networking when my ISP refused to connect?

My ISP kept on giving me errors on all flavours: Vista, Maverick and even downgrade installations to Jaunty! The error code indicated authentication problems, which may be protocol issues. I went ahead and got the ethernet and wifi checked elsewhere and all worked fine. Only then did I call my ISP and ask what the heck was going on. It turns out that my ISP has recently locked the account to a single MAC address for "security reasons". They wanted me to fill up a form to say that they should open my account to other MAC addresses and any misuse then would be my responsibility. I went straightaway looking for forms but they didn't tell me that Sunday their branch here is closed. I came back disappointed, but a search online landed me a simpler solution. Why go out at all signing forms when a few keystrokes get the job done?! :) So here goes:


skipblabber:

• Get your source system (my PC thats locked with the ISP) MAC address by ipconfig /all if you're in Windoze or in good ol' Linux you check the entry for ether by ifconfig. This MAC is used further as xx:xx:xx:xx:xx:xx
• Repeat the above for the target system (my laptop thats locked out from the ISP) so that I can jot it down in case something ever goes wrong. Contingency, that is. :)
• To change the target MAC on Linux:
• sudo ifconfig eth0 down
• sudo ifconfig eth0 hw ether xx:xx:xx:xx:xx:xx
• sudo ifconfig eth0 up (Goes off on reboot)
• OR in recent Ubuntu systems, just right click on network ->Edit Connections -> Eth0 -> Edit -> add xx:xx:xx:xx:xx:xx to Clone MAC. (Stays on reboot)
• To change the target MAC on Windoze:
• Go to LAN properties -> General -> Configure (LAN card) -> Advanced -> Network Address (Property) -> add xx:xx:xx:xx:xx:xx to Value -> OK
• Disable & enable the LAN or reboot (the Windoze way) :)
• OR regedit/ regedit32 and expand HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\ Control\Class\{4D36E972-E325-11CE-BFC1-08002BE10318}
• While there, check all subkeys 0001, 0002... till you get your LAN card in DriverDesc.
•  Add xx:xx:xx:xx:xx:xx to NetworkAddress value.
• Reboot.

If all went well, ipconfig /all or ifconfig should show you xx:xx:xx:xx:xx:xx as your new MAC. You need to try connecting to your ISP after the MAC change. In case of Linux, this would mean:

• sudo poff -a dsl-provider
• sudo pon dsl-provider
• OR sudo pppoeconf (if not already done earlier)

Note: In case your pppoeconf is stuck at 100% and goes nowhere, you're fast and lazy at the same time like me. :) You didn't read all that pppoeconf throws and pressed enter, enter,... If that, pppoeconf is likely stuck searching other network interfaces for announcements; this is a guess, by the way. Best way to get ahead immediately now is to unplug the LAN cable and replug it. :) Don't worry, its at 100% on eth0 search, so it will have those settings.

Using Linux for Windows fix!

I downloaded the trial version of BitDefender antivirus for my XP today and in its scanning during the installation itself, it found some 3 issues with Windows files and quarantined them. It asked for a reboot to continue installation. On reboot, it resumed or started the scan afresh without even really giving me my desktop; it was a blank screen with BitDefender scanning in the foreground. Meanwhile, a pop-up box told me that SYSTEM is going for a shutdown as the explorer.exe or some other service crashed. Well, okay, hardly a choice! However, on restart this time, I got a command line message on NTOSKRNL.EXE missing. Obviously, BitDefender knocked it off for a virus or something and am stuck with a command line. Worse yet, I can't restore it because I don't have a DVD/CD ROM drive. (It *burnt* a couple of months back).

So much for background. Next, I rebooted in Ubuntu Maverick and searched my system for an XP install ISO dumped. Maverick is awesome, because it opened .iso as is. Within that I386 folder, there was this NTOSKRNL.EX_ that needed to be expanded. I sent it straight down to my pen drive, ran an expand on it from Vista on my laptop and got it back here. All I needed now is to get the expanded NTOSKRNL.EXE (renamed from expanded NTOSKRNL.EX_) into C:\Windows\System32\. Phew.

Windows is mighty sick but my bank webpages and software unfortunately works only with Windows. :(