Tuesday, January 17, 2012
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.
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.
Monday, January 16, 2012
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.
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.
Sunday, January 15, 2012
Tuesday, January 3, 2012
Friday, December 16, 2011
A grid of size N rows and M columns is filled with numbers, one in
each cell. You start at the centre of the cell at the top-left corner
(1,1) and your destination is the centre of the cell at the bottom-right
corner(N,M). In each step, you are only allowed to move to the centre
of the cell to the right or to the centre of the cell to the bottom.
There are many paths you can take to reach your destination from your
start – however, every path can be uniquely broken down into a series of
straight line-segments joined at right-angles. Each straight
line-segment in your path is termed a ‘leg’ of your path.
Your task is to choose a subset of the cells along your path in such a way that the sum of the numbers in the chosen cells is maximized. Your choice of cells must be such that exactly one chosen cell is present on each leg of the path. Note that cells at the intersection of two legs belong to both legs. What is the maximum possible sum you can form?
Input Format:
The first line contains one integer T, the number of testcases. The first line of each test case contains two space-separated integers N and M. Each of the next N lines contains M space separated integers, denoting cell values. The jth integer in the ith line denotes the value of the cell (i, j).
Constraints:
1 <= T <= 10
1 <= N, M <= 100
Numbers in each cell will be between -10000 and 10000 inclusive.
Output Format:
For each testcase output a single line containing the maximum sum you can form.
Sample Input:
3
2 2
-1 -2
5 -1
3 4
-1 2 -3 -4
-2 -3 5 -2
-1 -1 -2 3
2 2
3 1
5 3
Sample Output:
5
10
6
Explanation:
In the first test case, you can first move down and then move right. Your path now has 2 legs and you can choose only the cell containing 5. This is valid as it satisfies the condition that you must choose exactly one cell in each leg (because 5 is a part of both legs).
In the second test case, one best path is to walk right, choose 2, go right again and then down to choose 5, go further down and then right to pick up the final 3 (There are also other ways to pick-up the same numbers).
In the third test case, the best path is either (down, right) or (right, down). Note that since you can pick-up only one number in each leg you cannot select the ’5′ in the lower left corner (If you decide to pick-up 5, then you cannot pick up any other number because ’5′ is shared by both legs. We can do better by selecting both 3s).
Time limit: 2 seconds
Memory: 64 MB
ACM International Collegiate Programming Contest, 2010, Asia-Amritapuri Site
Solution ( Source : Team Imperials )
Your task is to choose a subset of the cells along your path in such a way that the sum of the numbers in the chosen cells is maximized. Your choice of cells must be such that exactly one chosen cell is present on each leg of the path. Note that cells at the intersection of two legs belong to both legs. What is the maximum possible sum you can form?
Input Format:
The first line contains one integer T, the number of testcases. The first line of each test case contains two space-separated integers N and M. Each of the next N lines contains M space separated integers, denoting cell values. The jth integer in the ith line denotes the value of the cell (i, j).
Constraints:
1 <= T <= 10
1 <= N, M <= 100
Numbers in each cell will be between -10000 and 10000 inclusive.
Output Format:
For each testcase output a single line containing the maximum sum you can form.
Sample Input:
3
2 2
-1 -2
5 -1
3 4
-1 2 -3 -4
-2 -3 5 -2
-1 -1 -2 3
2 2
3 1
5 3
Sample Output:
5
10
6
Explanation:
In the first test case, you can first move down and then move right. Your path now has 2 legs and you can choose only the cell containing 5. This is valid as it satisfies the condition that you must choose exactly one cell in each leg (because 5 is a part of both legs).
In the second test case, one best path is to walk right, choose 2, go right again and then down to choose 5, go further down and then right to pick up the final 3 (There are also other ways to pick-up the same numbers).
In the third test case, the best path is either (down, right) or (right, down). Note that since you can pick-up only one number in each leg you cannot select the ’5′ in the lower left corner (If you decide to pick-up 5, then you cannot pick up any other number because ’5′ is shared by both legs. We can do better by selecting both 3s).
Time limit: 2 seconds
Memory: 64 MB
ACM International Collegiate Programming Contest, 2010, Asia-Amritapuri Site
Solution ( Source : Team Imperials )
01 | /***** Author : Kunal *****/ |
02 | #include <iostream> |
03 | #include <cmath> |
04 | #include <cstdio> |
05 | using namespace std; |
06 |
07 | #define REP(a,b) for(int a=0;a<b;a++) |
08 | #define FOR(a,b,c) for(int a=b;a<c;a++) |
09 | #define FORD(a,b,c) for(int a=b;a>=c;a--) |
10 |
11 | #define S scanf |
12 | #define P printf |
13 |
14 | #define INF 1000000000 |
15 |
16 | int A[102][102]; |
17 | int rmax[102][102][102]; |
18 | int cmax[102][102][102]; |
19 | int n, m; |
20 |
21 | void findRowMax() |
22 | { |
23 | REP(i, n ) REP(j, m ) REP(k, m ) rmax[i][j][k] = -INF; |
24 | REP(i, n ) |
25 | { |
26 | REP(j, m ) |
27 | { |
28 | rmax[i][j][j] = A[i][j]; |
29 | FOR(k, j+1, m ) rmax[i][j][k] = max( rmax[i][j][k-1], A[i][k] ); |
30 | } |
31 | } |
32 | } |
33 |
34 | void findColMax() |
35 | { |
36 | REP(i, m ) REP(j, n ) REP(k, n ) cmax[i][j][k] = -INF; |
37 | REP(i, m ) |
38 | { |
39 | REP(j, n ) |
40 | { |
41 | cmax[i][j][j] = A[j][i]; |
42 | FOR(k, j+1, n ) cmax[i][j][k] = max( cmax[i][j][k-1], A[k][i] ); |
43 | } |
44 | } |
45 | } |
46 | int dp[102][102][2][2]; |
47 | int main() |
48 | { |
49 | int t; S("%d", &t ); |
50 | while( t-- ) |
51 | { |
52 | S("%d%d", &n, &m ); |
53 | REP(i, n ) REP(j, m ) S("%d", &A[i][j] ); |
54 | findRowMax(); findColMax(); |
55 | REP(i, n ) REP(j, m ) REP(k,2) dp[i][j][k][0] = dp[i][j][k][1] = -INF; |
56 | REP(i, m ) |
57 | { |
58 | if( i-1 >= 0 ) dp[0][i][0][0] = rmax[0][0][i-1]; |
59 | dp[0][i][0][1] = A[0][i]; |
60 | } |
61 | REP(i, n ) |
62 | { |
63 | if( i-1 >= 0 ) dp[i][0][1][0] = cmax[0][0][i-1]; |
64 | dp[i][0][1][1] = A[i][0]; |
65 | } |
66 | FOR(i, 1, n ) |
67 | { |
68 | FOR(j, 1, m ) |
69 | { |
70 | REP(k, j ) |
71 | { |
72 | dp[i][j][0][0] = max( dp[i][j][0][0], dp[i][k][1][0] + rmax[ i][ k+1][ j-1] ); |
73 | dp[i][j][0][0] = max( dp[i][j][0][0], dp[i][k][1][1] ); |
74 | dp[i][j][0][1] = max( dp[i][j][0][1], dp[i][k][1][0] + A[i][j] ); |
75 | } |
76 | REP(k, i ) |
77 | { |
78 | dp[i][j][1][0] = max( dp[i][j][1][0], dp[k][j][0][0] + cmax[ j][ k+1][ i-1] ); |
79 | dp[i][j][1][0] = max( dp[i][j][1][0], dp[k][j][0][1] ); |
80 | dp[i][j][1][1] = max( dp[i][j][1][1], dp[k][j][0][0] + A[i][j] ); |
81 | } |
82 | } |
83 | } |
84 | int Ans = -INF; |
85 | REP(i, 2 ) REP(j,2) Ans = max( Ans, dp[n-1][m-1][i][j] ); |
86 | P("%d\n", Ans ); |
87 | } |
88 | return 0; |
89 | } |
My three-year old has a set of rings of different sizes, each fitting
on a wooden peg, with all the pegs arranged in a row. He likes to
arrange the rings on the row of pegs in order of increasing size. He
likes to arrange the rings on the row of pegs in order of increasing (or
decreasing) size. He has exactly the same number of pegs and rings,
and has figured out that even if the rings are not in order to begin
with, by repeatedly swapping two adjacent rings, suitably selected, he
can order them.
Since he is something of a mathematical prodigy, at least in a fond father’s eyes, I gave him a challenge — he is only allowed to swap rings that are a fixed distance K from each other i.e. he gets to pick a ring, then swap it with one K positions before or K positions after. K=1 means the next ring before or after. Of course, this can be done only if there is a peg K positions away.
As I increased the number of rings and pegs in my kid’s toy, I realized that he will throw a tantrum if I give him an unsolvable problem, or one that will take too long to sort. So your task is to tell me how many swap operations are required to sort the rings.
Input:
The first line contains T, the number of test cases. Then, T test cases follow.
The first line of each test case contains 2 integers N and K, N being the number of rings.
The second line contains N integers denoting a1, a2, …., aN, where the a’s are the diameters of the rings. Values may be repeated.
1 <= K, N <= 500
1 <= T <=50
a[i] <= 1,000,000,000
Output:
Output must contain T lines, one per test case.
If it is possible to sort the array, output the minimum number of operations required, otherwise output “-1″.
Sample Input:
3
3 2
3 2 1
3 2
3 1 2
5 2
8 2 5 7 1
Sample Output:
1
-1
3
Since he is something of a mathematical prodigy, at least in a fond father’s eyes, I gave him a challenge — he is only allowed to swap rings that are a fixed distance K from each other i.e. he gets to pick a ring, then swap it with one K positions before or K positions after. K=1 means the next ring before or after. Of course, this can be done only if there is a peg K positions away.
As I increased the number of rings and pegs in my kid’s toy, I realized that he will throw a tantrum if I give him an unsolvable problem, or one that will take too long to sort. So your task is to tell me how many swap operations are required to sort the rings.
Input:
The first line contains T, the number of test cases. Then, T test cases follow.
The first line of each test case contains 2 integers N and K, N being the number of rings.
The second line contains N integers denoting a1, a2, …., aN, where the a’s are the diameters of the rings. Values may be repeated.
1 <= K, N <= 500
1 <= T <=50
a[i] <= 1,000,000,000
Output:
Output must contain T lines, one per test case.
If it is possible to sort the array, output the minimum number of operations required, otherwise output “-1″.
Sample Input:
3
3 2
3 2 1
3 2
3 1 2
5 2
8 2 5 7 1
Sample Output:
1
-1
3
In the digital world geometric shapes are drawn using pixels. A pixel is a square area of unit dimension. For this problem we say 2 pixels are connected if they share an edge or a vertex between them. This is also called 8-connectivity. Your task is to find the maximum possible area of a closed loop made up of A pixels (these are boundary pixels of the closed loop). Area of a closed loop is the number of pixels which are completely inside the loop or on the loop.
Consider the example below: For A = 4, you can make a close loop as follows -
This has an area of 5 with 4 pixels on the loop and 1 pixel completely inside the loop.
Input:
First line contains an integer N, the number of test cases.
Next N lines contain an integer A for that test case.
N <= 100
A <= 1000
Output:
Print N lines with a single integer stating the maximum area of a closed loop.
Sample Input:
2
4
5
Sample Output:
5
6
Given N1, M1, N2 and M2, find the smallest non-negative integer X such that X % M1 = N1 and X % M2 = N2.
Example Inout
4 7 8 13
4 6 8 12
0 5 0 10
Output:
60
-1
0
Subscribe to:
Posts
(
Atom
)
