Wednesday, November 28, 2007

The Persuit of Happyness

Hi,
Well, today I am not here for posting a gazal or a puzzle. I watched a movie which forced me to write over here.

Today I watched "The Persuit of Happyness", well the 'y' in the "Happyness" is intentional and someone who has watched that movie would understand why. The movie is based on the true story of Chris Gardner who is a self made entrepreneur and a millionaire. It is really a must watch movie. The movie is not for entertainment but for inspiration. Will Smith truly gave justice to the character of Chris.

It was amazing to watch how Chris managed to take care of his son and manage to do his unpaid internship even when he was broke. How he convinced his son to sleep in a 'cave' through his 'time machine'. When everything was going wrong, he continued to see the bright and pursued the right. We find it very convenient to blame it on the circumstances when we don't have enough guts and courage to fight through it. The movie really teaches a lesson to never give up and to believe that "everything's gonna be fine".

I don't know how well I can follow the ideas depicted in that movie. But I will definitely remember this movie for it's unforgettable inspirational appeal.

Tuesday, November 27, 2007

Nice gujarati gazal by Befam

Hi,
I came across this nice gazal from here.

વ્યર્થ દુનિયામાં પ્રણયને આંધળો કહેવાય છે
તું નયન સામે નથી, તોપણ મને દેખાય છે.

જ્યાં જુઓ ત્યાં બધે એક જ વદન દેખાય છે
કોઇને એક વાર જોયા બાદ, આવું થાય છે?

એમ તો એનું અચાનક પણ મિલન થઇ જાય છે
શોધમાં નીકળું છું ત્યારે જ કેમ એ સંતાય છે

આવ મારાં આંસુની થોડી ચમક આપું તને,
તું મને જોઇને બહું ઝાંખી રીતે મલકાય છે.

એટલે સાકી, સુરા પણ આપજે બમણી મને,
મારા માથા પર દુઃખોની પણ ઘટા ઘેરાય છે.

હોય ના નહિ તો બધોય માર્ગ અંધારભર્યો,
લાગે છે કે આપની છાયા બધે પથરાય છે.

હું કરું છું એના ઘરની બંધ બારી પર નજર,
ત્યારે ત્યારે મારી આંખોમાં જ એ ડોકાય છે.

પ્યાર કરવો એ ગુનો છે એમ માને છે જગત,
પણ મને એની સજા તારા તરફથી થાય છે.

છે લખાયેલું તમારું નામ એમાં એટલે,
લેખ મારાથી વિધિના પણ હવે વંચાય છે.

છે અહીં ‘બેફામ’ કેવળ પ્રાણની ખુશ્બૂ બધી,
પ્રાણ ઊડી જાય છે તો દેહ પણ ગંધાય છે.


-બરકત વિરાણી “બેફામ”

Monday, November 19, 2007

Treasure of urdu poetry ( shayari)

Hi All,
Very nice collection of urdu poetry can be found here .

Thanks to ali for forwarding me such a nice collection.

Friday, November 02, 2007

A gazal by Saif Palanpuri

Hi,
Well, it has been a very long break here. I know, and I think I am still going to be very less frequent because of the coursework load ( Yeah I know, it is a nice excuse! )

Received this nice gazal in my orkut inbox.

-----------
ખુશ્બૂમાં ખીલેલા ફૂલ હતાં ઊર્મિમાં ડૂબેલા જામ હતા,
શું આંસુનો ભૂતકાળ હતો - શું આંસુનાં પણ નામ હતાં.

થોડીક શિકાયત કરવી’તી થોડક ખુલાસા કરવા’તા,
ઓ મોત જરા રોકાઈ જતે - બેચાર મને પણ કામ હતાં.

હું ચાંદની રતે નીકળ્યો’તો ને મારી સફર ચર્ચાઈ ગઈ,
કંઈ મંઝિલ પણ મશહૂર હતી - કંઈ રસ્તા પણ બદનામ હતાં.

જીવનની સમી સાંજે મારે જખ્મોની યાદી જોવી’તી,
બહુ ઓછાં પાનાં જોઈ શક્યો બહુ અંગત અંગત નામ હતાં.

પેલા ખૂણે બેઠા છે એ “સૈફ” છે મિત્રો જાણો છો ?!
કેવો ચંચલ જીવ હતો ને કેવા રમતારામ હતા !

’સૈફ’ પાલનપુર
------------

Saturday, September 22, 2007

A nice gujarati poem

Hi,
I received this poem from someone special. It it not written by her but it truely reflects the state of her heart :-)
-----------------------------------------------
કાગળમાં તારી યાદના કિસ્સાઓ લખ મને,
જો શક્ય હોય તો પ્રેમના ટહુકાઓ લખ મને !

તારા વિના અહીં તો છે ધુમ્મસ ફક્ત બધે,
તારી ગલીમાં કેવા છે તડકાઓ લખ મને !

અકળાઈ જાઉં એવા અબોલા ન રાખ તું,
તારા જ અક્ષરો વડે ઝઘડાઓ લખ મને !

કોઈ મને બીજા તો સહારા નહીં મળે,
અમથા જ તારે હાથે દિલાસાઓ લખ મને !

મારા જીવનનો પંથ હજી તો અજાણ છે,
ક્યાં ક્યાં પડ્યાં છે તારાં પગલાંઓ લખ મને !

Sunday, September 16, 2007

A couple of nice gujarati gazals

ઘરમાં એવાં કો’ક દિવસ ચોઘડિયાં આવે,
ખૂટે આંખમાં પાણી ત્યારે ખડિયા આવે.

ડૂબી ડૂબીને ડૂબવાનું શું માણસમાં ?
એક વેત ઊતરો ને ત્યાં તો તળિયાં આવે.

ડગલું એક ભરી શકવાના હોંશ નથી,પણ
ડગલું એક ભરું તો તારાં ફળિયાં આવે.

ઘંટીના પથ્થરની જેવા વિચાર છે, ને -
મારી તારી વચ્ચે બબ્બે દરિયા આવે.

શબ્દોની હૂંડી લઈ ભાષા સામે ઊભો,
પાછો વળવા જાઉં અને શામળિયા આવે.

-અશરફ ડબાવાલા

-------------------------------------------------------------
હૃદયને રસ્તે હું જન્મ્યો હતો, ખબર છે તને ?
રુદનને બદલે હું મલક્યો હતો, ખબર છે તને ?

હું તારી લટને કિનારે જ આવીને અટક્યો
ક્ષિતિજના ઢાળથી લપસ્યો હતો, ખબર છે તને ?

બિચારા ઈવ કે આદમને કંઈ ખબર ન્હોતી
પ્રણય મેં એમને શીખવ્યો હતો, ખબર છે તને ?
એ વર્ષોમાં તો રચાઈ નહોતી ભાષા છતાં,
હું બૂમ પાડીને બોલ્યો હતો, ખબર છે તને ?

