Tuesday, September 10, 2013

Kindle digital photo frame part 5: testing and finalizing

The scripting and programming is mostly complete. Time to test the Kindle. For the purpose of testing, I set the Kindle to change screensavers every 5 minutes instead of every 3 hours. It works flawlessly for hours at a time, then fails. It always fails in the same way: displaying no picture in screensaver mode. Even manually pressing the button power twice does not solve it. Perhaps the Blanket program crashed or something, I don't know, but it fixes itself after a restart.

After hours of debugging I still cannot figure out what the problem is. Decided to call it quits, but added a recovery option should that happen. I installed KUAL and kterm, so that after a reboot I can manually run my screensaver changing script again.

Finally, I decided to consolidate both the script to change screensavers and that to download images. Here's the final masterpiece:

# time to wake up
lipc-set-prop com.lab126.powerd wakeUp 1
sleep 3
mntroot rw
# download new images
lipc-set-prop com.lab126.cmd wirelessEnable 1
sleep 20
url=http://yourOwnURLhere.com
rm index
wget $url/images/index || error_exit "Cannot download list of images!"
grep "/img/uploads" index | awk -F\" '{print $2}' > /mnt/us/images.txt
cd pics
while read line
do
wget $url$line
done < /mnt/us/images.txt
# mark all images as downloaded
wget $url/images/reset
rm reset
lipc-set-prop com.lab126.cmd wirelessEnable 0
# randomize current set of photos
for f in /mnt/us/photos/*
do
newfile=`mktemp -p /mnt/us/photos`
mv -f $f $newfile
done
# if pics are downloaded, then choose between a pic and a photo
if [ "$(ls -A /mnt/us/pics)" ]
then
# 50% probability of displaying pic or photo
if [ `sed 's/[^[:digit:]]\+//g' < /dev/urandom | head -n 1 | awk '{print substr($0,0,2);}'` -lt 50 ]
then
# display a downloaded pic
echo displaying a downloaded pic
mv -f "/mnt/us/pics/`ls /mnt/us/pics -1 | head -n 1`" /mnt/us/linkss/screensavers/bg_xsmall_ss00.png
else
# display a photo
echo displaying a photo
cp "/mnt/us/photos/`ls /mnt/us/photos | sort | head -n 1`" /mnt/us/linkss/screensavers/bg_xsmall_ss00.png
fi
else
# no pics currently, just change to a photo
cp "/mnt/us/photos/`ls /mnt/us/photos | sort | head -n 1`" /mnt/us/linkss/screensavers/bg_xsmall_ss00.png
fi
/usr/bin/powerd_test -p
a=0
while [ $a -lt 50 ]
do
lipc-set-prop com.lab126.powerd deferSuspend 86400
sleep 2
a=`expr $a + 1`
done
view raw gistfile1.txt hosted with ❤ by GitHub

I've reset the screensavers to change every 3 hours instead of 5 minutes. It'll still be a few days before I present this to my girlfriend, a final few days to test and make sure it works perfect!

Kindle digital photo frame part 4: downloading pictures from the net + more screensaver problems

Even more problems came to bite me. I had intended to use wget with some options like -r to easily download all the images that I have listed on the front page of my CakePHP backend. However, Kindle's busybox wget is quite primitive; it does not have so many options, and I am forced to perform grep, awk and a lot more scripting to download the pictures that I uploaded. Here's the code:

lipc-set-prop com.lab126.cmd wirelessEnable 1
sleep 20
url=http://insertyourownURLhere.com
rm index
# get list of images to download
wget $url/images/index || error_exit "Cannot download list of images!"
grep "/img/uploads" index | awk -F\" '{print $2}' > images.txt
# download all queued images into pics/ folder
cd pics
while read line
do
wget $url$line
done < ../images.txt
# mark all images as downloaded, do not download them again
wget $url/images/reset
rm reset
lipc-set-prop com.lab126.cmd wirelessEnable 0
view raw gistfile1.txt hosted with ❤ by GitHub

In addition, Kindle renames screensavers after restart. All the photos inside the screensavers folder will be renamed to bg_xsmall_ssXX.png. That implies that a maximum of 100 photos are allowed. In addition, if the order of the photos is to be randomized via creating a file called "random", all the photos' filenames will be randomized again upon bootup, meaning I won't be able to tell if /var/local/blanket/screensaver/last_ss points to a photo or downloaded image.

In view of these, I decided to rotate the photos myself by placing one 1 photo inside the screensavers directory: bg_small_ss00.png, and replace that file everytime I change my screensaver. As usual, Busybox is so limited in functionality that I have to go through massive scripting just to choose a random photo or determine a random number. This is my updated screensaver-changing script:

lipc-set-prop com.lab126.powerd wakeUp 1
mntroot rw
sleep 3
# randomize order of photos
for f in /mnt/us/photos/*
do
newfile=`mktemp -p /mnt/us/photos`
mv -f $f $newfile
done
# if pics are downloaded, then choose between a pic and a photo
if [ "$(ls -A /mnt/us/pics)" ]
then
# 50% probability of displaying pic or photo
if [ `sed 's/[^[:digit:]]\+//g' < /dev/urandom | head -n 1 | awk '{print substr($0,0,2);}'` -lt 50 ]
then
# display a downloaded pic
echo displaying a downloaded pic
mv -f "/mnt/us/pics/`ls /mnt/us/pics -1 | head -n 1`" /mnt/us/linkss/screensavers/bg_xsmall_ss00.png
else
# display a photo
echo displaying a photo
cp "/mnt/us/photos/`ls /mnt/us/photos | sort | head -n 1`" /mnt/us/linkss/screensavers/bg_xsmall_ss00.png
fi
else
# no pics currently, just change to a photo
cp "/mnt/us/photos/`ls /mnt/us/photos | sort | head -n 1`" /mnt/us/linkss/screensavers/bg_xsmall_ss00.png
fi
# show the screensaver
/usr/bin/powerd_test -p
# suspend the Kindle in "Ready to suspend" mode indefinitely
a=0
while [ $a -lt 50 ]
do
lipc-set-prop com.lab126.powerd deferSuspend 86400
sleep 2
a=`expr $a + 1`
done
view raw gistfile1.txt hosted with ❤ by GitHub

Monday, September 9, 2013

MK 809 III Android mini PC

The MK 809 looks like an oversized thumb drive that plugs into a HDMI port, but it is a full fledged android pc. I was quite excited when I saw it on sale on Qoo10; I've been wanting a powerful arm computer to test BOINC on, and the MK 809 III has 4 cores, fits into my palm and uses a phone charger. Sweet!

I'm more bitter about the price though. The Qoo10 seller was selling at S$96 including shipping fees. That's out of my budget. Decided to source upstream, and found it alibaba.com, selling for US$45 a piece. However, there is a minimum order of 10. Thus finally, I went to it's sister site, aliexpress, and found one selling at US$57. Perfect!

I wonder if an Android OS can be used for programming?

Would update when the item arrives.

Final Fantasy Fables: Chocobo's Dungeon

Just cleared the 100 levels dungeon in Chopin's dungeon for the Wii. I killed the boss at level 71, and was level 8 dragoon wearing a genji's  talon+79 and king's saddle+57 when I did it. All I did was spam Holy Lance and Gungnir, drink ethers like crazy, and ate just one Phoenix down when near death.

Phew, that was fast!

Sunday, September 8, 2013

Kindle digital photo frame part 3: Changing screensavers every 3 hours

Getting the Kindle to change its screensaver is as simple as running /usr/bin/powerd_test -p twice. The script to do so:

/usr/bin/powerd_test -p
sleep 3
/usr/bin/powerd_test -p
view raw gistfile1.txt hosted with ❤ by GitHub

I wanted the screensaver to be changed every 3 hours, excluding nighttime. It's a matter of appending to /etc/crontab/root:

0 9 * * * /mnt/us/changeSS.sh
0 12 * * * /mnt/us/changeSS.sh
0 15 * * * /mnt/us/changeSS.sh
0 18 * * * /mnt/us/changeSS.sh
0 21 * * * /mnt/us/changeSS.sh
view raw gistfile1.txt hosted with ❤ by GitHub

Then I ran into a pesky problem. The screensaver changer works if I ran it manually. It doesn't work via the cron job. Or rather, I discovered that the Kindle goes to sleep after 1 minute in screensaver mode.

After fiddling with /usr/bin/powerd_test -s for quite some time I discovered the following. The Kindle has 4 power levels: Active, Screen Saver, Ready to suspend, and sleep. Active stays on for 10 minutes, Screen Saver stays on for 1 minute, and Ready to suspend stays on for 5 seconds. This is my log:

[root@kindle root]# /usr/bin/powerd_test -s
Powerd state: Active
Remaining time in this state: 581.725642
defer_suspend:1
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
[root@kindle root]# /usr/bin/powerd_test -s
Powerd state: Screen Saver
Remaining time in this state: 56.331120
defer_suspend:1
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
[root@kindle root]# /usr/bin/powerd_test -s
Powerd state: Screen Saver
Remaining time in this state: 0.984457
defer_suspend:1
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
[root@kindle root]# /usr/bin/powerd_test -s
Powerd state: Ready to suspend
Remaining time in this state: 4.947582
defer_suspend:0
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
view raw gistfile1.txt hosted with ❤ by GitHub

I can wake up my Kindle via the command "lipc-set-prop com.lab126.powerd wakeUp 1" provided it is in one of those 3 states. To try and suspend my Kindle in the "ScreenSaver" or "Ready to suspend" state for as long as possible, I investigated the seemingly useless property, deferSuspend, from com.lab126.powerd. When you run it, it gives the error:

com.lab126.powerd failed to set value for property deferSuspend (0x8 lipcErrNoSuchProperty)

I discovered that the property can only be set DURING THE READY TO SUSPEND STATE. That means after 11 minutes of leaving the Kindle alone I have a 5 second window to change the time left in "Ready to Suspend" state. See my logs:

csuspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
com.lab126.powerd failed to set value for property deferSuspend (0x8 lipcErrNoSu chProperty)
[root@kindle root]# /usr/bin/powerd_test -s; lipc-set-prop com.lab126.powerd def
erSuspend 1000
^[[APowerd state: Screen Saver
Remaining time in this state: 0.124960
defer_suspend:0
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
com.lab126.powerd failed to set value for property deferSuspend (0x8 lipcErrNoSu chProperty)
[root@kindle root]# /usr/bin/powerd_test -s; lipc-set-prop com.lab126.powerd def
erSuspend 1000
Powerd state: Ready to suspend
Remaining time in this state: 4.070775
defer_suspend:0
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
[root@kindle root]# /usr/bin/powerd_test -s; lipc-set-prop com.lab126.powerd def
erSuspend 1000
Powerd state: Ready to suspend
Remaining time in this state: 999.684285
defer_suspend:1
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
[root@kindle root]# /usr/bin/powerd_test -s; lipc-set-prop com.lab126.powerd def
erSuspend 3000000
Powerd state: Ready to suspend
Remaining time in this state: 995.529458
defer_suspend:1
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
[root@kindle root]# /usr/bin/powerd_test -s; lipc-set-prop com.lab126.powerd def
erSuspend 3000000
Powerd state: Ready to suspend
Remaining time in this state: 2999997.991570
defer_suspend:1
suspend_grace:0
prevent_screen_saver:0
drive_mode:unknown
Battery Level: 88%
Last batt event at: 88%
Charging: No
batt_full=0
Battery logging: On
[root@kindle root]#
view raw gistfile1.txt hosted with ❤ by GitHub

My screensaver changing script ended up as:

lipc-set-prop com.lab126.powerd wakeUp 1
sleep 3
/usr/bin/powerd_test -p
a=0
while [ $a -lt 50 ]
do
lipc-set-prop com.lab126.powerd deferSuspend 86400
sleep 2
a=`expr $a + 1`
done
view raw gistfile1.txt hosted with ❤ by GitHub

Digital photo frame: Kindle Touch vs Kindle Keyboard

In the midst of hacking my newly acquired Kindle keyboard I got myself another Kindle: this time a Kindle Touch 3G. I intended to use one as the photo frame and another as my ebook reader.

Now, which to use for my digital photo frame?

The Touch, being slimmer without a keyboard, would be easier to conceal within a frame. Not to mention that my Keyboard came with a leather case and I like it a lot. The Touch seems like a natural choice.

Until I got down to hacking it. After the usual jailbreaking and stuff, I found out that the Touch only supports PNG. This, while my Kindle keyboard can support jpg, gif and images of all shapes and sizes. Ended up using the Kindle Touch anyway.

Kindle digital photo frame part 2

Now that I can SSH into the Kindle I need to figure out the functions that I need. I want the Kindle to cycle through me and my gf's photos every 3 hours. Apart from that, I want to be able to upload photos of cute cats or love messages onto the internet, and those will show up, ONLY ONCE, on the Kindle.

For cycling photos, I need to:
  1. Wake up the Kindle from sleeping
  2. Put it to sleep again.

(1) is easy to find. The command, lipc-set-prop com.lab126.powerd wakeUp 1, will wake up the Kindle. (http://www.mobileread.com/. forums/archive/index.php/t-160328.html) Fortunately, cron works even when the Kindle is sleeping, so cycling photos is definitely possible.

(2) took me a while to find. The command is, /usr/bin/powerd_test -p . (http://www.mobileread.com/forums/showthread.php?t=220810) It works for waking up the Kindle as well, so now I can simply cycle my photos by running this command twice!

For displaying my uploaded pictures, I need to:
  1. Setup a server backend for uploading images
  2. Periodically downloading them into the Kindle
  3. Display the images occasionally, deleting them after they've been displayed.

For (1), I can simply use OpenShift and CakePHP to setup a backend for uploading and storing images. I've familiarized myself with that setup thanks to a previous competition, so no worries here.

(2), I can simply write a script for downloading the images from my backend and add it to crontab. I can even turn on wireless using cron, no issues here.

(3), I had no idea to detect which image is being displayed on screen. Thankfully, I found this page https://github.com/yifanlu/OpenBlanket/blob/master/screensaver.c, line 363 of the code shows that the last screensaver displayed is stored at "/var/local/blanket/screensaver/last_ss". I can use this while waking up the Kindle, to delete the images shown before.

Stay tuned to the next part!

Kindle digital photo frame part 1

Weeks ago I found out that my girlfriend would look at our pictures to relax herself when she is bored/stressed. I had the idea of putting a digital photo frame at her desk at work, that would cycle through our photos on a regular basis. She would be so delighted.

So I went to search for some digital photo frames on Qoo10.sg. Lots of choices, but there's a major problem. They're all using LED/LCD screens. This means: either they have an annoyingly short battery life (this item - 4 to 5 hours only?! Seriously?) or AC adaptor cables. I want a frame that is portable, not entangled by wires, and have a battery life counted in weeks, not hours.

So, the Kindle suits my purposes well. It does not consume power when displaying pictures, only when changing them. Suppose I change the images only once per hour... how much power can I save? The Kindle will last weeks!

I was lucky enough to find a seller on Hardwarezone selling his old Kindle keyboard WiFi at $70. He posted his offer just 3 hours before I saw it. And, coincidentally, he was visiting my office on the next day. I don't even need to arrange a pickup point! ^^

The next part: hacking the kindle. I followed a series of guides:

  1. http://anoved.net/2012/02/custom-kindle-screensaver-images-with-kite/ to enable custom screensavers.
  2. http://speely.wordpress.com/tag/3-4/ to enable ssh, and used this to figure out the root password
More to come!

Kindle lipc property list

=~=~=~=~=~=~=~=~=~=~=~= PuTTY log 2013.08.30 15:54:14 =~=~=~=~=~=~=~=~=~=~=~=
login as: root


Welcome to Kindle!

root@192.168.43.115's password: 
#################################################
#  N O T I C E  *  N O T I C E  *  N O T I C E  # 
#################################################
Rootfs is mounted read-only. Invoke mntroot rw to
switch back to a writable rootfs.
#################################################
[root@kindle root]# k   lipc-probe -a -v
com.lab126.pmond
 r  Str summary [name[pid] - state - mem_limit - mem_curr
----------------------------------------
tmd[13086] - started - 9000 - 2728
mcsd[13088] - started - 5000 - 1180
syslog[964] - started - 5000 - 808
netwatchd[0] - stopped - 5000 - 0
phd[13090] - started - 5000 - 2800
cvm[14228] - started - 103424 - 68272
wifid[13272] - started - 5000 - 3468
browserd[14055] - started - 90000 - 8408
webreader[14013] - started - 80000 - 15668
audioserver[15975] - started - 50000 - 4144
ttsd[13790] - started - 150000 - 6388
powerd[13143] - started - 5000 - 1456
volumd[13095] - started - 5000 - 1348
wand[0] - stopped - 5000 - 0
cmd[13267] - started - 5000 - 1516
]
 w Str start
 w Str restart
 w Str stop
 rw Str logMask [0xffff0000]
 w Str kill
 w Str heartbeat_start
 w Str mem_limit
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 w Str heartbeat_stop
com.lab126.audio
 rw  Str URI []
 w Str PlayerStop
 rw Int Control [0]
 rw Int GstrLatency [10000]
 r Int ManagerInitialize [1]
 rw Str logLevel [Current log level=none
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 rw Int CmdIVolume [14]
 r Int CmdISpeakerMax [15]
 w Str SendEvent
 w Int ThreadUp
 rw Str logMask [0x00000000]
 w Str PlayerDataReady
 w Str PlayerRelease
 r Int ManagerCleanup [1]
 w Str PlayerResume
WARNING: Failed to get value of Seek <0x213>
 rw Int Seek
 w Str PlayerCreate
 w Str PlayerPrefetch
 r Int CmdINSinks [2]
 rw Int Chapter [0]
WARNING: Failed to get value of ManagerSuspend <0xf>
 r Int ManagerSuspend
 w Str PlayerLoop
 w Str PlayerSeek
 w Str PlayerPause
 r Int CmdICurrentMax [15]
 w Str PlayerSuspend
 w Int ResetVolume
 rw Int GstrBufferTime [200000]
 w Str PlayerStart
 r Int ManagerShutdown [-4]
 w Int Kill
 rw Int Volume [70]
 r Int ManagerResume [1]
com.lab126.ttsd
 rw  Has enqueueSnippet [*NOT SHOWN*]
 w Int unpause2
 w Int cancelSnippetPlayback
 rw Has playSnippetNow [*NOT SHOWN*]
 w Int pause2
com.lab126.tts
 rw  Str TtsSVoice [Tom]
 w Int CtrlBookmark
 rw Has playFile [*NOT SHOWN*]
 rw Int TextToProcess [10]
 w Int stop
 rw Str logMask [0xffff0000]
 w Int pause
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 w Int unpause
 rw Str TtsSModel [full_155mrf22]
 rw Int TtsISpeed [100]
com.lab126.powerd
 w  Int addSuspendLevels
 r Str status [Powerd state: Active
Remaining time in this state: 308.400766
defer_suspend:0
suspend_grace:0
prevent_screen_saver:0
drive_mode:off
Battery Level: 97%
Last batt event at: 97%
Charging: No
batt_full=1
Battery logging: On
]
 w Int wakeUp
 rw Int preventScreenSaver [0]
 rw Str logMask [0xffff0000]
 w Int suspendGrace
 w Int deferSuspend
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 w Int touchScreenSaverTimeout
 r Str state [active]
 w Int abortSuspend
 r Int isCharging [0]
 r Int battLevel [97]
 w Int rtcWakeup
com.lab126.system
 w  Str date
 r Str version [System Software Version: 040-S4_luigi-172597 Sat Sep 1 14:29:41 PDT 2012]
 r Str boardid []
 r Str waveformversion [V220_C024_60_WJ7501_D (M24, S/N 1301, 85Hz)]
 r Str usid [B008A0A004357F9E]
 r Str orientation []
 w Str sendEvent
com.lab126.wifid
 rw  Has createProfile [*NOT SHOWN*]
 r Str signalStrength [5/5
]
 rw Has cmNWProperties [*NOT SHOWN*]
 rw Has netConfig [*NOT SHOWN*]
 r Str manufacturerCode [53GRADB9SMRC2WEX5DF4]
 rw Has profileData [*NOT SHOWN*]
 r Str feelingLuckyProfile [CBTL]
 w Str cmDisconnect
 rw Has currentEssid [*NOT SHOWN*]
 r Str 711 [********* 1- Connection *********
1.1 MAC: 28:EF:01:A8:69:3B
1.2 Wireless: On(1)
1.3 AP: A (02:08:22:d2:18:87)
1.3.1   Signal strength: 5/5
1.3.2   Captive: no
1.3.3   Security: WPA2-PSK
1.3.4   Channel: 1
1.6 Country: CN

********* 2- Wireless Configuration *********
2.1   A 0 [WPA2-PSK][CCMP] (6) 

********* 3- Interface Configuration *********
3.1 IP Address: 192.168.43.115
3.2 Netmask   : 255.255.255.0
3.3 Broadcast : 192.168.43.255
3.4 Gateway   : 192.168.43.1
3.5 Config    : DHCP
3.6 DNS       : 192.168.43.1, 
3.7 Sponsored    : no

********* 4- Last DHCP Session *********
Sending discover...
Offer from server xxx.xxx.43.1 received
Sending select for xxx.xxx.43.115...
Lease of xxx.xxx.43.115 obtained, lease time 43200

5 Device Time: Fri Aug 30 07:54:38 2013

]
 r Int profileCount [2]
 w Str cmConnMode
 r Str cmState [CONNECTED]
 w Str scan
 rw Str logMask [0xffff0000]
 rw Has createNetConfig [*NOT SHOWN*]
 w Str cmCheckConnection
 r Str cmProfile [A]
 r Int cmIntfInUse [1]
 rw Int enable [1]
 r Str macAddress [28:EF:01:A8:69:3B]
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 w Str deleteProfile
 r Str scanState [idle]
 w Str cmConnect
 rw Has scanList [*NOT SHOWN*]
 rw Has cmIntfInfo [*NOT SHOWN*]
 r Str macSecret [53GRADB9SMRC2WEX5DF4]
com.lab126.framework
 rw  Has transfer_status [*NOT SHOWN*]
 w Int insertKeystroke
 r Str xfsn [ELVvgP9mY0kDCu9gkeNQNYZqmnIHyNbJ9uP9xltY1/eJ3IvONcTj3bGDy7UE1w4Wb2yV3F0K9J4IFWBv9D8tGJXYHZgXqF5gXJG8eYsgooKWWH5iaa3vADv04BEdO29ecIIPVfUVejk=]
 rw Str logMask [crit | error | warn | info | event | perf | test | journal | debug0 | debug1 | debug2 | debug3 | debug4 | debug5 | debug6 | debug7 | debug8 | debug9 (0xffffff0)]
 w Int logContent
 rw Str logLevel [debug9]
 r Int wirelessSwitch [1]
 w Int read
 r Int isRegistered [0]
 r Int wanSwitch [1]
 w Int dismissDialog
com.lab126.transfer
 rw  Has dump_queues [*NOT SHOWN*]
 rw Has modify [*NOT SHOWN*]
 rw Has get_info [*NOT SHOWN*]
 rw Has request_upload [*NOT SHOWN*]
 rw Has dequeue [*NOT SHOWN*]
 rw Str logMask [0xffff0000]
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 rw Has send_status [*NOT SHOWN*]
 rw Has request_download [*NOT SHOWN*]
 rw Has obliterate [*NOT SHOWN*]
com.lab126.phd
 w  Str newSPHSchedule
 rw Str logMask [0xffff0000]
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
com.lab126.volumd
 r  Int mmcIsAvailable [0]
 r Int userstoreFreeSpace [3127952]
 r Int driveModeState [0]
 r Int mmcFreeSpace [-1]
 rw Int useUsbForSerial [0]
 w Int userstoreReadyToUnMount
 rw Str logMask [0xffff0000]
 r Int mmcTotalSpace [-1]
 rw Int useUsbForNetwork [0]
 r Int userstoreTotalSpace [3201936]
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 r Int userstoreIsAvailable [1]
com.lab126.webreaderListener
com.lab126.cmd
 r  Str activeInterface [wifi]
 w Str ensureConnection
 rw Str logMask [0xffff0000]
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
 rw Has availableInterfaces [*NOT SHOWN*]
 rw Has interfaceProperties [*NOT SHOWN*]
com.lab126.cvm
 rw  Str logMask [0xffff0000]
 rw Str logLevel [Current log level=info
(Possible levels: all, perf, debug[9-0], info, warn, error, crit, none)]
com.lab126.mcsd
 w  Int performScan
 w Int selectAutomaticMode
 r Int getManagementState [0]
 w Int enableManagementState
 w Int requestCurrentState
 w Int abortScan
 w Str selectNetwork
[root@kindle root]# exit

Monday, July 15, 2013

Codechef July 2013 Prob: the ultimate troll question

First, I had no idea how to solve this at all. There is no way to brute force it for such extremely large numbers.

Then, I saw this comment:
I was trolled by this question in two phases : First after solving for two hours I was like "oh man, awesome question. So one part of the question remains" then after 5 hours of PnC and probability, when I saw it I was like "mother of all trolls" serious mindfuck question.
I knew there had to be a shortcut somewhere. Hence, I worked out the first sample test case for t4=1. Yielded the result of 0.5. Could it be that the output is the same regardless of how many tickets Chef discards?

Investigating further, I made a program that calculates the probability of every single combination, a.k.a brute forcing the solution. Code here. Of course, I would only load the program with small inputs. The result:

Input:
9
2 2 1 0
2 2 1 1
2 2 1 2
2 2 1 3
2 3 4 0
2 3 4 1
2 3 4 2
2 3 4 3
2 3 4 4
view raw gistfile1.txt hosted with ❤ by GitHub


Output:
0.5
0.5
0.5
0.5
0.4
0.4
0.4
0.4
0.4
view raw gistfile1.txt hosted with ❤ by GitHub


I found the shortcut! Indeed, the probability is the same regardless of how many tickets Chef discarded. Happily discarded T4 from my program, submitted it, only to get a runtime error. Turns out my stack has run out of space due to too many recursive calls from T3. Hmm, I thought, I could make the calculation non-recursive, but it is still up to 1000000000 calculations for a single test. Another shortcut must exist!

Went back to the question to look for more patterns. Discovered than 0.5 = 2/(2+2) for first sample test case, and 0.4 = 2/(2+3) for second test case. T3 is also not needed!

Submitted a program consisting of just these few lines:

import sys
T = int(sys.stdin.readline().strip())
for t in range(T):
t1,t2,t3,t4 = sys.stdin.readline().strip().split()
t1,t2,t3,t4 = int(t1),int(t2),int(t3),int(t4)
print t1 * 1.0 / (t1+t2)
view raw gistfile1.txt hosted with ❤ by GitHub


ANDDDDDDDDDDDDDDDDD


Ultimate troll question.



Codechef July 2013 Galactik

First, to find out where to build the bridges, I had to find out what islands/isolated pockets of planets are there. This can be done by a connected components algorithm, simple enough.

Next step, to choose which islands to build the teleporters on....I had no idea. Dug through the comments on the question page for hints. I found this big one:
Can GFA create more than one teleport on a planet?
Please specify if GFA can construct more than one teleport ending on a planet.
@zwolf10003 ,@qwaker00: yes.

Hence, I could just build one end of all teleporters on the same planet. And of course, that planet would offer the cheapest rate in the galaxy for building one!

The other end would go to each individual island/component. And for each island, the best place to end the teleporter would be the cheapest planet in the island.

With the solution planned out I proceeded to code it out in Python. Code here. Worked perfectly, but when submitted:


Sigh.

Time for port over to C++ again. But before that, I made a search for the fastest I/O operation I can achieve on C++. I landed upon this blog post. Tried the last method, but found that Windows does not have getchar_unlocked(). Replaced it with getchar() instead.

The result:
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <map>
#define MAX_N 100000
#define MAX_M 1000000
using namespace std;
bool travelled[MAX_N] = {false};
vector<int> islandMinCost;
int cost[MAX_N];
int N,M;
//map<int, vector<int> > edges;
vector<int> edges[MAX_N];
void makeIslands()
{
for (int n=0;n<N;n++)
{
if (!travelled[n])
{
int minCost = cost[n];
stack<int> toVisit;
toVisit.push(n);
while (!toVisit.empty())
{
int current = toVisit.top();
//printf("current %d cost %d\n", current, cost[current]);
toVisit.pop();
if (travelled[current])
continue;
travelled[current] = true;
if (cost[current] >= 0 && cost[current] < minCost)
minCost = cost[current];
if (minCost < 0)
minCost = cost[current];
for (vector<int>::iterator iter = edges[current].begin(); iter != edges[current].end(); iter++)
{
toVisit.push(*iter);
}
}
islandMinCost.push_back(minCost);
}
}
}
inline void fastRead(int *a)
{
register char c=0;
bool negative = false;
while (c<33) c=getchar();
*a=0;
while (c>33)
{
if (c == '-')
negative = true;
else
*a=*a*10+c-'0';
c=getchar();
}
if (negative)
*a = *a * -1;
}
int main()
{
int A,B,C;
fastRead(&N);
fastRead(&M);
// printf("%d %d\n", N,M);
for (int m=0;m<M;m++)
{
fastRead(&A);
fastRead(&B);
//printf("%d %d\n", A,B);
A -= 1;
B -= 1;
edges[A].push_back(B);
edges[B].push_back(A);
}
for (int n=0;n<N;n++)
{
fastRead(&C);
// printf("%d\t",C);
cost[n] = C;
}
makeIslands();
int cheapestIsland = islandMinCost[0];
int totalCost = 0;
for (vector<int>::iterator iter = islandMinCost.begin(); iter != islandMinCost.end(); iter++)
{
//cout << *iter << " ";
if (*iter < 0)
{
totalCost = -1;
break;
}
if (*iter < cheapestIsland)
cheapestIsland = *iter;
totalCost += *iter;
}
// cout <<endl;
if (totalCost >= 0)
totalCost += (islandMinCost.size()-2) * cheapestIsland;
if (islandMinCost.size() == 1)
totalCost = 0;
cout << totalCost;
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub


It's accepted!


Tuesday, July 2, 2013

Codechef Jun 2013 Collect

Coded first in Python, time limit exceeded.

# time limit exceeded again.
#8 people choose 6 people to give 2 berries
#14 berries divide into set of 2,2,2,2,2,2,1,1
#first set 14 c 2 = 14! / 12!2!
#second set 12 c 2 = 12! / 10!2!
#third set 10 c 2 = 10! / 8!2!
#fourth set 8 c 2 = 8! / 6!2!
#fifth set 6 c 2 = 6! / 4!2!
#sixth set 4 c 2 = 4! / 2!2!
#seventh set 2 c 1 = 2! / 1!1!
#eighth set 1 c 1 = 1! / 1!
#number of ways to divide 14 berries into 8 sets
#(14!/2^6 * 8C6) mod 3046201 = 2065880
# 16 berries, 5 people
# 16 berries divide into set of 4,3,3,3,3
# 5 people choose 1 to give 4 berries
#first set 16 c 4 = 16! / 12!4!
#second set 12 c 3 = 12! / 9!3!
#third set 9 c 3 = 9! / 6!3!
#fourth set 6 c 3 = 6! / 3!3!
#fifth set 3 c 3 = 3! / 3!
# 26 berries, 4 people
# 26 berries divide into set of 7,7,6,6
# 4 people choose 2 to give 7 berries
#first set 26 c 7 = 26! / 19!7!
#second set 19 c 7 = 19! / 12!7!
#third set 12 c 6 = 12! / 6!6!
#fourth set 6 c 6 = 6! / 6!
# number of ways to choose = (choose people for more berries) * berries! / (bigger size)!^(size of larger set) / (smaller size)!^(size of smaller set)
import sys
modo = 3046201
def modular_exponential(a,b,n):
binary = ""
while b > 0:
if b & 1 == 1:
binary += "1"
else:
binary += "0"
b >>= 1
result = 1
for i in xrange(len(binary)):
result = (result * result) % n
if binary[len(binary)-1-i] == "1":
result = (result * a) % n
return result
def divides(a,p):
# Fermat's little theorem: since 3046201 is a prime number, we
# can use this
return modular_exponential(a,p-2,p)
N = int(sys.stdin.readline().strip())
numbers = sys.stdin.readline().strip().split()
for i in xrange(len(numbers)):
numbers[i] = int(numbers[i])
Q = int(sys.stdin.readline().strip())
factorials = [0]*(N*30+1)
factorials[0] = 1
factorials[1] = 1
for i in xrange(2,N*30+1):
factorials[i] = (factorials[i-1]*i) % modo
for q in xrange(Q):
query, l,r = sys.stdin.readline().strip().split()
l,r = int(l),int(r)
if query == "change":
numbers[l-1] = r
elif query == "query":
# count berries
berries = sum(numbers[l-1:r])
people = r-l+1
lessBerries = int(berries / people)
moreBerries = lessBerries + 1
moreBerriesSize = berries % people
lessBerriesSize = people - moreBerriesSize
#(choose people for more berries) * berries! / (bigger size)!^(size of larger set) / (smaller size)!^(size of smaller set)
print (factorials[berries] \
* factorials[people] \
* divides( \
( \
factorials[moreBerriesSize] \
* factorials[lessBerriesSize] \
* modular_exponential(factorials[moreBerries],moreBerriesSize,3046201) \
* modular_exponential(factorials[lessBerries], lessBerriesSize, 3046201) \
), 3046201) \
) % 3046201
view raw gistfile1.txt hosted with ❤ by GitHub

Then ported over to C++, time limited exceeded again.

#include <vector>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <ctime>
#define modo 3046201
using namespace std;
// base and base_digits must be consistent
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
vector<int> a;
int sign;
bigint() :
sign(1) {
}
bigint(long long v) {
*this = v;
}
bigint(const string &s) {
read(s);
}
void operator=(const bigint &v) {
sign = v.sign;
a = v.a;
}
void operator=(long long v) {
sign = 1;
if (v < 0)
sign = -1, v = -v;
for (; v > 0; v = v / base)
a.push_back(v % base);
}
bigint operator+(const bigint &v) const {
if (sign == v.sign) {
bigint res = v;
for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
if (i == (int) res.a.size())
res.a.push_back(0);
res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
carry = res.a[i] >= base;
if (carry)
res.a[i] -= base;
}
return res;
}
return *this - (-v);
}
bigint operator-(const bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
bigint res = *this;
for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
carry = res.a[i] < 0;
if (carry)
res.a[i] += base;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
}
void operator*=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
if (i == (int) a.size())
a.push_back(0);
long long cur = a[i] * (long long) v + carry;
carry = (int) (cur / base);
a[i] = (int) (cur % base);
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
}
trim();
}
bigint operator*(int v) const {
bigint res = *this;
res *= v;
return res;
}
friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
int norm = base / (b1.a.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.a.resize(a.a.size());
for (int i = a.a.size() - 1; i >= 0; i--) {
r *= base;
r += a.a[i];
int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
int d = ((long long) base * s1 + s2) / b.a.back();
r -= b * d;
while (r < 0)
r += b, --d;
q.a[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
}
bigint operator/(const bigint &v) const {
return divmod(*this, v).first;
}
bigint operator%(const bigint &v) const {
return divmod(*this, v).second;
}
void operator/=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
long long cur = a[i] + rem * (long long) base;
a[i] = (int) (cur / v);
rem = (int) (cur % v);
}
trim();
}
bigint operator/(int v) const {
bigint res = *this;
res /= v;
return res;
}
int operator%(int v) const {
if (v < 0)
v = -v;
int m = 0;
for (int i = a.size() - 1; i >= 0; --i)
m = (a[i] + m * (long long) base) % v;
return m * sign;
}
void operator+=(const bigint &v) {
*this = *this + v;
}
void operator-=(const bigint &v) {
*this = *this - v;
}
void operator*=(const bigint &v) {
*this = *this * v;
}
void operator/=(const bigint &v) {
*this = *this / v;
}
bool operator<(const bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (a.size() != v.a.size())
return a.size() * sign < v.a.size() * v.sign;
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != v.a[i])
return a[i] * sign < v.a[i] * sign;
return false;
}
bool operator>(const bigint &v) const {
return v < *this;
}
bool operator<=(const bigint &v) const {
return !(v < *this);
}
bool operator>=(const bigint &v) const {
return !(*this < v);
}
bool operator==(const bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const bigint &v) const {
return *this < v || v < *this;
}
void trim() {
while (!a.empty() && !a.back())
a.pop_back();
if (a.empty())
sign = 1;
}
bool isZero() const {
return a.empty() || (a.size() == 1 && !a[0]);
}
bigint operator-() const {
bigint res = *this;
res.sign = -sign;
return res;
}
bigint abs() const {
bigint res = *this;
res.sign *= res.sign;
return res;
}
long long longValue() const {
long long res = 0;
for (int i = a.size() - 1; i >= 0; i--)
res = res * base + a[i];
return res * sign;
}
friend bigint gcd(const bigint &a, const bigint &b) {
return b.isZero() ? a : gcd(b, a % b);
}
friend bigint lcm(const bigint &a, const bigint &b) {
return a / gcd(a, b) * b;
}
void read(const string &s) {
sign = 1;
a.clear();
int pos = 0;
while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + s[j] - '0';
a.push_back(x);
}
trim();
}
friend istream& operator>>(istream &stream, bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
}
friend ostream& operator<<(ostream &stream, const bigint &v) {
if (v.sign == -1)
stream << '-';
stream << (v.a.empty() ? 0 : v.a.back());
for (int i = (int) v.a.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.a[i];
return stream;
}
static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < (int) p.size(); i++)
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int i = 0; i < (int) a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int) cur);
while (!res.empty() && !res.back())
res.pop_back();
return res;
}
typedef vector<long long> vll;
static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= 32) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
}
int k = n >> 1;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end());
vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2);
for (int i = 0; i < k; i++)
a2[i] += a1[i];
for (int i = 0; i < k; i++)
b2[i] += b1[i];
vll r = karatsubaMultiply(a2, b2);
for (int i = 0; i < (int) a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
r[i] -= a2b2[i];
for (int i = 0; i < (int) r.size(); i++)
res[i + k] += r[i];
for (int i = 0; i < (int) a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
}
bigint operator*(const bigint &v) const {
vector<int> a6 = convert_base(this->a, base_digits, 6);
vector<int> b6 = convert_base(v.a, base_digits, 6);
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back(0);
while (b.size() < a.size())
b.push_back(0);
while (a.size() & (a.size() - 1))
a.push_back(0), b.push_back(0);
vll c = karatsubaMultiply(a, b);
bigint res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < (int) c.size(); i++) {
long long cur = c[i] + carry;
res.a.push_back((int) (cur % 1000000));
carry = (int) (cur / 1000000);
}
res.a = convert_base(res.a, 6, base_digits);
res.trim();
return res;
}
};
bigint modular_expo(bigint a, bigint b, bigint n)
{
bigint c(b);
string binary;
while (c > 0)
{
if (c%2 == 1)
binary += "1";
else
binary += "0";
c /= 2;
}
bigint result("1");
for (int i=0;i<binary.length();i++)
{
result = (result * result)%n;
if (binary.at(binary.length()-i-1) == '1')
result = (result * a)%n;
}
return result;
}
bigint fermat(bigint a,bigint p)
{
return modular_expo(a,p-2,p);
}
int main() {
unsigned int N,Q,l,r;
string query;
int* n = new int[100000];
// input
cin >> N;
for (int z=0;z<N;z++)
{
cin >> n[z];
}
cin >> Q;
// initialize factorials
bigint* factorials = new bigint[N*30+1];
factorials[0] = 1;
factorials[1] = 1;
for (unsigned int i=2;i<N*30+1;i++)
{
factorials[i] = (factorials[i-1]*i)%modo;
}
for (int z=0;z<Q;z++)
{
cin >> query >> l >> r;
if (query == "change")
{
n[l-1] = r;
} else if (query == "query")
{
// count berries and people
unsigned int berries = 0, people = r-l+1;
for (int k=l-1;k<r;k++)
{
berries += n[k];
}
unsigned int lessBerries = berries/people;
unsigned int moreBerries = lessBerries + 1;
unsigned int moreBerriesSize = berries % people;
unsigned int lessBerriesSize = people - moreBerriesSize;
bigint result
= (factorials[berries]
* factorials[people]
* fermat(
(factorials[moreBerriesSize]
* factorials[lessBerriesSize]
* modular_expo(factorials[moreBerries], moreBerriesSize, modo)
* modular_expo(factorials[lessBerries], lessBerriesSize, modo)
),modo)
) % modo;
cout << result << endl;
}
}
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub

Reviewed the editorial, added segment trees to facilitate range querying, but still exceeded time limit!

// time limit exceeded
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <ctime>
#define modo 3046201
using namespace std;
// base and base_digits must be consistent
const int base = 1000000000;
const int base_digits = 9;
class Segtree
{
private:
int* nodes;
int num_leaves;
public:
Segtree(int size1, int* values)
{
num_leaves = 1;
int size2 = size1;
while (size2 > 1)
{
size2 -= int(size2/2);
num_leaves *= 2;
}
nodes = new int[num_leaves*2];
// init
for (int i=0;i<num_leaves*2;i++)
nodes[i] = 0;
// copy the values
for (int j=0;j<size1;j++)
{
nodes[num_leaves-1+j] = values[j];
}
// summarize the leaves
for (int i=num_leaves-2;i>=0;i--)
{
nodes[i] = nodes[i*2+1] + nodes[i*2+2];
}
};
void update(int node, int value)
{
node = num_leaves-1+node;
nodes[node] = value;
int i = node;
while (i>0)
{
if (i%2 == 0)
{
nodes[(i-2)/2] = nodes[i] + nodes[i-1];
i = (i-2)/2;
} else {
nodes[(i-1)/2] = nodes[i] + nodes[i+1];
i = (i-1)/2;
}
}
};
int query(int queryStart, int queryEnd)
{
return query(0, 0, num_leaves-1, queryStart-1, queryEnd-1);
};
int query(int curNode, int rangeStart, int rangeEnd, int queryStart, int queryEnd)
{
if (rangeEnd < queryStart) return 0;
if (rangeStart > queryEnd) return 0;
if (queryStart <= rangeStart && rangeEnd <= queryEnd)
return nodes[curNode];
int midNode = int((rangeEnd - rangeStart)/2)+rangeStart;
return query(curNode*2+1, rangeStart, midNode, queryStart, queryEnd) + query(curNode*2+2, midNode+1,rangeEnd, queryStart, queryEnd);
};
void display()
{
for (int i=0;i<num_leaves*2;i++)
{
cout << nodes[i] << " ";
}
cout<<endl;
}
};
struct bigint {
vector<int> a;
int sign;
bigint() :
sign(1) {
}
bigint(long long v) {
*this = v;
}
bigint(const string &s) {
read(s);
}
void operator=(const bigint &v) {
sign = v.sign;
a = v.a;
}
void operator=(long long v) {
sign = 1;
if (v < 0)
sign = -1, v = -v;
for (; v > 0; v = v / base)
a.push_back(v % base);
}
bigint operator+(const bigint &v) const {
if (sign == v.sign) {
bigint res = v;
for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
if (i == (int) res.a.size())
res.a.push_back(0);
res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
carry = res.a[i] >= base;
if (carry)
res.a[i] -= base;
}
return res;
}
return *this - (-v);
}
bigint operator-(const bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
bigint res = *this;
for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
carry = res.a[i] < 0;
if (carry)
res.a[i] += base;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
}
void operator*=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
if (i == (int) a.size())
a.push_back(0);
long long cur = a[i] * (long long) v + carry;
carry = (int) (cur / base);
a[i] = (int) (cur % base);
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
}
trim();
}
bigint operator*(int v) const {
bigint res = *this;
res *= v;
return res;
}
friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
int norm = base / (b1.a.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.a.resize(a.a.size());
for (int i = a.a.size() - 1; i >= 0; i--) {
r *= base;
r += a.a[i];
int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
int d = ((long long) base * s1 + s2) / b.a.back();
r -= b * d;
while (r < 0)
r += b, --d;
q.a[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
}
bigint operator/(const bigint &v) const {
return divmod(*this, v).first;
}
bigint operator%(const bigint &v) const {
return divmod(*this, v).second;
}
void operator/=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
long long cur = a[i] + rem * (long long) base;
a[i] = (int) (cur / v);
rem = (int) (cur % v);
}
trim();
}
bigint operator/(int v) const {
bigint res = *this;
res /= v;
return res;
}
int operator%(int v) const {
if (v < 0)
v = -v;
int m = 0;
for (int i = a.size() - 1; i >= 0; --i)
m = (a[i] + m * (long long) base) % v;
return m * sign;
}
void operator+=(const bigint &v) {
*this = *this + v;
}
void operator-=(const bigint &v) {
*this = *this - v;
}
void operator*=(const bigint &v) {
*this = *this * v;
}
void operator/=(const bigint &v) {
*this = *this / v;
}
bool operator<(const bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (a.size() != v.a.size())
return a.size() * sign < v.a.size() * v.sign;
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != v.a[i])
return a[i] * sign < v.a[i] * sign;
return false;
}
bool operator>(const bigint &v) const {
return v < *this;
}
bool operator<=(const bigint &v) const {
return !(v < *this);
}
bool operator>=(const bigint &v) const {
return !(*this < v);
}
bool operator==(const bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const bigint &v) const {
return *this < v || v < *this;
}
void trim() {
while (!a.empty() && !a.back())
a.pop_back();
if (a.empty())
sign = 1;
}
bool isZero() const {
return a.empty() || (a.size() == 1 && !a[0]);
}
bigint operator-() const {
bigint res = *this;
res.sign = -sign;
return res;
}
bigint abs() const {
bigint res = *this;
res.sign *= res.sign;
return res;
}
long long longValue() const {
long long res = 0;
for (int i = a.size() - 1; i >= 0; i--)
res = res * base + a[i];
return res * sign;
}
friend bigint gcd(const bigint &a, const bigint &b) {
return b.isZero() ? a : gcd(b, a % b);
}
friend bigint lcm(const bigint &a, const bigint &b) {
return a / gcd(a, b) * b;
}
void read(const string &s) {
sign = 1;
a.clear();
int pos = 0;
while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + s[j] - '0';
a.push_back(x);
}
trim();
}
friend istream& operator>>(istream &stream, bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
}
friend ostream& operator<<(ostream &stream, const bigint &v) {
if (v.sign == -1)
stream << '-';
stream << (v.a.empty() ? 0 : v.a.back());
for (int i = (int) v.a.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.a[i];
return stream;
}
static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < (int) p.size(); i++)
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int i = 0; i < (int) a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int) cur);
while (!res.empty() && !res.back())
res.pop_back();
return res;
}
typedef vector<long long> vll;
static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= 32) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
}
int k = n >> 1;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end());
vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2);
for (int i = 0; i < k; i++)
a2[i] += a1[i];
for (int i = 0; i < k; i++)
b2[i] += b1[i];
vll r = karatsubaMultiply(a2, b2);
for (int i = 0; i < (int) a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
r[i] -= a2b2[i];
for (int i = 0; i < (int) r.size(); i++)
res[i + k] += r[i];
for (int i = 0; i < (int) a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
}
bigint operator*(const bigint &v) const {
vector<int> a6 = convert_base(this->a, base_digits, 6);
vector<int> b6 = convert_base(v.a, base_digits, 6);
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back(0);
while (b.size() < a.size())
b.push_back(0);
while (a.size() & (a.size() - 1))
a.push_back(0), b.push_back(0);
vll c = karatsubaMultiply(a, b);
bigint res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < (int) c.size(); i++) {
long long cur = c[i] + carry;
res.a.push_back((int) (cur % 1000000));
carry = (int) (cur / 1000000);
}
res.a = convert_base(res.a, 6, base_digits);
res.trim();
return res;
}
};
bigint modular_expo(bigint a, bigint b, bigint n)
{
bigint c(b);
string binary;
while (c > 0)
{
if (c%2 == 1)
binary += "1";
else
binary += "0";
c /= 2;
}
bigint result("1");
for (int i=0;i<binary.length();i++)
{
result = (result * result)%n;
if (binary.at(binary.length()-i-1) == '1')
result = (result * a)%n;
}
return result;
}
bigint fermat(bigint a,bigint p)
{
return modular_expo(a,p-2,p);
}
int main() {
unsigned int N,Q,l,r;
string query;
int* n = new int[100000];
// input
cin >> N;
for (int z=0;z<N;z++)
{
cin >> n[z];
}
cin >> Q;
Segtree* segtree = new Segtree(N, n);
// initialize factorials
bigint* factorials = new bigint[N*30+1];
factorials[0] = 1;
factorials[1] = 1;
for (unsigned int i=2;i<N*30+1;i++)
{
factorials[i] = (factorials[i-1]*i)%modo;
}
for (int z=0;z<Q;z++)
{
cin >> query >> l >> r;
if (query == "change")
{
n[l-1] = r;
segtree->update(l-1,r);
} else if (query == "query")
{
// count berries and people
unsigned int berries = 0, people = r-l+1;
berries = segtree->query(l,r);
unsigned int lessBerries = berries/people;
unsigned int moreBerries = lessBerries + 1;
unsigned int moreBerriesSize = berries % people;
unsigned int lessBerriesSize = people - moreBerriesSize;
bigint result
= (factorials[berries]
* factorials[people]
* fermat(
(factorials[moreBerriesSize]
* factorials[lessBerriesSize]
* modular_expo(factorials[moreBerries], moreBerriesSize, modo)
* modular_expo(factorials[lessBerries], lessBerriesSize, modo)
),modo)
) % modo;
cout << result << endl;
}
}
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub

=_=U

Thursday, June 27, 2013

Win32 no more flicker

Thanks to this blog, solved that flicker problem by:

  1. Painting to a back buffer instead of directly to screen
  2. Overriding WM_ERASEBKGND with "return true" so that it doesn't erase the background every second/every time the screen is invalidated.

Code

Next, to get rid of the black background.

Wednesday, June 26, 2013

Codechef Jun 2013 Elephants (C++)

This code is simply a direct port from Python to C++. My Python submission gave a "time limit exceeded" error, while my C++ submission is perfectly accepted. Is Python really that slow?
#include <iostream>
#include <string>
using namespace std;
int main()
{
int T, n,m;
int** influence = new int*[100];
int*** dp = new int**[100];
for (int i=0;i<100;i++)
{
influence[i] = new int[100];
dp[i] = new int*[100];
for (int j=0;j<100;j++)
{
dp[i][j] = new int[2];
}
}
cin >> T;
for(int t=0;t<T;t++)
{
cin >> n >> m;
string* mapp = new string[n];
// read map
for (int n1=0;n1<n;n1++)
{
cin >> mapp[n1];
}
// initialisation
for (int n1=0;n1<n;n1++)
{
for (int m1=0;m1<m;m1++)
{
influence[n1][m1] = 0;
dp[n1][m1][0] = 0;
dp[n1][m1][1] = 0;
}
}
// create influence map
for (int n1=0;n1<n;n1++)
{
for (int m1=0;m1<m;m1++)
{
if (mapp[n1].at(m1) == '1')
{
influence[n1][m1] += 1;
if (m1-1 >= 0) influence[n1][m1-1]+=1;
if (n1-1 >= 0) influence[n1-1][m1]+=1;
if (m1+1 < m) influence[n1][m1+1]+=1;
if (n1+1 < n) influence[n1+1][m1]+=1;
}
}
}
// run dp
int x,y;
for (y=0;y<n;y++)
{
for (x=0;x<m;x++)
{
int fromleft,fromtop;
dp[y][x][0] += influence[y][x];
dp[y][x][1] += influence[y][x];
if (x-1 >= 0)
{
fromleft = min(dp[y][x-1][0], (y-1>=0)? (dp[y][x-1][1]-((mapp[y-1].at(x) == '1')?1:0)) : dp[y][x-1][1]);
if (mapp[y].at(x)=='1') fromleft -= 1;
if (mapp[y].at(x-1)=='1') fromleft -= 1;
}
if (y-1 >= 0)
{
fromtop = min(dp[y-1][x][1], (x-1 >= 0) ? dp[y-1][x][0]-(((mapp[y].at(x-1)=='1')?1:0)) : dp[y-1][x][0]);
if (mapp[y].at(x)=='1') fromtop -= 1;
if (mapp[y-1].at(x)=='1') fromtop -= 1;
}
if (x-1 < 0 and y-1 < 0)
{
} else if (x-1 < 0) {
dp[y][x][0] += fromtop;
dp[y][x][1] += fromtop;
} else if (y-1 < 0) {
dp[y][x][0] += fromleft;
dp[y][x][1] += fromleft;
} else {
dp[y][x][0] += fromleft;
dp[y][x][1] += fromtop;
}
}
}
cout << min(dp[y-1][x-1][0], dp[y-1][x-1][1])<<endl;
}
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub

Tuesday, June 25, 2013

More Win32 fun

Managed to set a timer to update the text on the screen every second, however, the window does not wipe itself clean after every update.

Code

After much research, came upon this solution: http://msdn.microsoft.com/en-us/library/ms632599(VS.85).aspx#layered

Instead of

hWnd = CreateWindow(szWindowClass, 0, 0,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
view raw gistfile1.txt hosted with ❤ by GitHub
I used
hWnd = CreateWindowEx(WS_EX_LAYERED, szWindowClass, 0, 0,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
SetLayeredWindowAttributes(hWnd,RGB(255,255,255), 0, LWA_COLORKEY);
view raw gistfile1.txt hosted with ❤ by GitHub
That solved it. Code

Codechef June 2013 Elephants

# wrong answer
# standard DP problem with a twist.
# the approach I chose:
# 1. create an influence map not unlike those in game AI
# 2. add the influence value at every point of the path
# 3. deduct appropriate values when a mouse is double-counted
# the rules for detecting double-counting mice:
# 1. if a mouse moves right from tile x1 to tile x2 and there
# is a mouse at x2, deduct 1
# 2. if a mouse moves down from tile y1 to tile y2 and there
# is a mouse at y2, deduct 1
# 3. if a mouse moves from tile t to any tile, and there is a
# mouse at t, deduct 1
import sys
T = int(sys.stdin.readline().strip())
for t in xrange(T):
n,m = sys.stdin.readline().strip().split()
n,m = int(n), int(m)
mapp = []
# read map
for i in xrange(n):
mapp.append(sys.stdin.readline().strip())
# create influence map
influence = []
for i in range(n):
influence.append([0] * m)
for y in xrange(n):
for x in xrange(m):
if mapp[y][x] == "1":
influence[y][x] += 1
if x-1 >= 0:
influence[y][x-1] += 1
if y-1 >= 0:
influence[y-1][x] += 1
if x+1 < m:
influence[y][x+1] += 1
if y+1 < n:
influence[y+1][x] += 1
# run DP
dp = []
for i in range(n):
dp.append([0] * m)
for y in xrange(n):
for x in xrange(m):
dp[y][x] += influence[y][x]
# from left
if x-1 >= 0:
fromleft = dp[y][x-1]
# rule 1
if mapp[y][x] == "1":
fromleft -= 1
# rule 3
if mapp[y][x-1] == "1":
fromleft -= 1
# from top
if y-1 >= 0:
fromtop = dp[y-1][x]
# rule 2
if mapp[y][x] == "1":
fromtop -= 1
# rule 3
if mapp[y-1][x] == "1":
fromtop -= 1
if x-1 < 0 and y-1 < 0:
pass
elif x-1 < 0:
dp[y][x] += fromtop
elif y-1 < 0:
dp[y][x] += fromleft
else:
dp[y][x] += min(fromtop,fromleft)
print dp[y]
print
view raw gistfile1.txt hosted with ❤ by GitHub
# time limit exceeded for some reason
# tested with 100x100 map and it runs fine locally
# updated according to the editorial
# catered to handle double-counting when turning a corner
# without passing through mouse
# standard DP problem with a twist.
# the approach I chose:
# 1. create an influence map not unlike those in game AI
# 2. add the influence value at every point of the path
# 3. deduct appropriate values when a mouse is double-counted
# the rules for detecting double-counting mice:
# 1. if a mouse moves right from tile x1 to tile x2 and there
# is a mouse at x2, deduct 1
# 2. if a mouse moves down from tile y1 to tile y2 and there
# is a mouse at y2, deduct 1
# 3. if a mouse moves from tile t to any tile, and there is a
# mouse at t, deduct 1
import sys
T = int(sys.stdin.readline().strip())
for t in xrange(T):
n,m = sys.stdin.readline().strip().split()
n,m = int(n), int(m)
mapp = []
# read map
for i in xrange(n):
mapp.append(sys.stdin.readline().strip())
# create influence map
influence = []
for i in range(n):
influence.append([0] * m)
for y in xrange(n):
for x in xrange(m):
if mapp[y][x] == "1":
influence[y][x] += 1
if x-1 >= 0:
influence[y][x-1] += 1
if y-1 >= 0:
influence[y-1][x] += 1
if x+1 < m:
influence[y][x+1] += 1
if y+1 < n:
influence[y+1][x] += 1
# run DP
dp = []
for i in range(n):
b = []
dp.append(b)
for j in range(m):
b.append([0,0]) # 0 for left, 1 for top
for y in xrange(n):
for x in xrange(m):
dp[y][x][0] += influence[y][x]
dp[y][x][1] += influence[y][x]
# from left
if x-1 >= 0:
fromleft = min(dp[y][x-1][0], dp[y][x-1][1]-int(mapp[y-1][x]) if y-1 >= 0 else dp[y][x-1][1])
# rule 1
if mapp[y][x] == "1":
fromleft -= 1
# rule 3
if mapp[y][x-1] == "1":
fromleft -= 1
# from top
if y-1 >= 0:
fromtop = min(dp[y-1][x][1], dp[y-1][x][0]-int(mapp[y][x-1]) if x-1 >= 0 else dp[y-1][x][0])
# rule 2
if mapp[y][x] == "1":
fromtop -= 1
# rule 3
if mapp[y-1][x] == "1":
fromtop -= 1
if x-1 < 0 and y-1 < 0:
pass
elif x-1 < 0:
dp[y][x][1] += fromtop
dp[y][x][0] += fromtop
elif y-1 < 0:
dp[y][x][0] += fromleft
dp[y][x][1] += fromleft
else:
dp[y][x][0] += fromleft
dp[y][x][1] += fromtop
#print dp[y]
print min(dp[y][x][0], dp[y][x][1])
view raw gistfile1.txt hosted with ❤ by GitHub

Thursday, June 20, 2013

Codechef May 2013 Tree

# a dive into the deep, a lot of concepts here
# Kirchoff's Matrix Tree Theorem, Laplacian matrix, cofactors, a revision into
# determinants
# Revision: replacing a row by itself minus a multiple of another row:
# doesn't change determinant
# k=3, A =
# 0,0,0,1,1,1,1,1,1.......1
# 0,0,0,1,1,1,1,1,1.......1
# 0,0,0,1,1,1,1,1,1.......1
# 1,1,1,0,0,0,1,1,1.......1
# 1,1,1,0,0,0,1,1,1.......1
# 1,1,1,0,0,0,1,1,1.......1
# 1,1,1,1,1,1,0,0,0.......1
# 1,1,1,1,1,1,0,0,0.......1
# 1,1,1,1,1,1,0,0,0.......1
# ............
# ............
# 1,1,1,1,1,1,1,1,1,1,0,0,0
# D =
# 3n-3,0,0,0,0,0,.....
# 0,3n-3,0,0,0,0,0,0..
# 0,0,3n-3,0,0,0,0,0..
# ....
# ....
# 0,0,0,0,0........0,0,3n-3
# Laplacian matrix = D - A
# =
# 3n-3,0,0,-1,-1,-1,-1,-1,-1,-1....-1
# 0,3n-3,0,-1,-1,-1,-1,-1,-1,-1....-1
# 0,0,3n-3,-1,-1,-1,-1,-1,-1,-1....-1
# .....
# -1,-1,-1,-1,-1,-1,-1...........3n-3
# taking away last row, and column
# Laplacian matrix = D - A
# =
# 3n-3,0,0,-1,-1,-1,-1,-1,-1,-1....-1
# 0,3n-3,0,-1,-1,-1,-1,-1,-1,-1....-1
# 0,0,3n-3,-1,-1,-1,-1,-1,-1,-1....-1
# .....
# -1,-1,-1,-1,.......0,3n-3,0,-1-1
# -1,-1,-1,-1,.......0,0,3n-3,-1-1
# -1,-1,-1,-1,-1,-1,-1........3n-3,0
# -1,-1,-1,-1,-1,-1,-1........0,3n-3
# =
# 3n-3,3-3n,0,0,0,0,0............0 normalized = 1,-1,0000
# 0,3n-3,3-3n,0,0,0,0............0 normalized = 0,1,-1,00
# 1,1,3n-2,2-3n,-1,-1,0,0,0......0 -= row1 + row2*2
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0 # same
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0 # same
# 0,0,0,1,1,3n-2,2-3n,-1,-1,0,0..0 # same
# ....
# 0,0,0..............3n-2,2-3n,-1
# 0,0,0..................3n-3,3-3n
# -1,-1,-1,-1,-1,-1........0,3n-3
# =
# 3n-3,3-3n,0,0,0,0,0............0
# 0,3n-3,3-3n,0,0,0,0............0
# 0,0,3n,2-3n,-1,-1,0,0,0........0
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
# 0,0,0,0,0,3n,2-3n,-1,-1,0,0....0
# ....
# 0,0,0.................3n,2-3n,-1
# 0,0,0..................3n-3,3-3n
# -1,-1,-1,-1,-1,-1........0,3n-3
# =
# 3n-3,3-3n,0,0,0,0,0............0
# 0,3n-3,3-3n,0,0,0,0............0
# 0,0,3n,-3n,0,0,0,0,0...........0
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
# ....
# 0,0,0.................3n,2-3n,-1
# 0,0,0..................3n-3,3-3n
# -1,-1,-1,-1,-1,-1........0,3n-3
# =
# 3n-3,3-3n,0,0,0,0,0............0 = 1,-1, 0, 0, 0 * 1
# 0,3n-3,3-3n,0,0,0,0............0 = 0, 1,-1, 0, 0 * 2
# 0,0,3n,-3n,0,0,0,0,0...........0 = 0, 0, 1,-1, 0 * 3
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0 = 0, 0, 0, 1,-1 * 4
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0 ......
# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
# ....
# ......... .0,0,0,3n-3,3-3n, 0, 0 = ............1,-1 * (3n-4)
# 0,0,0..................3n,1-3n,0
# 0,0,0..................3n-3,3-3n
# -1,-1,-1,-1,-1,-1...-1,-1,0,3n-3
# =
# 3n-3,3-3n,0,0,0,0,0............0
# 0,3n-3,3-3n,0,0,0,0............0
# 0,0,3n,-3n,0,0,0,0,0...........0
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
# ....
# 0,0,0..................3n,1-3n,0
# 0,0,0................0,3n-3,3-3n
# 0,0,0................3-3n,0,3n-3
# =
# 3n-3,3-3n,0,0,0,0,0............0
# 0,3n-3,3-3n,0,0,0,0............0
# 0,0,3n,-3n,0,0,0,0,0...........0
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
# ....
# 0,0,0...................3n,1-3n,0
# 0,0,0..................0,3n-3,3-3n = 0,1,-1
# 0,0,0..................3-3n,0,3n-3 = -1,0,1
# =
# 3n-3,3-3n,0,0,0,0,0............0
# 0,3n-3,3-3n,0,0,0,0............0
# 0,0,3n,-3n,0,0,0,0,0...........0
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
# ....
# 0,0,0..................1,0,0
# 0,0,0..................0,3n-3,3-3n
# 0,0,0..................3-3n,0,3n-3
# =
# 3n-3,3-3n,0,0,0,0,0............0
# 0,3n-3,3-3n,0,0,0,0............0
# 0,0,3n,-3n,0,0,0,0,0...........0
# 0,0,0,3n-3,3-3n,0,0,0,0,0......0
# 0,0,0,0,3n-3,3-3n,0,0,0,0......0
# 0,0,0,0,0,3n,-3n,0,0,0,0.......0
# ....
# 0,0,0..................1,0,0
# 0,0,0..................0,3n-3,3-3n
# 0,0,0..................0,0,3n-3
# cofactor(3n,3n) = (3n-3)^(2n) * (3n)^(n-2)
# finally correct; spent 3 hours figuring this out
import sys
def modular_exponent(a,b,n):
binary = ""
while b > 0:
if b & 1 == 0:
binary += "0"
else:
binary += "1"
b >>= 1
result = 1
for k in xrange(len(binary)):
result = (result * result) % n
if binary[len(binary)-k-1] == "1":
result = (result * a) % n
return result
T = sys.stdin.readline().strip()
n,k = T.split()
n = int(n)
k = int(k)
print (modular_exponent(k*(n-1),n*(k-1),10**9+7)* modular_exponent(k*n,n-2,10**9+7)) % (10**9+7)
view raw gistfile1.txt hosted with ❤ by GitHub

Google Code Jam Qualification Round 2009 Problem A. Alien Language

First time using Python sets.
import sys
# return a list of all tokens from a case
# e.g. abc(abc)b(ab) returns [a,b,c,abc,b,ab]
def getTokens(case):
tokens = []
token1 = case.split(")")
for t in token1:
t2 = t.split("(")
for c in t2[0]:
tokens.append(c)
if len(t2) > 1:
tokens.append(t2[1])
return tokens
# return all dictionary entries that has
# that token at that position
# e.g. getEntries(0,"ab") returns all entries
# that has either a or b at pos 0
# returns a set so no overlap/duplicate entry
def getEntries(pos,token):
result = set([])
for c in token:
if (pos,c) in sets:
result |= sets[(pos,c)]
return result
L,D,N = sys.stdin.readline().strip().split()
L = int(L)
D = int(D)
N = int(N)
# initialize map of characters to dictionary entry
# dictionary[(position, letter)] = set of all dictionary entries
# that has that letter at that position
sets = {}
for d in xrange(D):
entry = sys.stdin.readline().strip()
l = 0
for c in entry:
if (l,c) in sets:
sets[(l,c)].add(entry)
else:
sets[(l,c)] = set([entry])
l += 1
for n in xrange(N):
# 1. read case, split into tokens
# 2. for each position/token get all entries that has that token at position
# 3. then get the entries common to all tokens/is present at every position
case = sys.stdin.readline().strip()
tokens = getTokens(case)
possible = getEntries(0,tokens[0])
for l in xrange(1,L):
possible &= getEntries(l, tokens[l])
print "".join(["Case #",str(n+1),": ",str(len(possible))])
view raw gistfile1.txt hosted with ❤ by GitHub

Wednesday, June 19, 2013

Win32 programming: random messages on the screen

I've always wondered how typical keygen programs, when run, doesn't create a window on screen. Or rather, technically, it's still a window, but there are no title bars, no _ □ X buttons, no borders, and even the background is transparent. Well, after viewing some basic Win32 tutorials and meddling with windows style I managed to satisfy my curiosity:
#include "stdafx.h"
#include "win32_gui_test.h"
#define MAX_LOADSTRING 100
// Global Variables:
HINSTANCE hInst; // current instance
TCHAR szTitle[MAX_LOADSTRING]; // The title bar text
TCHAR szWindowClass[MAX_LOADSTRING]; // the main window class name
// Forward declarations of functions included in this code module:
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM);
int APIENTRY _tWinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPTSTR lpCmdLine,
int nCmdShow)
{
UNREFERENCED_PARAMETER(hPrevInstance);
UNREFERENCED_PARAMETER(lpCmdLine);
// TODO: Place code here.
MSG msg;
HACCEL hAccelTable;
// Initialize global strings
//LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadString(hInstance, 0, szTitle, MAX_LOADSTRING);
LoadString(hInstance, IDC_WIN32_GUI_TEST, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);
// Perform application initialization:
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_WIN32_GUI_TEST));
// Main message loop:
while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
return (int) msg.wParam;
}
//
// FUNCTION: MyRegisterClass()
//
// PURPOSE: Registers the window class.
//
// COMMENTS:
//
// This function and its usage are only necessary if you want this code
// to be compatible with Win32 systems prior to the 'RegisterClassEx'
// function that was added to Windows 95. It is important to call this function
// so that the application will get 'well formed' small icons associated
// with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW ;
wcex.lpfnWndProc = WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_WIN32_GUI_TEST));
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)0;//(HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = 0;//MAKEINTRESOURCE(IDC_ARK2_GUI);
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = 0;//LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));
return RegisterClassEx(&wcex);
}
//
// FUNCTION: InitInstance(HINSTANCE, int)
//
// PURPOSE: Saves instance handle and creates main window
//
// COMMENTS:
//
// In this function, we save the instance handle in a global variable and
// create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HWND hWnd;
hInst = hInstance; // Store instance handle in our global variable
hWnd = CreateWindow(szWindowClass, 0, 0,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
SetWindowLong(hWnd, GWL_STYLE, ~WS_CAPTION & ~WS_VSCROLL & ~WS_HSCROLL & ~WS_THICKFRAME);
if (!hWnd)
{
return FALSE;
}
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
return TRUE;
}
//
// FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
// PURPOSE: Processes messages for the main window.
//
// WM_COMMAND - process the application menu
// WM_PAINT - Paint the main window
// WM_DESTROY - post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
PAINTSTRUCT ps;
HDC hdc;
HFONT font;
RECT rect;
switch (message)
{
case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
// Parse the menu selections:
switch (wmId)
{
case IDM_ABOUT:
DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
break;
case IDM_EXIT:
DestroyWindow(hWnd);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
break;
case WM_MOVE:
GetClientRect(hWnd, &rect);
InvalidateRect(hWnd,&rect, true);
break;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
SetBkMode(hdc, TRANSPARENT);
GetClientRect(hWnd, &rect);
//DrawText(hdc, TEXT("Hello, win32!"),-1,&rect,DT_SINGLELINE | DT_CENTER | DT_VCENTER);
SetTextColor(hdc, RGB(255,0,0));
font = CreateFont(46*2, 28*2, 215, 0,
FW_NORMAL, FALSE, FALSE, FALSE,
ANSI_CHARSET, OUT_DEFAULT_PRECIS,
CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY,
DEFAULT_PITCH | FF_ROMAN,
L"Times New Roman");
SelectObject(hdc, font);
TextOut(hdc, 50, 400, L"HELLO WIN32", 12);
EndPaint(hWnd, &ps);
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
UNREFERENCED_PARAMETER(lParam);
switch (message)
{
case WM_INITDIALOG:
return (INT_PTR)TRUE;
case WM_COMMAND:
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return (INT_PTR)TRUE;
}
break;
}
return (INT_PTR)FALSE;
}
view raw gistfile1.txt hosted with ❤ by GitHub
Next step, to make it drag-able!

Tuesday, June 18, 2013

Codechef May 2013 WitMath

I thought that by referencing the editorial and following faithfully I could have the solution out in minutes. Turned out to be hours..totally forgot how to do repeated squaring. Good revision, this was.
# My first attempt at implementing Miller-Rabin primality test
# decided to implement it instead of stealing from somewhere
# in order to understand it
# v2. fixed the miller rabin pass function. Now correct.
# v3. a**s is too slow for large numbers
# v4. using def apowbmodn(a,b,n):
# if b==1: return a
# return apowbmodn(a*a,b/2,n) if b%2==0 else apowbmodn(a,b-1,n)*a
# is too slow! My guess is that the stack isn't that huge to accomodate such
# computation.
# v5. redesigned my modular exponential function.
# I studied the solution from
# http://www.codechef.com/viewsolution/2167990
# got an Non Zero Exit Code error =\
# v6. getting an OverflowError in the statement for i in xrange(N-1)
# fixed; no longer using xrange
import random
import sys
def miller_rabin_pass(a,r,n):
a = a % n
if a == 1: return True
for z in xrange(r-1):
if a == n-1: return True
a = (a*a) % n
return a == n-1
def apowbmodn(a,b,n):
binary = ""
while b > 0:
if b & 1 == 0:
binary += "0"
else:
binary += "1"
b >>= 1
result = 1
for i in xrange(len(binary)):
result = (result * result)%n
if binary[len(binary)-i-1] == "1":
result = (result * a)%n
return result
def isProbablyPrime(n):
if n == 2: return True
if n % 2 == 0: return False
random.seed()
if n < 100:
for i in xrange(2,n): # lazy to put sqrt
if n%i ==0: return False
return True
else:
s = n-1
r = 0
while s % 2 == 0:
r += 1
s /= 2
for z in xrange(30):
a = int(random.random() *(n-1))+1
if not miller_rabin_pass(apowbmodn(a,s,n),r,n):
return False
return True
T = int(sys.stdin.readline().strip())
for z in xrange(T):
N = int(sys.stdin.readline().strip())
while 1:
if isProbablyPrime(N):
print N
break
N -= 1
view raw gistfile1.txt hosted with ❤ by GitHub

Monday, June 17, 2013

Codechef June 2013 Delish

I worked for hours on this one, just for my solution to be rejected. =( But the hard work paid off, my solution came very close to the one in the editorial =) This one didn't get accepted:
# just some test inut
# 10 -1 -1 -1 -1 1 -9 8 -99 2000 0 -1 -1
# and just playing around with DP
# 6 -4 -3 -2 -1
# 7 -3 -2 -1 0 1
# -2 -12 -11 -10 -9 -8 -9
# 6 -4 -3 -2 -1 0 -1 8
# -84 -94 -103 -102 -101 -100 -99 -100 -91
# Managed to hit upon this property after thinking for hours
# Edit: This is mentioned in the editorial too
# Property 1:
# j and k cannot have gap
# because if have gap > 0, one side will eat it up
# hence for each middle position j or k
# calculate the min/max values for each section, one to the left
# and one to the right of j/k
# then calculate the largest absolute difference between each
# pair of left/right sections
# Property 2:
# if I need the minimum value, and the sum of all elements
# before this is > 0, then why shouldn't I leave them all out?
# I should do this checking at every point where the previous
# value is positive and my current number is negative.
# EDIT: from the editorial I learnt that I should check at every
# point, not just the points I've chosen.
# need to speed it up
import sys
T = int(sys.stdin.readline().strip())
for z in range(T):
N = int(sys.stdin.readline().strip())
numbers = []
leftMins = []
leftMaxs = []
rightMins = []
rightMaxs = []
max_delish = 0
lines = sys.stdin.readline().strip()
for n in lines.split(" "):
numbers.append(int(n))
leftMins.append(10000001)
leftMaxs.append(-10000001)
rightMins.append(10000001)
rightMaxs.append(-10000001)
i_min = 0
i_max = 0
leftMins[0] = numbers[0]
leftMaxs[0] = numbers[0]
rightMins[len(numbers)-1] = numbers[len(numbers)-1]
rightMaxs[len(numbers)-1] = numbers[len(numbers)-1]
# for left sides
for j in range(1,N-1):
# for minimums
if numbers[j] <= 0 and numbers[j-1] > 0:
# try to move i
if leftMins[j-1] >= 0:
i_min = j
leftMins[j] = numbers[j]
else:
leftMins[j] = leftMins[j-1] + numbers[j]
else:
leftMins[j] = leftMins[j-1] + numbers[j]
# for maximums
if numbers[j] >= 0 and numbers[j-1] < 0:
# try to move i
if leftMaxs[j-1] <= 0:
i = j
leftMaxs[j] = numbers[j]
else:
leftMaxs[j] = leftMaxs[j-1] + numbers[j]
else:
leftMaxs[j] = leftMaxs[j-1] + numbers[j]
l_min = len(numbers)-1
l_max = len(numbers)-1
# for right sides
for z in range(1,N-1):
j = N - 1 - z
# for minimums
if numbers[j] <= 0 and numbers[j+1] > 0:
# try to move i
if rightMins[j+1] >= 0:
l_min = j
rightMins[j] = numbers[j]
else:
rightMins[j] = rightMins[j+1] + numbers[j]
else:
rightMins[j] = rightMins[j+1] + numbers[j]
# for maximums
if numbers[j] >= 0 and numbers[j+1] < 0:
# try to move i
if rightMaxs[j+1] <= 0:
l_max = j
rightMaxs[j] = numbers[j]
else:
rightMaxs[j] = rightMaxs[j+1] + numbers[j]
else:
rightMaxs[j] = rightMaxs[j+1] + numbers[j]
max_delish = 0
for j in range(N-1):
k = j+1
delish = max(rightMaxs[k] - leftMins[j], leftMaxs[j] - rightMins[k])
if delish > max_delish:
max_delish = delish
print max_delish
view raw gistfile1.txt hosted with ❤ by GitHub
Did my correction and got it accepted:
# Correction after viewing the editorial
# Property 1:
#j and k cannot have gap
#because if have gap > 0, one side will eat it up
# hence for each middle position j or k
# calculate the min/max values for each section, one to the left
# and one to the right of j/k
# then calculate the largest absolute difference between each
# pair of left/right sections
import sys
T = int(sys.stdin.readline().strip())
for z in range(T):
N = int(sys.stdin.readline().strip())
numbers = []
leftMins = []
leftMaxs = []
rightMins = []
rightMaxs = []
max_delish = 0
lines = sys.stdin.readline().strip()
for n in lines.split(" "):
numbers.append(int(n))
leftMins.append(10000001)
leftMaxs.append(-10000001)
rightMins.append(10000001)
rightMaxs.append(-10000001)
leftMins[0] = numbers[0]
leftMaxs[0] = numbers[0]
rightMins[len(numbers)-1] = numbers[len(numbers)-1]
rightMaxs[len(numbers)-1] = numbers[len(numbers)-1]
# for left sides
for j in range(1,N-1):
# for minimums
if leftMins[j-1] >= 0:
leftMins[j] = numbers[j]
else:
leftMins[j] = leftMins[j-1] + numbers[j]
# for maximums
if leftMaxs[j-1] <= 0:
leftMaxs[j] = numbers[j]
else:
leftMaxs[j] = leftMaxs[j-1] + numbers[j]
# for right sides
for z in range(1,N-1):
j = N - 1 - z
# for minimums
if rightMins[j+1] >= 0:
rightMins[j] = numbers[j]
else:
rightMins[j] = rightMins[j+1] + numbers[j]
# for maximums
if rightMaxs[j+1] <= 0:
rightMaxs[j] = numbers[j]
else:
rightMaxs[j] = rightMaxs[j+1] + numbers[j]
max_delish = 0
for j in range(N-1):
k = j+1
delish = max(rightMaxs[k] - leftMins[j], leftMaxs[j] - rightMins[k])
if delish > max_delish:
max_delish = delish
print max_delish
view raw gistfile1.txt hosted with ❤ by GitHub

Codechef June 2013 Wstring

Seen the editorial, the algorithm described is exactly the same as what I did..but my solution is not accepted. I don't know why ='(
# 1. partition into substrings separated by #
# 2. for every substring, create map of symbols and their frequencies
# 3. for every set of 3 points, from the first 3 to the last 3, compute longest length
# 4. length for each set of points = longest length for the 4 partitions:
# a. all partitions, merged as one, before P1
# b. partition between P1 and P2
# c. partition between P2 and P3
# d. all partitions, merged as one, after P3
# can optimize step 4 by maintaining a map for 4a and 4b each.
import sys
def getMaxFrequency(freq):
maxFreq = 0
key = -1
for k in freq.keys():
if freq[k] > maxFreq:
maxFreq = freq[k]
key = k
return maxFreq
def compileFrequencies(flist):
a = {}
for f in flist:
for k in f.keys():
if k in a:
a[k] += f[k]
else:
a[k] = f[k]
return a
def minusFrequencies(one, two):
a = one
for k in two.keys():
a[k] -= two[k]
return a
T = int(sys.stdin.readline().strip())
for z in range(T):
S = sys.stdin.readline().strip()
# create partitions and frequency dictionary
partitions = []
prevIndex = S.find("#")
frequencies = {}
for c in S[:prevIndex]:
if c in frequencies:
frequencies[c] += 1
else:
frequencies[c] = 1
partitions.append(frequencies)
while prevIndex != -1:
nextIndex = S.find("#", prevIndex+1)
frequencies = {}
if nextIndex == -1:
for c in S[prevIndex+1:]:
if c in frequencies:
frequencies[c] += 1
else:
frequencies[c] = 1
else:
for c in S[prevIndex+1:nextIndex]:
if c in frequencies:
frequencies[c] += 1
else:
frequencies[c] = 1
#print getMaxFrequency(frequencies)
partitions.append(frequencies)
prevIndex = nextIndex
# cannot have empty partitions
error = False
for p in partitions:
if len(p) == 0:
error = True
if len(partitions) < 4:
error = True
#print partitions
if error != True:
max_length = 0
allLeft = partitions[0]
allRight = compileFrequencies(partitions[3:])
#print allRight
i = 0
max_length = 3 + getMaxFrequency(allLeft) + getMaxFrequency(partitions[i+1]) + getMaxFrequency(partitions[i+2]) + getMaxFrequency(allRight)
for i in range(1,len(partitions)-3):
# alter allLeft and allRight
allLeft = compileFrequencies([allLeft, partitions[i]])
allRight = minusFrequencies(allRight, partitions[i+3])
length = 3 + getMaxFrequency(allLeft) + getMaxFrequency(partitions[i+1]) + getMaxFrequency(partitions[i+2]) + getMaxFrequency(allRight)
if length > max_length:
max_length = length
#length = 3 + 1
print max_length
else:
print 0
view raw gistfile1.txt hosted with ❤ by GitHub

Codechef June 2013 Predictopus

Was wondering for a while if the each test case is accumulative from the previous...turned out it was not. Accepted!
# Let p = probability that team A win
# M = amount of rupees bet on team A
# R = number of rupees = 10000
# E = max expected rupees
# Hence,
# R-M = number of rupees bet on team B
# 1-p = probability that team B wins
# Expected rupees
# = p(M + M * (2-2p)) + (1-p)((R-M) + (R-M) * (2-2(1-p)))
# = pM + pM(2-2p) + (1-p)(R-M) + (1-p)(R-M)(2p)
# = pM + 2pM -2ppM + R-Rp -M +pM + (2p-2pp)(R-M)
# = 4pM - 2ppM +R-Rp-M + 2pR - 2ppR -2pM +2ppM
# = 2pM + R -Rp - M + 2pR - 2ppR
# = 2pM + R - M + pR - 2ppR
# = M(2p-1) + R - pR - 2ppR
# For each case, p and R are constant.
# Take the derivative of E against M
# to find value of M which E is greatest
# That value = 2p-1.
# If p > 0.5, increasing M will increase E
# If p < 0.5, increasing M will decrease E
# Hence if p > 0.5 bet everything on team A
# else if p < 0.5 bet everything on team B
# Verification: expected rupees
# = p[M( 1 + (2-2p))] + (1-p)[(R-M)(1+2p)]
# = pM(3 - 2p) + (R-M) (1+p-2pp)
# = 3pM - 2ppM + R + Rp - 2ppR - M - pM + 2ppM
# = 2pM + R + Rp - 2ppR - M
# = pM - M + pM + R + Rp - 2ppR
# = M(p-1) + pM + R(1+p-2pp)
import sys
T = int(sys.stdin.readline().strip())
R = 10000
for i in range(T):
p = float(sys.stdin.readline().strip())
if p > 0.5:
print(p*(R+R*(2-2*p)))
else:
print((1-p)*(R+R*2*p))
view raw gistfile1.txt hosted with ❤ by GitHub

Codechef June 2013 Lapindromes

Accepted!
# 1. split string into two sections along the middle
# 2. use a associative array to store frequency of letters in each part
# 3. compare the 2 associative arrays
# 4. win!
import sys
T = int(sys.stdin.readline().strip())
for i in range(T):
p = sys.stdin.readline().strip()
if (len(p) % 2 == 0):
# even
part1 = p[0:(len(p)/2)]
part2 = p[len(p)/2:]
else:
# odd
part1 = p[0:int(len(p)/2)]
part2 = p[int(len(p)/2)+1:]
a = {}
b = {}
for c in part1:
if (c in a):
a[c]+=1
else:
a[c] = 1
for c in part2:
if (c in b):
b[c]+=1
else:
b[c]=1
palid = True
for key in a.keys():
#print(key, ":", a[key])
if key not in b or a[key] != b[key]:
palid = False
for key in b.keys():
#print(key, ":", a[key])
if key not in a or a[key] != b[key]:
palid = False
if palid:
print ("YES")
else:
print("NO")
view raw gistfile1.txt hosted with ❤ by GitHub

Friday, June 14, 2013

Google Code Jam 2009, Round 1C, Problem A: All Your Base

Here is a nice summary of the approach to this problem.
The above problem statement, requires the output to be the minimum possible number. The first step is to understand that the number would be smaller if you take the smallest possible 'Base System' for the number. To find the base system that you want, you would have to find the number of unique symbols in the input string. If there are 2 'Unique' symbols in the string, take it as 'Base 2' system. If there are 10 unique symbols, take it as 'Base 10 (Decimal)' system.....and so on. Since the 'Unary System' is not used, ignore that. 
After that, we need to find how we can make the sum, as minimal as possible. Since we don't know which digit stands for what, we have to make a decision for each symbol, so as to make the number, as small as possible. Since the left most digit carries more weight, this digit should be multiplied by the smallest digit. But since the left-most digit can't be zero (0), make it '1'. Use the Zero (0) for the second left-most digit (if there is 2nd digit in the number). Then use '2' for the third left most digit (if it is unique), '3' for the 4th left most digit (if it is unique)..and so on, unitl the end of the string with symbols. 
// Google code jam Round 1C 2009
// Problem A: All Your Base
// sirpoot
#include <iostream>
#include <string>
#include <map>
#include "math.h"
#include "bigint.h"
using namespace std;
BigInt power(int one, int two)
{
if (two == 0) return 1;
BigInt a = one;
for (int i=1;i<two;i++)
{
a *= one;
}
return a;
}
int main()
{
int T;
cin >> T;
for (int n=0;n<T;n++)
{
string input;
map <char, int> val;
cin >> input;
//cout << input << endl;
// 1. count number of unique symbols
int symbols = 0;
for (int i=0;i<input.size();i++)
{
if (val.count(input.at(i)) <= 0)
{
symbols++;
val[input.at(i)] = -1;
}
}
// 2. assign values to symbols. First encountered symbol has value of 1, second encountered is 0
// third encountered symbol is 3, 4th is 4, 5th is 5....
int nextVal = 0;
for (int i=0;i<input.size();i++)
{
if (val[input.at(i)] == -1)
{
val[input.at(i)] = nextVal == 0 ? 1 : (nextVal == 1 ? 0 : nextVal);
//cout << input.at(i) << " = " << (nextVal == 0 ? 1 : (nextVal == 1 ? 0 : nextVal)) << endl;
nextVal++;
}
}
// 3. calculate minimum seconds remaining
BigInt sum = 0;
int base = symbols;
base = base < 2 ? 2 : base; // not using unary
for (int i=0;i<input.size();i++)
{
//cout << power(base, input.size()-1-i) * val[input.at(i)]<< " + ";
sum += power(base, input.size()-1-i) * val[input.at(i)];
}
cout << "Case #" << n+1 << ": " << sum << endl;
}
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub
^^

Thursday, June 13, 2013

ACM 103 Stacking Boxes

Greedy problem. For each box, sort each dimension from biggest to smallest. Then, sort all boxes from smallest to biggest. Apply some dynamic programming and viola!
// acm uva 103 stacking boxes
// sirpoot
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 30
int dimension;
int num_box;
int** box;
int max_length[MAX];
int from[MAX];
int label[MAX];
using namespace std;
bool can_nest(int* inner, int* outer)
{
for (int i=0;i<dimension;i++)
{
if (inner[i] >= outer[i])
return false;
}
return true;
}
void recursePrint(int box)
{
if (from[box] != -1)
recursePrint(from[box]);
cout << label[box] << " ";
}
int main()
{
while (cin >> num_box >> dimension)
{
// input
box = new int*[num_box];
for (int i=0;i<num_box;i++)
{
box[i] = new int[dimension];
for (int k=0;k<dimension;k++)
{
cin>>box[i][k];
}
sort(box[i], box[i]+dimension);
}
// done input, init
for (int i=0;i<MAX;i++)
for (int j=0;j<MAX;j++)
{
max_length[i] = 1;
from[i] = -1;
label[i] = i+1;
}
// done init, process
// first, sort boxes from smallest to biggest
for (int i=0;i<num_box;i++)
{
for (int j=i-1;j>=0;j--)
{
if (can_nest(box[j+1],box[j]))
{
int* temp;
// swap box
temp = box[j];
box[j] = box[j+1];
box[j+1] = temp;
// swap label
int temp2;
temp2 = label[j];
label[j] = label[j+1];
label[j+1] = temp2;
}
}
}
// do the DP
for (int i=0;i<num_box;i++)
{
// with i as end point
for (int j=i-1;j>=0;j--)
{
if (i==j) continue;
if (can_nest(box[j],box[i]))
{
if (max_length[j] + 1 >= max_length[i])
{
max_length[i] = max_length[j] + 1;
from[i] = j;
}
}
}
}
// processing done, analyze results
int max_max_length = 0;
int max_box = -1;
for (int i=0;i<num_box;i++)
{
if (max_length[i] > max_max_length)
{
max_max_length = max_length[i];
max_box = i;
}
}
// analysis done, output
cout << max_max_length << "\n";
recursePrint(max_box);
cout <<"\n";
}
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub