P != NP !

Vinay Deolalikar, an extremely common & dull Indian name as such.
But that is what I would have said a few hours back on this name. What do I say now ? Well - this might well be the name of the most famous computer scientist of all times. Yes you read it right - of all times.

Why ? A guy with this name who works as a researcher  at HP labs, Palo Alto,  has claimed that he has a proof to establish that P!=NP.  What it means is that if this is true, not only he takes home 1 million $, THE most difficult & important problem of computer science would be solved .

His paper is awful 103 pages long & a preliminary version can be found here.This only brings one name to my mind- Andrew Wiles ! If you don't know why- well you don't deserve to be reading this blog !

You know what is startling ? This guy was not even a computer scientist. He was an electric engineering major from IITB only. Even his PhD was in electrical engineering. Though on his homepage, he describes himself as a mathematician.
It would be a long stick in the ass of all computer scientists of this world if an inter-disciplinary researcher solves the hardest nut.

Plus its cool that he was born & brought up in Delhi & he passed out of a university which is the nearest kin to mine.(IIT Delhi).
I am so excited.

Y0 baby. C0de monkey is jumping restlessly. :)

Raining Parabolas

Source: Spoj.pl
See the problem statement here

Problem: (In abstract) You have n length strip. You at any time choose a segment of strip [x0,x1] & apply paint on it such that paint applied on ith square is a*i^2 +b*i + c for constant a, b, c given with every paint trial.
Given any segment [x0,x1] we are to find the sum of paint amounts applied to this segment .

Constraints: We need an algorithm where both query for a given segment & updating a paint attemp take atmost O(logn) time.

Hunch: My first hunch is to go for segment trees ofcourse. What is problematic here is that sum amount to be applied is not uniform across all squares. I can think of only storing with each segment its total sum. So that query becomes O(logn) only. I dont know how to update yet.

Tool Tips

Suddenly I feel so ahead of the groove- always current.
Like few days back I was working on new model of search & the next day I see exact same in (snapshots) of a web newssift.com ( dead now).  The other day I was seeing auto suggestion navigation lists & after I told Ayan what do I want it to look like- he shows me a recent page on something called Elastic List. I last week was thinking of auto suggest & now I see exact same functionality in facebook (ofcourse done before me thinking about it- but atleast I am starting to see & predict things my own.)

So what now ?
Tonight Only I saw a new feature in FB- you hover over some link & it loads you a tip box - sometimes a snapshot of the page too but essentially an html div . & I had spent all my day in finding the best way of doing a tool tip.


Here is a simplistic javascript tooltip creating code:


To actually create a tool tip , just bind this simple function to events like onhover or onclick & pass them proper arguements. You may also like to take measures to remove the div by using onmouseout or some other events.

Ofcourse this is too simple but possibilities are endless. Happy tool tipping. :)

jQuery

Fourth day of coding in java script & I have already written one fairly advanced app. Also today I started learning jQuery too. For javascript n00bs let me clarify- jQuery is the awsmest js library of this world written by another God John Resig.
jQuery  program I wrote today was - dynamic tab adder & remover in  arbitrary js container. I currently dont have functionality to support downloads through blogger but I hope to add it soon enough so I ll put for download all my work.

I have never found anything so exciting to codeup as whole javascript paradigm. I found my first ever dynamic scoped lanuage in js. What that means is :

If I have some variables in a program & user at run time enters a string say "totalSalary" , I can show him the contents of the variable "totalSalary". If you think this is trivial to do in your favorite static language- think again !

//TODO: 1) Creation of own home page in full javascript.
//TODO: 2) An auto suggest box

Dominoes

Source: Spoj.pl

Problem: We have n sticks standing at some points on number line. Location & height of each are given . A single knock( to left or right) of some stick with knock all sticks which it touches. That is if a stick of height h at location h is knocked right , it will knock all sticks at x+1 , x+2....x+h.

Given all sticks' information , Find the minimum number of knocks required to knock all the sticks. We can only spend O(nlogn) time at max.


Link to exact problem page here.

Adding Fractions

Source: CodeChef April Challange. See here

Problem: You have an array A of length n with each entry stroing a fraction a/b.
Define B[i] as length of sequence starting at i such that sum of fractions of this sequnce is largest amongst all sequnces beginning at i. Sum of a/b & c/d is defined to be (a+b)/(c+d).
Compute Array B given A.

LCM Sum

Source : CodeChef

Problem: Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

Update:  Solution given by a friend Tarundeep posted  in comments.