સમયની શોધ થઈ તેની આગલી સાંજે
મેં ઇન્તજારને શોધ્યો હતો, ખબર છે તને ?

-મુકુલ ચોક્સી

Sunday, September 02, 2007

A few more gujarati gems

Hi,
Found some very interesting gujarati shers from an orkut community.
Here they are :
--------------
મરણ નું મૂલ્ય જીવનથી વધારે એ રીતે લાગ્યું,
ન આવે જ્યાં કોઈ મળવાને ત્યાં આખી સભા આવે.............
-----------------
સમયની તો સીમાઓ પૂરી થઈ
હવેજોઈએ કેવી ક્ષણ આવશે

અમસ્તા જ દરવાજો ખોલ્યો અમે
હતી ક્યાં ખબર કે મરણ આવશે?
---------------
જીવન એટલા માટે કોઇ ને અર્પણ કરી દીધુ...,
કે મોત આવે તો કહી શકુ, મિલ્કત પરાઇ છે...
-------------------
હવે તો ‘સૈફ’, ઇચ્છા છે કે મૃત્યુ દ્વાર ખખડાવે:
ઘડીભર તો મને લાગે કોઇના આગમન જેવું !
--------------------
એ બધાં ‘બેફામ’ જે આજે રડે છે મોત પર,
એ બધાંયે જિન્દગી આખી રડાવ્યો છે મને.
-----------------------
મન મરણ પહેલા મરી જય તો કહેવાય નહી
વેદના કામ કરી જાય તો કહેવાય નહી
આંખથી અસ્રુ ખરી જાય તો કહેવાય નહી
ધૈર્ય પણ પાણી ફરી જાય તો કહેવાય નહી
એની આંખોને ફરી આજ સુઝી છે મસ્તી…
દીલ ફરી મુજથી ફરી જાય તો કહેવાય નહી
આંખડી ભોળી, વદન ભોળુ, અદાઓ ભોળી..
પ્રાણ એ રુપ હરી જાય તો કહેવાય નહી…
કંઇ મજા મીઠી તડપ્વામાં મળે છે એ ને…
દીલ વ્યથા વે રે વરી જાય તો કહેવાય નહી
આંખનો દોષ ગણે છે બધા દીલ ને બદ્લે…
ચોર નીર્દોષ ઠરી જાય તો કહેવાય નહી
શોક્નો માર્યો તો મરશે નહી તમારઓ આ “ઘાયલ”
ખ્શી નો માર્યો મરી જાય તો કહેવાય નહી
-”ઘાયલ”
--------------------
‘બેફામ’ તોયે કેટલું થાકી જવું પડ્યું ?
નહિ તો જીવનનો માર્ગ છે ઘરથી કબર સુધી
------------------------
કદર બેફામ શું માંગુ જીવનની એ જગત પાસે,
કે જ્યાંનાં લોકો સૌ કેવળ મરેલાને વખાણે છે.
-------------------------
‘બેફામ’, મારા મૃત્યુ ઉપર સૌ રડે ભલે,
મારા જનમ ઉપર તો ફક્ત હું જ રોઉં છું.
----------------------------
રડ્યા ‘બેફામ’ સૌ મારા મરણ પર એ જ કારણથી,
હતો મારો જ એ અવસર ને મારી હાજરી નહોતી.
-------------------------------

Thursday, August 30, 2007

The Biggest Number

Hi,
Well, I was referred to a very nice article by ali today. It describes human's quest to find the biggest number, in a very interesting way. I actually wished to copy it over here to make sure I do not loose it, in case the original post is removed. But then the it contained some images too. So here is the place where original article can be found :
http://www.scottaaronson.com/writings/bignumbers.html

Sunday, August 26, 2007

Game of Coins

So, I am back again with an interesting puzzle. Credit goes to my dear friend Sambuddha Roy to introduce me to this puzzle as well as its very simple solution.

Here goes the puzzle :

Even number of coins are laid out in a straight line. Coins may have different denominations. Two players p1 and p2 are playing a game. When a player's turn comes he/she has to pick a coin from either end of the line. When all the coins are exhausted, player with the highest amount wins. A tie occurs whent both the player possess the equal amount.

Prove that if p1 goes first, he/she always have the stretagy such that he/she does not loose the game.


Solution :

Solution to this puzzle is very simple and I really felt really stupid when I came to know about the solution and its simplicity. As always, I tried to use induction to prove that p1 always have a winning stretagy ( or non-loosing stretagy). For the case when number of coins is 2, p1 can pick the larger of the two. But then things get complicated when we need to prove the induction step. In fact, I did not spend enough time to prove that using induction.

A very simple solution is that p1 can index the coins from 1 to n. Then, he can calculate sum total of odd-numbered coins as well as even-numbered coins. p1 can always pick coins in a way such that he/she always gets even-numbered or odd-numbered coins depending on which of those will make up a larger amount.

Sunday, August 19, 2007

Space v/s Time

Hi all,
I know there has been a long pause on my blog. Well, it was a transition period for me from IRL to IITK. Yes, I have joined its CSE department as a PhD student. Anyways, I know the title is somewhat misleading as many would think this post has something to do with einstein's theory of relativity and the four dimensional world. You are grossly mistaken if you think so.

Actually, as part of my coursework here I am attending a course by Prof Manindra Aggarwal. Well, it is a big mistake on my side that I have not registered for this course. Even the bigger mistake is that I have registered for a course named "Computational Number Theory and Algebra" by Prof Piyush Kurur. The content itself may be interesting but the way that guy teaches the course, makes it difficult. The worst part is that all the exams of this course are "take home" exams.

Anyways, let's get back to the point. It is indeed an honour to sit in Prof Manindra's class and see him deliver some of the toughest content of the course with a flair. All the people with computer science background are aware of the P not equals NP conjecture. This decade old conjecture has still remain unbeaten. In other words, this conjecture states that the set of problems that can be solved by a deterministic turing machine in polynomial time and the set of problems that can be solved by a non-deterministic turing machine in polynomial time are equal.

There is another notion called Space Complexity in computer science. Space complexity is a measure of the space required to solve any problem by an algorithm. One wonders, whether there is any difference between the set of problems which can be solved by a deterministic turing machine in polynomial space , and the set of problems which can be solved by a non-deterministic turing machine in polynomial space. It actually turns out that non-determinism does not give any more power over deterministic mechanism when space is the criterion. Due to Savitch's theorem it is proven that PSPACE equals NPSPACE.

One may wonder why the similar version in time complexity is yet unbeaten? Non-determinism gives the power to explore exponentially many threads of computation simultaneously. If a deterministic turing machine tries to mimic the behaviour of a non-deterministic one, it has to explore all the paths one by one. It costs time to go through all the paths one by one. One has to add up all the time that has been spend. But does one really have to add up the space as well??? I felt really stupid when I come to know that the reason why power of deterministic and non-deterministic turing machine comes out to be same, is that space can be reused!!!!

