Estimating Distance-Find maximum distance between any pair of points in a plane

A set of n points are on a plane. Let d denote the maximum distance between any pair of points. Design a linear time algorithm to guess the value of d. Your guess is good if it lies between 0.7d and d. also proove correctness of algorithm.

Beaded Necklace-Find a sequence of such operations with minimum total cost for a given initial distribution of beads.

You are given a circular necklace containing n beads. Each bead maybe black or white. You have to rearrange the beads so that beads of the same color occur consecutively.

The only operation allowed is to cut the necklace at any point, remove some number of beads from both ends and put them back in any order, and join the cut ends. The cost of this operation is the number of beads removed. Any number of such operations can be used. You have to find a sequence of such operations with minimum total cost for a given initial distribution of beads.

For example, if the initial string is wbwbwb, this can be done by a single operation of cost 4, or two operations of cost 2 as shown.

Describe a polynomial-time algorithm for this problem; with short proof of correctness. You get points only if you match (or better) the judge solution's time complexity.

Save Me Please, Doctor!

Mr. Bean drinks from a water bottle that he carried for a long time without re lling, and
the stale water has resulted in him su ering from mild dysentery. He goes to a nearby nursing
home and gets diagnosed with Amoebiasis. The doctor identi es the pathogen to be a partic-ular kind of amoeba that has two variants, namely Asperdabrum (a) and Bostonostrum (b).
Each amoeba reproduces every hour by splitting into two, a !ab, and b !ba, and they stick
together in a chain in that particular sequence. At every step of reproduction, all the present
amoeba undergo binary ssion. For e.g. starting with type a, after 1st step the chain is ab,
after 2nd step the chain is abba, after the 3rd step the chain is abbabaab and so on. Mr.Bean
was infected n hours ago by a single amoeba and the doctor needs to know the type of the kth amoeba in the chain present now to be able zo nd a cure. Help the doctor cure him.

Input Format:
First line contains the number of test cases T. For each test case, there will be a single line of
input that starts with a character denoting the type of amoeba, , that infected him initially (a
or b) followed by two integers, n - the number of hours that have passed since he was infected,
and k - the position at which the doctor needs to know the type of amoeba.
Limits: 1<= T<=1000000, 1<= N<=4100, 1<=K<=2^N
.
Moreover, for the rst test le you can assume N, K lie within integer range (32 bits).

Output Format:
For each test case, output on a separate line the type of the kth amoeba in the current chain.

Sample Input:
2
a 3 3
b 4 6
Sample Output:
b
b

Source BITWise IITKGP,

Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “n” number of cells between two placed locations of number “n”

Write a program to display numbers placed in this way.

Example:-

(1) One of the possible placement for 7 numbers in 14 positions is :

5 7 2 3 6 2 5 3 4 7 1 6 1 4

write an algorithm that outputs each point along with the three other points that are closest to it.

You are given a list of points in the plane, write a program that
outputs each point along with the three other points that are closest
to it. These three points ordered by distance.
The order is less then O(n^2) .

For example, given a set of points where each line is of the form: ID
x-coordinate y-coordinate


1  0.0      0.0
2  10.1     -10.1
3  -12.2    12.2
4  38.3     38.3
5  79.99    179.99



Your program should output:


1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1

Determine whether a number is colorful or not. 263 is a colorful number because (2,6,3,2x6,6x3,2x3x6) are all different whereas 236 is not because (2,3,6,2x3,3x6,2x3x6) have 6 twice. So take all consecutive subsets of digits, take their product and ensure all the products are different

first point from where a truck will be able to complete the circle.

Given a circle. You have five points on that circle. Each
point corresponds to a petrol pump. You are given two sets of data.

1. The amount of petrol that petrol pump will give.
2. Distance from that petrol pump tp the next petrol pump.

(Assume for 1 lit Petrol the truck will go 1 km)

Now calculate the first point from where a truck will be able to
complete the circle.
(The truck will stop at each petrol pump and it has infinite
capacity).
Give o(n) solution. You may use o(n) extra space.

The Social Network (2010) - FaceMash Algorithm

I saw Social Network 2-3 times in 1 week. Not for entertainment. Not because I had nothing better to do. But because I wanted to understand the math and computer science fundae used in the movie. I would like to discuss one particularly interesting scene from the movie.

You may remember Mark inviting his friend Eduardo to give him his chess algorithm at the beginning of the movie (Mark was drinking, blogging and hacking simultaneously and creating Facemash.com). You may also remember the scribbles on the window:

and

What is this? This is actually the math behind Elo Rating System. Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor.

As explained in the movie, Facemash was quite simple. Not unlike hotornot.com, students went to a page and 2 random images of girls were picked and presented to them. The students then had to click on the hottest girl presented to them and then another set of two girls would be presented asking the students to repeat the same actions they had done. The difference with hotornot was that the girls presented were all Harvard students. In other words, the students were rating girls of Harvard based on their looks (You can imagine why Mark got into trouble).

