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.
Tuesday, July 6, 2010
Thursday, July 1, 2010
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. :)
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. :)
Subscribe to:
Posts (Atom)