As a wild thought, may be if a deterministic turing machine can go back in time to explore the alternate future, thus, reusing the time we may as well have P = NP :D.

Wednesday, July 04, 2007

A few gems in gujarati

I have realised that no medium, tool is good or bad in general. It depends on how you view it or how you use it. Orkut may be a nuisance to some but I could find a few gujarati gems from a community.
----------------------------
પ્યાલો લૈ જ્યાં હું પહોંચ્યો તરસ છીપાવા માટે,
કમનશીબ મારું કે મને જોઈ કીનારા જ સુકાઈ ગયા.

પતઝડ ની કશ્મ્કશ તો જીરવી ગયા અમે પરંતુ,
જીંદગી ના બાગ તો ભરવસંત માં જ ઉજડી ગયા.

તૂફાન માંથી કશ્તી બચાવી લાવનારા એવા ધણા,
છે જેમના વહાણ કીનારે આવી જ ડૂબી ગયા.

મોસમ ની મહેર હોય તો હેલી આવી ચઢે છે ઘરમાં,
અમારા જેવા તો કૈં કીન્તુ ભર વરસાદે પણ કોરા રહી ગયાં.

હજારો લાશો ને મ્ંઝીલ સુધી પહોંચાડી હતી 'મક્કુ' પરંતુ,
ખુદ અમારાં જનાજા ચાર કાંધા ના મહોતાજ રૈ ગયા.....

----ભાવેશ 'મક્કુ'
----------------------------------
દુઃખમાં રડી લેવાની પણ મઝા અનેરી હોય છે,
હારેલી જીંદગી જીવવાની પણ મઝા અનેરી હોય છે.

કીનારા પર વહાણ હંકારનારાઓ તમને શું ખબર,
તૂફાન માં કશ્તી ગુમાવવાની પણ મઝા અનેરી હોય છે.

તમામ ઉમર જેને પામવાની તડપ હોય પરંતુ,
તેને મેળવીને ગુમાવાની પણ મઝા અનેરી હોય છે.

બે હાથ વડે ઝીંદગી ઉલેચનારાઓ એટલું પણ જાણો કે,
છેલ્લા શ્વાસે હથેળી ખાલી જોવાની પણ મઝા અનેરી હોય છે.

એક વાટ પકડી ને ચાલનારાઓ મંઝીલ જરુર પામે છે,
કીન્તુ માર્ગ માં ભટકી જવાની પણ મઝા અનેરી હોય છે.

દુનીયા જીતનારા ઘણાં સીકંદરો ભૂલાઈ ગયાં 'મક્કુ',
એક-બે ના દીલ જીતી ચાલી જવાની પણ મઝા અનેરી હોય છે...................

--ભાવેશ 'મક્કુ'
--------------------------
પાંદડું કેવી રીતે પીળું થયું કોને ખબર ?
એટલે કે ઝાડમાંથી શું ગયું કોને ખબર ?

શહેર પર ખાંગી થઈ વરસી પડી આખી વસંત,
એક જણ નખશીખ ઉજ્જડ રહી ગયું કોને ખબર ?

શાહીમાંથી આમ કાં ઢોળાય છે તારાં સ્મ્રણ્ ?
એને મારું એક મન ઓછું પડ્યું ? કોને ખબર ?

સ્વપ્નમાં વહેતી'તી નહેરો તારા ચહેરાની સત્ત,
ને સવારે આંખમાંથી શું વહ્યું ? કોને ખબર ?

માછલીએ એકદા જળને પૂછ્યું ઃ તું કોણ છે ?
એનો ઉત્ર શોધવા જળ ક્યાં ગયું, કોને ખબર ?

મેં અરીસાને અમ્સ્તો ઉપલક જોયો, 'રમેશ',
કોણ એમાંથી મને જોતું રહ્યું, કોને ખબર ?

---રમેશ પારેખ
------------------------------------------

ચૂમી છે તને -

ગીતના ઘેઘૂર ગરમાળામાં ચૂમી છે તને,
બે ગઝલની વચ્ચેના ગાળામાં ચૂમી છે તને.

પર્વતો પાછળ સવારે, ને બપોરે ઝીલમાં,
સાંજ ટાણે પંખીના માળામાં ચૂમી છે તને.

સાચું કહું તો આ ગણિત અમથું નથી પાકું,
બે ને બે હોઠોના સરવાળામાં ચૂમી છે તને.

કાળી રાતોમાં છુપાઈને ગઝલની આડમાં,
પાંચ દસ પંક્તિના અજવાળામાં ચૂમી છે તને.

લોકોએ જેમાં ન પગ મુકવાની ચેતવણી દીધી,
પગ મૂકીને એ જ કુંડાળામાં ચૂમી છે તને.

પાંપણો મીંચાય ને ઉઘડે એ પલકારો થતાં,
વાર બહુ લાગી તો વચગાળામાં ચૂમી છે તને.

-મુકુલ ચોકસી
---------------
નદીની રેતમાં રમ્તું નગર મળે ન મળે,
ફરી અ દશ્ય સ્મ્રુતી પટ ઉપર મળે ન મળે,
ભરી લો સ્વાસમાં એની સુગંધનો દરીયો,
પછી આ માટીની ભીની અસર મળે ન મળે,
પરીચીતોને ધરાઈને જોઈ લેવા દો,
આ હસતા ચહેરા; આ મીઠી નજર મળે ન મળે,
ભરીલો આંખમાં રસ્તાઓ, બારીઓ, ભીંતો,
પછી આ શહેર, આ ગલીઓ, આ ઘર મળે ન મળે,
વતનની ધૂળથી માથું ભરી લઉં આજ અહીં,
અરે આ ધૂળ પછી ઉમ્રભર મળે ન મળે,
વળાવા આવ્યા છે એ ચ્હેરા ફરશે આંખમાં,
ભલે સફરમાં કોઇ હમસફર મળે ન મળે,


રડી લો આજ સંબંધોને વીંટળાઈ અહીં,
પછી કોઇને કોઇની કબર મળે ન મળે,


--આદીલ મન્સૂરી
-----------------------
ઘણાં વરસો પછી આવ્યા છો એનો એ પુરાવો છે,
જે મહેંદી હાથ ને પગ પર હતી એ કેશ પર લાગી છે..............
-----------------------
માછલી સાથે જ દરીયો નીકળ્યો,
લ્યો ઋણાનુબંધ પાછો નીકળ્યો.

હુંજ મારા ભાર થી થાકી ગયો,
હું હતો એ 'હું' જ ખોટો નીકળ્યો.

ચાંદની સમજી અમે મુઠ્ઠી ભરી,
મૂઠ ખોલી ત્યાંજ તડકો નીકળ્યો.

સાંજ પડતાંયે ફર્યુ ના એટલે,
શોધવા પંખીને માળો નીકળ્યો.

આશરો કેવળ નદીને જ હતો,
એક સાગર એય ખારો નીકળ્યો.