The algorithm used - The Elo Rating system - insured a fair rating and ranking of the girls. A hot girl A winning over hot girl B girl would gain more points than winning (or being picked) against ugly girl C. Same goes for the following: ugly girl C wins over ugly girl D. ugly girl C gains some points in her general ranking. If ugly girl C wins over hot girl A then ugly girl C gains more points because the ranking of hot girl A is much higher than ugly girl D. The previous scenario is roughly what the algorithm implemented by Mark was doing. It was somewhat insuring a level of fairness despite the misogynistic nature of the product.

In today’s society, the Elo Rating system is used by many rating and ranking system to predict the outcome of matches but also insure a level of fairness between teams of different levels playing against each others. FIFA uses it to rank football teams.

You can read more about the system on wikipedia page(http://en.wikipedia.org/wiki/Elo_rating_system).

Why Programmer Works @ Night ..A Programmer Must Read :)

I found this quite Interesting, so posting this article, have a good read and happy coding.

A popular saying goes that Programmers are machines that turn caffeine into code.

And sure enough, ask a random programmer when they do their best work and there’s a high chance they will admit to a lot of late nights. Some earlier, some later. A popular trend is to get up at 4am and get some work done before the day’s craziness begins. Others like going to bed at 4am.

At the gist of all this is avoiding distractions. But you could just lock the door, what’s so special about the night?

I think it boils down to three things: the maker’s schedule, the sleepy brain and bright computer screens.

The maker’s schedule

Paul Graham wrote about the maker’s schedule in 2009 – basically that there are two types of schedules in this world (primarily?). The traditional manager’s schedule where your day is cut up into hours and a ten minute distraction costs you, at most, an hour’s worth of time.

Image via Wikipedia

On the other hand you have something PG calls the maker’s schedule – a schedule for those of us who produce stuff. Working on large abstract systems involves fitting the whole thing into your mind – somebody once likened this to constructing a house out of expensive crystal glassand as soon as someone distracts you, it all comes barreling down and shatters into a thousand pieces.

This is why programmers are so annoyed when you distract them.

Because of this huge mental investment, we simply can’t start working until we can expect a couple of hours without being distracted. It’s just not worth constructing the whole model in your head and then having it torn down half an hour later.

In fact, talking to a lot of founders you’ll find out they feel like they simply can’t get any work done during the day. The constant barrage of interruptions, important stuff ™ to tend to and emails to answer simply don’t allow it. So they get most of their “work work” done during the night when everyone else is sleeping.

The sleepy brain

But even programmers should be sleeping at night. We are not some race of super humans. Even programmers feel more alert during the day.

Ballmer's peak

Why then do we perform our most mentally complex work work when the brain wants to sleep and we do simpler tasks when our brain is at its sharpest and brightest?

Because being tired makes us better coders.

Similar to the ballmer peak, being tired can make us focus better simply because when your brain is tired it has to focus! There isn’t enough left-over brainpower to afford losing concentration.

I seem to get the least work done right after drinking too much tea or having a poorly timed energy drink. Makes me hyperactive and one second I’m checking twitter, the next I’m looking at hacker news and I just seem to be buzzing all over the place..

You’d think I’d work better – so much energy, so much infinite overclocked brainpower. But instead I keep tripping over myself because I can’t focus for more than two seconds at a time.

Conversely, when I’m slightly tired, I just plomp my arse down and code. With a slightly tired brain I can code for hours and hours without even thinking about checking twitter or facebook. It’s like the internet stops existing.

I feel like this holds true for most programmers out there. We have too much brainpower for ~80% of the tasks we work on – face it, writing that one juicy algorithm, requires ten times as much code to produce an environment in which it can run. Even if you’re doing the most advanced machine learning (or something) imaginable, a lot of the work is simply cleaning up the data and presenting results in a lovely manner.

And when your brain isn’t working at full capacity it looks for something to do. Being tired makes you dumb enough that the task at hand is enough.

Bright computer screens

This one is pretty simple. Keep staring at a bright source of light in the evening and your sleep cyclegets delayed. You forget to be tired until 3am. Then you wake up at 11am and when the evening rolls around you simply aren’t tired because hey, you’ve only been up since 11am!

Image via Wikipedia

Given enough iterations this can essentially drag you into a different timezone. What’s more interesting is that it doesn’t seem to keep rolling, once you get into that equilibrium of going to bed between 3am and 4am you tend to stay there.

Or maybe that’s just the alarm clocks doing their thing because society tells us we’re dirty dirty slobs if we have breakfast at 2pm.

Fin

To conclude, programmers work at night because it doesn’t impose a time limit on when you have to stop working, which gives you a more relaxed approach, your brain doesn’t keep looking for distractions and a bright screen keeps you awake.

Source : http://swizec.com/blog/why-programmers-work-at-night/swizec/3198

Problem: You are given a two dimensional bit array(elements are 0 or 1). Find number of islands in this array. One island is defined as all elemnts which are 1, including neighbours(with or without diagonals). Or Array Islands problem.