આગીયાઓ ઉજળા છેકે પછી-,
વેશ બદલી સૂર્જ ઊડતો નીકળ્યો.

થોભવાનો થાક વસમો હોય છે,
માર્ગ સમજ્યો એ ઉતારો નીકળ્યો............................

----ધૂની માંડલીય
------------------------------
લીધો છે જન્મ પ્રેમ મેં કરવા બધાંની સાથ,
એમાં જરાક આપ વધારે ગમી ગયાં........
-------------------------------
આવ મારી જાત ઓઢાળુ તને...
સાહેબા, શી રીતે સંતાડુ તને...

ઘર સુધી તુ આવવાની જીદ ના કર...
ઘર નથી, નહીતર હું ના પાડુ તને?
-------------------------
મને એ જ સમજાતું નથી કે આવું શાને થાય છે.
ફૂલડાં ડૂબી જતાં ને પથ્થરો તરી જાય છે.

ટળવળે તરશર્યાં તારાં જે વાદળી વેરણ બને.
તે જ રણમાં ઘૂમ મુસળધાર વરસી જાય છે.

ઘર-હીણાં ઘૂમે હજારો ઠોકરાતાં ઠેર ઠેર
ને ગગન-ચુમ્બી મહાલો જનસૂનાં રહી જાય છે.

દેવડીએ દંડ પામે ચોર મૂઠી જારના:
લાખ ખાંડી લૂંટનારા મહેફિલે મંડાય છે.

કામધેનુને જડે ના એક સૂકું તણખલું
ને લીલાંછમ ખેતરો સૌ આખલા ચરી જાય છે.

છે ગરીબોના કુબામાં તેલ ટીપુંય દોહ્યલું ?
ને શ્રીમંતોની કબર પર ઘીના દીવા થાય છે.
--------------------------------------------
સમય જાતાં બધું સહેવા હૃદય ટેવાઇ જાયે છે
ગમે તેવું દુઃખી હો, પણ જીવન જીવાઇ જાયે છે.

હૃદયના દર્દની વાતો કદી છાની નથી રહેતી
હૃદય ગભરાય છે ત્યારે નયન ભીંજાઇ જાયે છે.

સમય બદલે તો બદલે, પણ પ્રણય રંગો નહીં બદલે
હૃદય રંગાઇ જાયે છે તો બસ રંગાઇ જાયે છે.

મુસીબતના દહાડા એ કસોટીના દહાડા છે.
છે પાણી કેટલું કોના મહીં જોવાઇ જાયે છે.

જીવન સારું જીગરની આહ થી ફૂંકી દઉં ‘ઘાયલ’
કદીક મારા ઉપર મને ય એવી ખાઇ જાયે છે.

- અમૃત ઘાયલ
-------------------------------------
સારું છેે એની સાથે કશી ગુફતગુ નથી,
નહીંતર હું કંઈક ભુલ કરત બોલચાલમાં.
કરતો હતો જે પહેલાં તે પર્સતાવના ગઈ,
લઈ લઉં છું એનું નામ હવે બોલ્ચાલમાં.
એ 'ના' કહીને સહેજમાં છુટી ગયા 'મરીઝ્',
કરવી ન જોઈતી'તી ઉતાવળ સવાલમાં...........
------------------------------------------
લેવા ગયો જો પ્રેમ તો વહેવાર પણ ગયો,
દર્શનની ઝંખના હતી, અણસાર પણ ગયો.

એની બહુ નજીક જવાની સજા છે એ,
મળતો હતો જે દૂરથી સહકાર પણ ગયો.

રહેતો હતો કદી કદી ઝુલ્ફોની છાંયમાં,
મારા નસીબમાંથી એ અંધકાર પણ ગયો.

સંગતમાં જેની સ્વર્ગનો આભાસ હો ખુદા,
દોઝખમાં કોઈ એવો ગુનેગાર પણ ગયો ?

એ ખુશનસીબ પ્રેમીને મારી સલામ હો,
જેનો સમયની સાથે હ્રદયભાર પણ ગયો ?

એ પણ છે સત્ય એની ઉપર હક નથી હવે,
એવુંય કંઈ નથી કે અધિકાર પણ ગયો.

સાકી છે સ્તબ્ધ જોઈ નશાની અગાઢ ઊંઘ,
પીનારા સાથે કામથી પાનાર પણ ગયો.

કેવી મજાની પ્રેમની દીવાનગી હશે !
કે જ્યાં ‘મરીઝ’ જેવો સમજદાર પણ ગયો.
------------------------------------------------
િલ મા કોઇની યાદ ના પગલાં રહી ગયા,
ઝાંકળ ઊડી ગયું અને ડાઘાં રહી ગયા.

એને મળ્યા છતાંય કોઇ વાત ના થઇ,
ગંગા સુધી ગયા અને પ્યાસા રહી ગયા.

ફૂલો લઇને બાગથી હું નીકળી ગયો,
ને પાનખરના હાથમાં કાંટા રહી ગયા.

વરસ્યા વિના જંતી રહી શિર પરથી વાદળી,
‘આદિલ’ નજર ઉઠાવીને જોતા રહી ગયા.
-----------------------------------------

Monday, June 25, 2007

Lion's Hunger

Here goes yet another puzzle, not as good as the one with the thieves.


Problem
------------

In a zoo far far away ( I am being a little dramatic, eh? :D ), there was a cage filled with n lions. One day the care taker of the zoo put in only one huge meat loaf in the cage. If any lion eats the meat, he will feel dizzy and will fall asleep. Now, that the lion has fallen asleep, he would serve as meat for other lions. Also, assume hypothetically that all lions are intelligent, so none of them would want to get killed.

If you are one of the lion and given an option to eat the meat, would you go for it??


Solution
-----------

Like many of the interesting problem in mathematics, this can be solved using the principle of mathematical induction.

If you are the only lion in the cage, you can go ahead and have your food.

If two lions are there, none of them would eat. why?? Because, if any one of them eat the meat then he is going to be killed by the other lion.

What if three lions are there? you know that if you eat the meat, you will fall asleep. Though you will be as good as meat for other two lions during your slumber, none of them would eat you for the reason stated above.

It is easy to generalize and see that you can have your meal if odd number of lions (including yourself ) are in the cage. For the case of even number of lions, it is better to stay hungry :p.

Wednesday, June 20, 2007

આવ મારા આંસુની ચમક આપું તને ..

Hi,
Found this nice poem in the "about me" section of rushi's Orkut profile.
------------------------------
આવ મારા આંસુની ચમક આપું તને ..
તું મને જોઇને બહુ ઝાંખી રીતે મલકાય છે .. ..
•.¸¸.•♥´¨`♥•.¸
મદમસ્ત એવી ચાલ ચાલ ના ,
કેટલાય મુસાફરોની મંઝીલ બની જઇશ ..
સંભાળીને રાખ તારા કાજળભર્યા નયન ,
બેફામ વરસ ના , કાતીલ બની જઇશ ..
આ રીતે ઝુલ્ફોને હાથોથી પસવાર ના ,
કેટલાયે શાયરોની ગઝલ બની જઇશ ..
આટલું ધ્યાન દઇને ગઝલ વાંચ ના ,
કોઇના પ્રેમમાં પાગલ બની જઇશ .. ..
█▓▒░
તું નથી આ સુરના શણગારમાં ..
તું નથી આ શબ્દના આકારમાં ..
ક્યા નજાકત તારી ને , ક્યા આ જગત ..
સાચવું તેથી જ તને ધબકારમાં .. ..
•.¸¸.•♥´¨`♥•.¸
ટોળે વળે છે કોઇની દીવાનગી ઉપર ..
દુનીયાના લોકો કેવા મીલનસાર હોય છે .. ..
█▓▒░
વાત મારી નીકળી તો હશે ..
સાંભળી પાંપણો ઢળી તો હશે ..
મૌન પાળ્યું હશે છતાં "ઘાયલ" ..
આહ આંખોમાં સળવળી તો હશે .. ..

Tuesday, June 19, 2007

Honour among thieves???

Hi All,
Seems I have been too frequent in posting on my blog now a days. Thanks to my friends Sanjeet, Pranjal, Ashok ... with whom I discuss interesting problems. Just like my previous post, this post is also regarding a technical interview question asked in some company. Anyways, coming directly to the point.

Problem
-----------
There are five thieves T1, T2, T3, T4 and T5. They robbed 100 gold bars from a bank. For dividing the gold bars they came up with following idea.

- Starting from T5 to T1, a thief T_i will come up with a scheme to divide the gold bars amongst the thieves.
- Voting will happen in favour or against this scheme. If Majority ( Strictly greater than 50 % ) votes in favour then the division will happen according to the scheme. If not, then T_i will be killed and it will be T_i-1's turn to come up with a scheme.

Please keep in mind that
1) All thieves are intelligent.
2) All are very greedy, so they would try to get as much wealth as possible.
3) They all would like to kill as many thieves as possible. Of course, this motive stands at a lower priority level as compared to their greed for the gold.

If you are T5, what scheme would you come up with? Obviously, your motive would be to survive but try to come up with a scheme where you will get away with as much gold as possible.
PS:- Smallest unit of division is a gold bar. A bar can not be further divided.

-----
Solution
----
The answer is that if you are T5, you can get away with as much as 97 gold bars and still survive!!! Puzzled!! Read further to discover how.

Let's try to situation one by one from thieves perspective.

If T1 is the only person left, he will take all the gold bars.

If T1 and T2 are the only persons alive, no matter what scheme T2 comes up with, he is going to be killed and T1 would take everything. Because T2 can not get the majority ( > 50% ). Obviously, T2 would do anything to keep T3 alive.

T3 knows that T2 is going to support him no matter what scheme he comes up with. T3 can take away all 100 gold bars as he will have the majority no matter what. ( T3+T2 = 66% votes ). Obviously, T3 would like T4 to get killed so that he can take everything.

T4 knows that T3 would want him to be killed. If T4 is killed, T1 and T2 would not get anything. So T4 would give one gold bar to T1 and T2 each. Now, T4 will get the majority ( T1 + T2 + T4 = 75%) and he can take as much as 98 gold bars.

You are T5. If you get killed, you know that T3 would not get anything. So to take T3 into confidence you will give him a gold bar. If you get killed, T1 and T2 each get a gold bar. As you want to optimize the amount that you can get away with, you would give one of T1 or T2 2-gold bars. You can get away with as much as 97 gold bars!!!

Monday, June 18, 2007

Young Tableau

Hi All,
The other day me, sanjeet, and pranjal were discussing a few questions ( or puzzles ) which are likely to be asked in technical interviews. One of the question that was asked to someone in google was about finding out a specific element in an n x n Young Tableau.

Let me first define, what a young tableau is. It is an m x n array with the following property.

for all j = 1 to n-1, A[p][i] <= A[p][i+1]
and for all , i = 1 to m-1 , A[i][q] <= A[i+1][q] It is easy to see that following statement holds for a young tableau.
  1. For any sub-matrix of a young tableau, the top-left element is the smallest element within that sub-matrix.
  2. For any sub-matrix of a young tableau, the bottom-right element is the largest element within that sub-matrix.
Now, the problem is to find out a given element within an n x n young tableau.

----
Method -1
----

Start with the top-right element of the tableau. Compare this element e with the element to be found x.
if e > x then
discard the column in which e appears. ( Because e is the first(smallest ) element of that column.
else
discard the row in which e appears.
end if.
Repeat this exercise until the element is found or the tableau is exhausted.

It is easy to see that time complexity of Method-1 is O(n). As at every step we will discard either row or column which will take at most 2n steps.

---------
Method - 2
---------
Do a binary search over the diagonal of the tableau. If we find the desired element x then we are done. If not, we will have two element u and v where u <> u is the bottom-right element and v is the top-left element. The elements that we will discard at each step would be at least half of the elements in the original matrix.
Here is why,


i^2 + (n-i)^2
function is minimum where i=n/2. With i=n/2 the value of the function is (n^2)/2.

Now, if we do the analysis with respect to number of elements.
T(n^2) = 2T((n^2)/4) + logn

or

T(m) = 2T(m/4) + 0.5 logm

Solution of this recurrence, turns out to be O(m^(0.5)) = O(n). So, there is no improvement over the complexity as compared to the first method. Besides, this second method fails when the sub-matrices that were discarded were not square. In which case, the remaining two sub-matrices will not be square either.
----
Method 3
------
Compare the central element
e with the desired element x.
if e > x then
discard the bottom-right quadrant of the tableau.
else
discard the top-left quadrant of the tableau.

Now , we are left with three sub-matrices of the size n/2 x n/2.

The recurrence would be

T(n) = 3T(n/2) + O(1).

Solving it would give us n^(log_2 3) = n^1.585. It turns out that even though in Method-1 you discard n elements and in this method you discard (n^2)/4, the complexity does not favour Method-3. Anyways, it was a good exercise to do this analysis.

Thursday, June 14, 2007

Necklace puzzle - yet another solution

Hi all,

I am posting here another solution to "Necklace Puzzle". The solution is by my friend Vaibhav Gupta

-------


Let A and B are the 2 necklaces with N gemstones. A and B has three types of
gemstones which are equal in number.

A = A[1] A[2] ... A[N]
B = B[1] B[2] ... B[N]

Where A[i] is the ith gemstone in Necklace A.
B[i] is the ith gemstone in Necklace B.

Let Color(A[i]) represents the type of the gemstone A[i].

We construct a bipartite graph G = (X,Y,E), with the following condition:

For each gemstone A[j] in A we create a node X_j in X. So |X| = N
Foe each gemstone B[j] in B we create a node Y_j in Y. So |Y| = N
E is the edges set from node in X to node in Y.

E = { (u,v) | u \in X and v \in Y and Color(u) = Color(v)}

|E| = (N^2) / 3 since each node has exactly N/3 edges.

We define weight to each edge in E:
Weight(e) = orientation of the string.
OR Mathematically
Weight((X_i,Y_j)) = i - j if i>=j
= N+i-j otherwise

0 <= Weight((X_i,Y_j)) <= N-1 since 1<=i<=N, 1<=j<=N So there are N possible values of weight.

Now we just need to prove that there are atleast N/3 edges of same weight.
This can be proved by pigon hole principle. There are (N^2) / 3 edges and
each edge has N possible values of weight so there must exist a set of
ceil(|E|/N) edges of same weight

|E| / N >= N/3

Hence proved.

For general case :

For 3 gemstone types
( a^2 + b^2 + c^2 ) / (a + b + c)

Where a is the number of gemstone of type 1.
b is the number of gemstone of type 2.
c is the number of gemstone of type 3.

For m gemstone types:
(N_1^2 + N_2^2 + N_3^2 ... + N_m^2) / (N_1+N_2+N_3 ..+N_m)

where N_i is the number of gemstone of type i.

---------

Wednesday, June 13, 2007

Quote by John Von Neumann

"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is"
-- John Von Neumann

I saw this quote as saket's status message in google talk.

Necklace Theorem - Solutions to puzzles

Hi All,
So I am back again after some gap. This post will describe the solutions to the two puzzle that I posed as part of my prequel post "Necklace Theorem". For the sake of clarity I am copying the puzzles again over here.

1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.
As shown in the figure on the left, let us consider a baseline B. The circle represent the point set we are interested in. Refer to the prequel of this post and convince yourself that it is possible to have a line in any given direction which divides the point set into two equal half. Hence, it is also possible to have two orthogonal lines both of which will divide the point set into two equal half. ( When I say, two equal half, I mean that division in two portion satisfying the constraint "less or equals n/2" ). As both p and q divides the point set into two equal half, the region which is captured on top-left and bottom-right will be equal ( call it x, or to be more precise "less or equal x" ). Similarly, tom-right and bottom-left would be equal ( call it y). Let us have a function f(x,y) = (x-y) = v. By rotating p and q , 90 degrees we will have function value exactly negative, as x and y would swap their places. From intermediate value theorem we can argue that there will be a configuration where x = y = n/4.

2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.

With respect to the baseline B, we can have two lines p and q, each dividing the point set into equal half and region trapped as shown in figure would be equal to n/6 on each side. ( n/6 is written outside the circle to make it readable ). Now, as shown in the prequel post, we can have a line r which will divide the two point sets ( each of size n/3 ) into two equal half. This line r need not be concurrent with p and q. Let the triangle trapped between these three lines is equal to A. As we rotate this configuration 180 degree the area will become -A. Again, from intermediate value theorem we can state that area will be 0 at some configuration making r concurrent to p and q. Thus, each segment will have size n/6.

Tuesday, May 29, 2007

Necklace Puzzle

Hi All,
So I am here back again with a new interesting puzzle ( courtesy Vaibhav Gupta ). I am copying his mail verbatim below followed by the solution that I have in mind.
---------- Puzzle ------
NECKLACE PUZZLE #2

There are two circular necklaces with same number of three types of gemstones,
but the gemstones may be strung in different order along the necklace.

Now the two necklaces are placed on one top of the other so that the
gems are aligned
one above the other. Count the number of locations where the pair of
gems (one from
the lower necklace, one from the upper) is of the same type.
Since one necklace can be rotated relatively to the other, there are
many orientations
in which the count of matching gems can be taken.

Prove that there is at least one orientation where the number of
matches is at least
a certain number v.

For the special case of equal numbers of each kind of gem, v = N/3,
where N = total number of gems in one necklace (and 3 kinds of gems).

1. prove this for the special case.
2. find, with proof, value of v in the general case (with m kinds of
gems not necessarily equal in number).

some clarifications:
1. the necklace is circular i.e. its a simple closed loop. so given
two necklaces RGB and RBG,
the second can be rotated wrt first to give three orientations (but
this small example
is unusual because the number of matches is same in all 3 orientations):

RGB
RBG 1 matches

RGB
GRB 1 matches

RGB
BGR 1 matches

so v = 1

2. "there is at least one orientation where the number of matches is
at least v"
label the orientations from 1 to N. denote the number of matches for
orientation i as m[i].
then " there exists an i such that m[i] >= v" is the more formal way
of saying this.


-Vaibhav.
------------------
Well, indeed an interesting puzzle. Intially for a few minutes I thought whether it can be proved by contradiction or not. I tried to see whether I am able to hit a contradiction by imagining that "v is always less than N/3". Within a few minutes I realized that this is not going to work. As I remembered the lessons from Prof Sundar Vishvanathan , I thought of trying to prove it by induction. Prof Sundar always used to say that most of the proofs can be given by the principle of mathematical induction. This time I did not bank too much on this options as I learnt it from my earlier experience as I mentioned in my previous post. The solution of this proof also along the line which was taught to me by Prof Sundar.

The proof here makes use of the fact that if expected value of some random variable is a then there exist a possibility where the random variables has a values at least a.

Let us assume that first necklace is fixed and the second necklace is rotated with respect to the first one. Let us define a random variable X such that
X_i = 1 ( if ith gem of first necklace matches with the second one )
X_i = 0 Otherwise.

The ordering in the second necklace can be anything so assuming a uniform distribution there.
Calculating the expected value,
E(X_i) = Pr(X_i).X_i = (Number of gems having the same colour as ith gem/Total number of gems)
For 3 different kind of gems
E(X) = Sum(i=1 to N) ( E(X_i) ) = R^2/N + B^2 /N + G^2/N.

For the special case where R = B = G = N/3 we will have
E(X) = N/3. As the expected value is N/3 we can say that there is at least one configuration of second necklace which would make the number of matching gems at least N/3.

When there are m kinds of gems, not necessarily equal in number, let C[i] denote the number of gems of the same kind as i, where i varies from 1 to m.
Therefore, for general case the expected value is
E(X) = Sum (i = 1 to n ) ( C[i]^2/N )

Well, a nice puzzle indeed. As a closing remark, I have the solutions to the puzzle that I mentioned in my previous post. It will require some figures to be embedded to explain the solution in a lucid way. I will post it soon as I get the time.

Friday, May 11, 2007

Necklace Theorem

Hi all,
As mentioned in my last post, after lunch talks can be very fruitful at times. Describing a yet another fruitful chat with my friend Sambuddha Roy.

The other day he gave me an interesting problem to think about, which is formerly known as, as he told me, necklace theorem. Two thieves have stolen queen's very precious necklace. There are three kinds of gems in the necklace called R, G and B. All are even. The problem is to divide the necklace in such a way that both the thieves get equal amount of gems of each kind. The necklace can have any interleaving of the gems. ( e.g. RRGBGGRBBBG..... ) Prove that it is always sufficient to divide the necklace in equal share by at most 3 cuts.

The proof makes use of Ham Sandwich Theorem. For brevity, I will quote it as HST now on. HST for 2-dimension says that given any two point sets in a plane, there always exist a line which will cut both these point sets simultaneously into half. To say it more formally, call the point sets R and B. Then one side of line will contain at most |R|/2 points and at most |B|/2 points. The same constraints will be followed on the other side too.

If there is only 1 point set R. For a given direction we can always have a line which will divide R in two. The proof is based on intermediate value theorem. It says that for a continuous function if f(x1) = 0 and f(x2)=1 then there exist a z \in (x1,x2) such that f(z) = 1/2.

Now that we have two point sets. What we can do is we get a line for point set R. Now we evaluate how this line L behaves with respect to B. Let us define diff(L) = number of blue gems on the left of L - number of blue gems on the right of L. For initial line L, let the value of diff(L) be b. What we can do is rotate this line a bit. We know that for any given direction, we have a corresponding line L which will divide R equally. We will again evaluate wrt B. We keep on doing this until we have rotated the line for 180 degree. At this point value of diff(L) would be -b. From intermediate value theorem, we can state that there will be a line where diff(L) will be 0.

How about, Ham Sandwich theorem in 3-dimension?? Well, my friend has given me the proof as an exercise. The statement is that given 3 point sets R, G, B in R^3 ( or 3-dim space ) there always exist a plane which will divide all 3 point sets simultaneously into equal portion.

Now, we need to reduce Necklace Theorem to HST in 3D. Starting from left to right, assign every gem an index i. Plot a parametric curve ( t, t^2, t^3 ) using these indices. HST assures us that we will have a plane ax+by+cz+d=0 which will divide R, G, B equally. This plane will divide the parametric curve at , at most 3 points as at + bt^2 + ct^3 + d = 0 will have at most 3 roots. Now, it is easy to map these 3 intersection points on the curve to 3 cuts on the necklace.

Phew!!! It never occurred to me that this proof will use such weird things. Induction based method was too tempting for me to let me think in some different direction. But the story is not over yet. The proof given above is not constructive. So if we were to find an algorithm to find these 3 cuts we might have to explore all possibilities taking O(n^3) time. So another exercise would be to try to find more efficient algorithm to find these cuts.

The generalization of HST is that given k point sets in R^k there would be always be a hyperplane which would cut all these k point sets simultaneously into equal portion. Yet another generalization one can think of is that, what if there are more thieves??? Given q number of thieves and k kind of gems, what would be the upper bound on the number of cuts required?? The answer is due to dold's theorem ( Neither sambuddha nor I have read the proof ). It say that for such situation at most k(q-1) cuts would be necessary.

What if there are 3-point sets in two dimension?? Definitely a line would not suffice. An exercise would be to prove that two rays originating from an apex would be sufficient. Give an algorithm for finding them out.

Two more puzzles are :
1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.

2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.

That's enough to tease our brain for a while :D.

Wednesday, May 02, 2007

After lunch talks

Hi,
It's been a long pause on my blog. I would say nothing significant to write. Even in this post not much significant but few small interesting pieces of interesting discussion.

Sometimes we go to IRL foyer after lunch and have some discussion. At times, those discussions are fruitful too. By fruitful, I mean it adds something in your knowledge. For example, today I was chatting with my friend Sambuddha . He is a very good narrator, I must admit. He was talking about his BTech advisor Manindra Agrawal who has been awarded with a Godel Prize.

He narrated an incident when Prof Manindra was out to present his work on a conference. There were a few Fields medalist , who were unable to grasp the idea of a young talent like Prof Manindra taking away the Godel prize on the same problem that they once tried to tackle. As Prof Manindra was presenting his talks, these fellows tried to interrupt him in order to embarrass him every now and then. At one point, a question was posed on such a trivial thing that Prof Manindra could not resist but say "I don't know about the undergraduates in US, but I can assure you that any undergraduate student in India would be able to understand this". Needless to say, no further interruptions occurred during his presentation :-).

There were also a few things that I came to know like a complexity class ( NP^NP ) as well as
game of Hex, Secretary Problem and things like that.

Sometimes, chatting can be more brain stimulating than the work :-)

Thursday, March 08, 2007

Sudoku Solver

It is very unlikely for me to post twice in a day, yet I am back again. I had a little idle time at my disposal so I thought to put it to some use.

A couple of months back I read in Times of India about world Sudoku championship which was to happen in March 2007. In addition to the day to day sudoku puzzles they included certain variation of the puzzle too, to encourage readers to take part as well as to stimulate their brain :D.

Sudoku took over my mind during those days and I was completely engrossed in reading about Sudoku as well as solving them at websudoku . It occurred to me why not write a program to solving the puzzle? So I took up the task and was ready with a small Sudoku Solver .

Of course, for certain inputs it does not give the solution. I pondered over the completeness and soundness issues of the initial sudoku board. I don't know whether it is appropriate to use these terms which are often used and associated with algorithms. Let me define it this way. Completeness means that the initial information given in the board should be sufficient to solve the puzzle by using only inferences ( No guessing game/No coin tossing/ No breaking tie). In other words, there must exist at most one solution that can be derived from the initial configuration of the board. Soundness means that the information should not be conflicting, or say, at least one solution exist that can be derived from the initial information. I discussed the matter with my mathematics teacher Mr Motilal Panigrahi at GCET .

We could not arrive at any definitive proofs or conditions to ensure the soundness and completeness, but it was nice to chat with him over these things years after I left the college.

Sherlock Holmes

Lately, I have been reading famous "Sherlock Holmes" stories. What a nice piece of literature it is! Sir Arthur Conan Doyle is truly a master of creating writings that hold the reader till the end. It really takes a true genius to create such a timeless character like Sherlock Holmes.

Though, some of the inferences employed by Sherlock Holmes in unleashing the truth seems to be unrealistic, I especially admire the literature for the flair with which the author wrote it. The description of a scene creates enough impact on your mind to force it to weave a virtual world around as if you are witnessing the entire series of events. Author has put to use his vocabulary so perfectly that it does not drive away a reader with average vocabulary and yet maintaining enough variations to make it far from banal. I wish I could attain at least 1/20th of author's writing skill.

Now I know, why Sir Arthur Conan Doyle was awarded knighthood. :-)

Monday, February 12, 2007

Bitwise fiasco

Yesterday was one of the worst day. It was the day of Bitwise 2007 . I participated in this contest with Pranjal as my team mate. I had really high hopes and a bit of arrogance as I could claim 26th rank in this prestigious contest last time amongst 2700 participating teams. Bitwise 2006 was my first official participation in a programming contest. Having done so well in my debut, I was dreaming to climb further up the ladder with Pranjal ( who secured 8th rank in Bitwise 2006 ) along the side.

The arrogance had fogged the part of the brain which does rational thinking, and I ended up starting my day without any kind of warm up practice for the contest. I had not even revised any relevant material.

Bitwise 2k7 started a little late than the announced time of 1300hrs. And as usual, I thought to attempt the "easier" problems ( 100 points ) first. It was based on graph theory where one was required to find out the vertice(s) having the minimum distance to all other vertices in a given tree. Initially, I started with an O(n^3) implementation and when I found the response of the system to be "Time Limit Exceeded" ( which was kind of obvious with such a naive approach to the problem ), I improved it to O(n^2). Even though, I tried harder I could neither change the complexity nor the response of the system. After 2-3 failed attempts I decided to concentrate on some other problem and come back to this one at a later time.

Problem 4, had two parts, the initial part was to decide whether a certain door k out of n will be open or closed having gone through a certain toggling scheme. It was kind of easy. The next part was a variation of the classical Tower of Hanoi problem. No matter how hard I tried, my algorithm was not matching the given sample input/output. I asked the admins to look at the problem again for any possible mistake in the statement or sample input/output. But this time they were not as quick in response as they were for the last event. After around 10-15 questions fired by different teams, they answered only one. The overall contest also had attained height of mismanagement with problem statements being updated several times after the contest timer was started. Having tried for 2-3 hours on Problem 4, to my utter surprise, I found out that many other teams were cribbing about the correctness of its problem statement. I checked the rankings and was shocked to see that none of the teams ( not even those who were sitting at Top 10 ) could solve that problem. So I gave up on this problem too.

Then, I started yet another problem having to do with dynamic programming, coins and denominations. It was a variation of the classic denomination problem. Not that it was too hard to do it, I was kind of getting low because of failures and hunger. We went out to have a dinner at a small restaurant just opposite to IIT where we discussed yet another problem involving prime number and modular arithmetic. I thought to give it a shot after coming back, but that damn "Time Limit Exceeded" was not getting out of my sight.

Finally, we decided to give up as we were still sitting at zero where other Top 50 teams begged more than 800 points. I had never been so dejected in a long time. I was literally ashamed of myself.

Today morning I read a couple of articles on Modular Arithmetic and
Fermat's little theorem and realized why my implementation was not fast enough to defeat that "Time Limit Exceeded" demon. For Problem 1 ( The one with the vertices ) I learned that the middle vertice(s) of the longest path in the tree always have minimum sum of distance to all other vertices. How to find the longest path in a tree? Well, start from any vertex A and find out the furthest vertex B from it. Now start with B and find out the furthest vertex C from B. Path B to C is the longest path and its middle vertice(s) are the ones that we needed to find out. Running time?? O(n)

The bottom line is that I have got rusty. My programming skills and algorithm designing skills have fallen down. It seems I have not been doing much brain stimulating work for a long time. May be this failure is an indication for me to start honing my skills and in addition to giving exercise to my body I should give enough exercise to my brain as well.

Thursday, February 01, 2007

Parzania : A distorted reflection of Gujarat Riots

So I am back to the blogs after a long break. Life is going on as routine and events happening not worth mentioning. But something happened that forced me to write today, something that evoked memories of gujarat riots. Yes, I am referring to movie "Parzania".

Last sunday evening me and pranjal went to see a movie at PVR Saket. Though the movie has been praised by critics, I did not like it much. It seems to be a fashion to make movies on "sensitive" issues and show that you ( producer / director and the whole league ) are "concerned" about those who suffered those horrific series of events.

The thing I did not like most about the movie is that they depicted the police force as an evil spectator and accomplice. I am not saying that police was acting like an angel during the events and may be some incidents might have happened which caused the notoriety the police has gained. Bollywood keeps on depicting our police force as a demon and then we all yell that police does not perform its duties very well. If someone who has done good deeds is always been criticized for his/her wrongdoing, will there be any motivation to keep on doing good? Isn't it the case that lack of appreciation cultivates a tendency not to take pain in doing something right ( because no body would care/mention/appreciate )?

I had been there in gujarat. I am born and brought up in gujarat itself. And I must say that the biggest villain was media. Stating baseless rumors as facts, presenting events in a sensitized form, showing provoking clips/statements this is all media has done. Should not they act responsibly? But who is to blame, after all, we like things presented in this manner. We always try to hide our irresponsible behavior by criticizing someone.

So called "Top class" reporter barkha dutt was standing on a lonely highway and screaming there is no security force there? What should I say about that asinine woman? Gujarat has thousands of kilometers of highway, what did she want? A policeman at every 50 meter on the highway and leave the burning cities unattended?

Army batallions were air lifted from Jodhpur to get them as fast to gujarat as possible. Those army men did not took a rest. But did we appreciate? My friends were stuck in vidyanagar because of curfew. No mess, no shops and no food. It was the police who came to the rescue, searching for such caged souls and escorting them to Anand railway station. They did not ask whether the students that they are helping is hindu or muslim, the just performed their duties. Alas! it all goes unnoticed. When the mob came to our place and burned shops at the ground floor, police did came. What do you think a group of four people, three carrying a lathi each and one carrying a vintage pistol could have done against a mob of 3000 people? I have seen police officers begging the mob to keep cool. And the way they depict in the movie is that police watched the entire scene taking satanic pleasure in whatever was happening.

Is it police' fault that we do not have enough policemen? Is it police' fault that it is not well equipped and poorly paid? At the time of riots, they were staying in tents in a sensitive areas so that people could feel safe, but no body cared asking them even for a glass of drinking water.

Well, may be I had a lot to write but my anger towards the movie was subdued because of the delay in this writing. And even from a movie point of view, having english as a language while you are filming on a lower class background???

Besides, I still don't understand what was the point of making this movie after years of those horrific past. Did they want to revive the wounds of victims? It is such kind of distorted and exaggerated representation which had damaged gujarat's reputation irrevocably. Gujarat was pushed to a sixth place in industrial investment, because they say gujarat is an "unsafe" place.

For me, gujarat is much much safer than any other place in india where girls can stroll at almost midnight without worries. May the peace prevail!!!

Friday, January 12, 2007

Esterel : Syntax and Indent files for Vim

The other day I was programming in Esterel with my favourite editor Vim. And it turned out that I did not have syntax and indent files which would make my life easier while using Esterel.

I could find syntax file for esterel from somewhere, and I modified, indent file for shell scripts to suit for esterel.

You must add following 3 lines to your .vimrc file :
au BufRead,BufNewFile *.strl set filetype=esterel
au! Syntax ESTEREL source /usr/share/vim/vim63/syntax/esterel.vim
:filetype indent on


Change the source where you had put the syntax file for esterel.
Ideally it should go to $VIMRUNTIME/syntax and $VIMRUNTIME/indent respectively.

Anyways, here are the links for the syntax and indent file for esterel.