I came across toptal from a friend and was thrilled by the possiblities to connect to so different people who would be interested in your sckills acoss the world.

I have been doing lot of work in Machine Leraning using R and Python. I have a site sublimeinsights.in where we take machine learning project with emphasis on ensuring the data and well as the results remains confidential.

I have worked with Microsoft and Amazon and a couple of starups. I have applied machine learnig to Social Learning, IoT, Finance, Electrodynamic etc as part of my work.

Answer by Ishan Dutta:

I would say short contests.
Google, Facebook, Palantir, imo, pocket gems, rocket fuel most of them hire from short contests.
However there are companies like Quora who hire from long contests as well.
But if are only concerned about getting hired and not about the kind of work you will be hired for then your odds will be high participating in short contests.

View Answer on Quora

Answer by Ishan Dutta:

By "From India" I believe you mean companies founded by an Indian founder. Correct me if I am wrong . In that respect the companies which immediately come to mind are

• Fractal Analytic

• Latentview
• MuSigma
• Inductis
• absolutdata
• iCreate

If you include non-Indian MNCs who have set up their offices in India like IBM and Accenture it would be a huge list
For exhaustive lists you can check these pages:

Page on Analyticsindiamag
Consulting Companies in Analytics, Data Mining and Big Data
Page on Huntshire
Retail Consulting Jobs India
Premier Analytics Players
Analytics Training
122 Analytics Companies in India
Exhaustive List of Analytics Companies in India
Business Analytics and Advanced Analytics Companies in India
Page on Manavtalks
List of Analytics Consulting Companies in India
Analytics Companies
Exhaustive List of Analytics Companies in India
Page on Allinterview
Easy Analytics Solution Labs
Retail Consulting Jobs India
Analytics Companies Using SAS in India

View Answer on Quora

Elliptic Curve is supposed to be one of the most powerful weapons of modern mathematics. Basically Elliptic curve alongside Group theory has become the day to day language of a mathematicians of 20th and 21st century. The most notable use of Elliptic curves was done in Andrew Wiles proof of Fermat’s Last Theorem. Well, if you dont know Andrew Wiles you should not be calling yourself a Mathematics lover. Even in his effort to prove P!=NP (though unsuccessful) our very own Vinay Deolalikar’s tried to used elliptic cuves quite extensively.

It is that elliptic curve that are working with. We are trying to apply it in the field of Cryptography. But I feel we have failed to convince SKG sir with our procedings. Everyone asks “what new have you done?”. Actually we dont have anything new.Nor is it possible to have anything new so soon. If simply tampering of the problem in some way or the other is to be called a new thing then we should really be sorry. I have talked with students from IITs,ISIs,IIITs,MIT. Even they admit they don’t have mathematical depth to come up with new things as yet and we sitting here at IEM would invent new things every single day;what Mathematicians and Scientist are stuggling to find for thousands of year we will will do that within a flash. Is it a joke or what? If such was the case then all the theorems of text books would have been replaced by the names of IEMians instead of the Mathematician from the past.

Classical Problems:

Graph Theory-These are the easier problems in a programming contest.The challenge lies in the ability to manage time and memory with choice and implementation of appropriate Data Structure.

Number Theory-These are generally elementary but the toughest of all problems in any programming contest.By elementary what I mean is that the theory behind them is understandable even for a layman but are very difficult to reason out. They range from elementary gcd-lcm,factorization-primality,rationality-irrationality, divisibility-modularity to critical analysis of Diophantine equations.

Group Theory-Group Theory is the language of modern mathematicians and Computer Scientists.Tough to comprehend but has revolutionary range of applications and one of the most powerful weapons of a programmer. Group Theory along with Graph Theory forms the basis of solution to most of the tough Combinatorics problems.

Game Theory-Problems in game theory can range from easy to super tough ones.The hurdle is to identify the underlying problem from the complicated storyline or its application field’s description in the problem statement.

Computational Geometry-Techniques(mostly polynomial time) devised to tackle problems which are not solvable in constant time i.e using classical geometry solely.Prerequisite is to have a good understanding of High School Geometry and their manipulation techniques in Cartesian and polar co-ordinate system and a bit of elementary trigonometry as well.Computational Geometry is an area where programmers are mostly found to lag in.

Challenge Problems:

These are basically Optimization problems for which no particular correct algorithm exits(or has not been discovered till date).These problems generally do not form a part of any on-spot programming contest.They are mainly for contests which span over a longer period of time.These problems can be from any active research areas.
Sound knowledge of Calculus,Numerical Analysis, Probability ,Statistics, Fuzzy Logic,Neural Network and Artificial Intelligence comes in handy.

The Art and Craft of Problem Solving

The book doesn’t teach you how to get 4 by adding a two to another two,
it makes you realize why the result is 4 and not 1 or 3.
The books does not attempt to give you a collection of mind boggling problems.
the book makes you realize how our mind works to decide which is trivial and
which is not or rather to be specific why it is not.It makes you realize why a same problem appears simple to one but super tough to another.
in what different way do those two persons brain work.
The book does not boost your mathematical knowledge.but it makes you think
about the way you have been thinking for years.
It gives wonderful names and similes to techniques that we have been using from
our birth without actually being aware of it.
I haven’t made much inroads into the book yet,I am only halfway through the book,
but whatever little I have seen the book is bound to fill the heart of any
scientifically thinking person with enormous joy.

Here are a couple of games that I had made some times back.These are nothing but plain programs in  Turbo C.No help of graphics has been taken.Download and play and feel free to comment on the run-time errors that you may encounter or anything about them.

PINGPONG
TETRIS

This is a SPOJ Problem. Here is the solution. It is for readers to optimize it further or give me better alternative means. Let’s take a look at the problem first.

Problem code: BGARDEN

Byteman owns the most beautiful garden in Bytetown. He planted n roses in his garden. Summer has come and the flowers have grown big and beautiful. Byteman has realized that he is not able to take care of all the roses on his own. He has decided to employ two gardeners to help him. He wants to select two rectangular areas, so that each of the gardeners will take care of the roses inside one area. The areas should be disjoint and each should contain exactly k roses. Byteman wants to make a fence surrounding the rectangular areas, but he is short of money, so he wants to use as little fence as possible. Your task is to help Byteman select the two rectangular areas.

The garden forms a rectangle l meters long and w meters wide. It is divided into l ·w squares of size 1 meter × 1 meter each. We fix a coordinate system with axes parallel to the sides of the garden. All squares have integer coordinates ( x,y) satisfying 1 ≤ x ≤ l, 1 ≤ y ≤ w. Each square may contain any number of roses.

The rectangular areas, which must be selected, should have their sides parallel to the sides of the garden and the squares in their corners should have integer coordinates. For 1 ≤l₁ ≤l₂ ≤l and 1 ≤w₁ ≤w₂ ≤w, a rectangular area with corners ( l₁,w₁), ( l₁,w₂), ( l₂,w₁) and ( l₂,w₂):

• contains all the squares with coordinates ( x,y) satisfying l₁ ≤ x ≤ l₂ and w₁ ≤ y ≤ w₂, and
• has perimeter 2 ·( l₂ – l₁ +1)+2 ·(w₂-w₁ +1).

The two rectangular areas must be disjoint, that is they cannot contain a common square. Even if they have a common side, or part of it, they must be surrounded by separate fences.

Task

Write a program, that:

• reads from the standard input the dimensions of the garden, the number of roses in the garden, the number of roses that should be in each of the rectangular areas, and the positions of the roses,
• finds the corners of two such rectangular areas with minimum sum of perimeters that satisfy the given conditions,
• writes to the standard output the minimum sum of perimeters of two non-overlapping rectangular areas, each containing exactly the given number of roses (or a single word NO, if no such pair of areas exists).

Input

The first line of standard input contains two integers: l and w (1 ≤ l,w ≤ 250 ) separated by a single space — the length and the width of the garden. The second line contains two integers: n and k (2 ≤ n ≤ 5000 , 1 ≤ k ≤ n/2 ) separated by a single space — the number of roses in the garden and the number of roses that should be in each of the rectangular areas. The following n lines contain the coordinates of the roses, one rose per line. The ( i+2)^nd line contains two integers l_i, wⁱ (1 ≤ l_i ≤ l, 1 ≤ w_i ≤ w) separated by a single space — the coordinates of the square containing the i^th rose. Two or more roses can occur in the same square.

In 50% of test cases, the dimensions of the garden will satisfy l,w ≤ 40 .

Output

The standard output should contain only one line with exactly one integer — the minimum sum of perimeters of two non-overlapping rectangular areas, each containing exactly k roses, or a single word NO, if no such pair of areas exists.

Example

For the input data:
6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1
the correct result is:
22
1 2 3 4 5 6
1
2
3
4
5

____________________________________________________________

Solutions:

All through the solution I have used the array notation rather than the Cartesian co-ordinate convention of the problem statement.

ALGORITHM 1A

The first thing that comes to mind is to apply brute force to find the minimum perimeter by checking all the (w*l)*(w*l) rectangles (i.e. we can find top left corner in w*l ways and bottom right corner in w*l ways) and to count the number of roses in each of those rectangles it takes time proportional to further w*l.
thereby taking a total time of O(w*w*w*l*l*l)……………………. (1.1)
we can find the least among them in O(w*w*l*l)………………….(1.2)
thereby effective time= w*w*w*l*l*l + w*w*l*l .
i.e. O(w*w*w*l*l*l)…………………………………………………………..(1.3)

ALGORITHM 1B

Are we done? We have just calculated minimum perimeter of a rectangle containing exactly k roses.
But in the problem statement we are asked to find two disjoint (non-overlapping) rectangles having exactly k roses such that their sum of perimeters is least. So didn’t we just goof up? Didn’t we end up calculating something not required. Let’s now proceed towards what we think is required for the given problem.
So among w*w*l*l rectangles we can find the two rectangles having exactly k roses each with least sum of perimeters among all non-intersecting pair of rectangles in
O((w*w*l*l)*(w*w*l*l))…..…………………………………….. (1.4)
(i.e. selection of two objects among n objects in done in nC2 ways i.e.O(n*n),here the number of objects is w*l*w*l rectangles)

thereby effective time= w*w*w*l*l*l + w*w*w*w*l*l*l*l .
i.e. O(w*w*w*w*l*l*l*l)…………………………………………………. (1.5)
This makes a horribly poor time complexity.

ALGORITHM 2

Careful observations can lead to a much better result.

Firstly we don’t need to count the number of roses in a given rectangle traversing through the entire rectangle every single time only if we pre compute it dynamically.
If R(r1,c1,r2,c2) — the number of roses in a rectangular region with corners (r1,c1) and (r2,c2) is:
R(r1,c1,r2,c2) = R(r2,c2) − R(r2,c1−1)− R(r1−1,y2) + R(r1−1,c1−1) …………………………………………(2.1)

The pre-computation matrix form the above recurrence relation is dynamically generated in O(w*l )…………………………………………….(2.2).
Thus time for rose counting operation for a rectangle reduces down from O(w*l) to O(1) ……………………………………………..(2.3)
and time for counting for all (w*l)*(w*l) rectangles reduces from O(w*w*w*l*l*l) to O(w*w*l*l)……………………………………….(2.4)
effective time= (w*l+w*w*l*l) + w*w*w*w*l*l*l*l .
i.e. O(w*w*w*w*l*l*l*l)…………………………………………………..(2.5)
However the above trick of introducing dynamic programming does not reduce our time as the time complexity of the algorithm is dominated by the last term(i.e. finding of two rectangles with least sum of perimeters among all non-intersecting pair of rectangles)

ALGORITHM 3

This can make the improvement in ALGORITHM 2 look useless as it eventually results in the same time complexity as ALGORITHM 1B.To make our effort of trickily implementing dynamic programming to compute the number of roses in a given rectangle not go in vain we need to reduce the time of finding of two rectangles with least sum of perimeters among all non-intersecting pair of rectangles too.

The first part of observation is if the rectangles are non-overlapping then there must be a line separating them(either horizontal or vertical).So we are no longer required to find disjoint pair of rectangle among (w*l)*(w*l) rectangles. We now just have to find least perimeter rectangle containing exactly k roses on either side of this line and then add the two. We have to do this for all l-1+w-1 such lines and find which of these l-1+w-1 cases yields a minimum.
So finding rectangle of least perimeter containing k roses algorithm from ALGORITHM 1A and counting of roses in a given rectangle from ALGORITHM 2 we have,
effective time= (w*l+w*l*w*l) + w*w*l*l*(w+l).
i.e. O(w*w*l*l*(w+l))………………………………………………………..(3.1)
Still the 2^nd part of the time complexity equation dominates but we have reduced it significantly from O(w*w*w*l*l*l) to O(w*w*l*l*(w+l))……………………………………………………………..(3.2)

<<Note:-did you notice how finding of rectangle having the least perimeter with k roses comes into play. when we initially did that in ALGORITHM 1A it looked so irrelevant but now the more formidable idea of considering two rectangles with least sum of perimeters among all non-intersecting pair of rectangles is no longer being considered a good idea>>

ALGORITHM 4

Every time we are selecting a line we are having to check for all possible rectangles on either side of the line cant we optimize it any further. The answer is yes we can look whenever we are shifting a line to its next line we are checking a large number of rectangles many of which are same as that we found for the last line. So don’t you think we are unnecessarily rechecking them? Here again to avoid re-computation we can take the help of dynamic programming. Let’s see how. I wont call it dynamic programming as we are not having any recurrence relation to work with but we know there are something common for two or more line and that re-computation needs to be avoided. So we need some sort of relation.

Observe carefully, say we have a line next to r, let’s consider the lower part of r. So we have to find all possible rectangles whose one line(take it to be upper line) must be lying among one of the lines r+1, r+2,….,l.

If we define MD(r) as the Minimum Perimeter rectangle of k rose Down of Row r and MSR(r_i) as the Minimum Perimeter rectangle of k rose with the Starting side exactly along i^th Row.()

Then we have MD(r) = min {MSR(r+1), MSR(r+2)…, MSR(l)}….(4.1)

Similarly we can have MU, MR, ML and analogously MER,MSC,MEC

Now let’s discuss how to make use of such a relation. For that we use a kind of memorization. Lets set the 4 lists MSR,MER,MSC and MEC initially to infinity. Now we just traverse once (i.e. consider all w*l*w*l rectangles) and update these 4 lists accordingly. This operation takes only time of O(w*l*w*l)…………………………………………………(4.2)

For a given line we can get the least perimeter k rose containing rectangle from its respective list just in linear time i.e. O(l) or O(w)…………(4.3)

Considering all lines effective time is O(l*l+w*w)…………………(4.4)

After incorporation of this idea of memorization into our algorithm

effective time = (w*l+w*w*l*l) + {w*w*l*l +( l*l +w*w)}

i.e. O(w*w*l*l)………………………………………………………(4.5)

ALGORITHM 5

Now here is a point worth noting. Interestingly if we see very carefully observe we can find that we do not need to consider all rectangles having exactly k roses.
We can restrict our considerations to only those rectangles having exactly k roses which do not contain any other rectangles having exactly K roses in their interiors. So here we incorporate our ^4th trick.

Let us consider a case for a given r1 and r2.Say suppose we have found

Case1:R(r1, c1, r2, c2) =k then we have found a required rectangle and we are sure that for minimum perimeter and for a given r1 and r2 the value c2-c1 can not be any greater but it may not be lesser. So there is no point in incrementing c2 for same c1.so we increment c1 (trying to find smaller rectangles with k roses) keeping

Case2:R(r1, c1, r2, c2) >k then is a chance of finding a rectangle in its interior with exactly k rosés. We contract the rectangle by incrementing c1 (why did not we contract by decreasing c2? because that case has already been considered)

Case3:R(r1, c1, r2, c2) <k then there is no point decreasing c2-c1 value further because if this rectangle does not have k roses then there is no way a rectangle interior to it will have k roses we increase c2 to make the rectangle bigger.

In this entire algorithm we either increment c1 or c2 until c2>w

So it takes a linear time i.e. O(w)…………………………………(5.1)

But remind u, we have done this calculation for a given r1 and r2.

Now we have to consider all pair of r1 and r2 which takes O(l*l)…………..(5.2)

As for a given rectangle number of roses can be found in O(1) [from equation 2.2]time we are not required to check no of roses for all possible w*w*l*l. We will only retrieve the number of rose information in O(1) time and that time will be proportional to the number of rectangles taken up for consideration i.e.O(w*l*l)…………………………………………………………(5.3)

Effective time = (w*l+w*l*l) + {w*l*l + (l*l +w*w)} i.e.O(w*l*l)………………………………………………………..(5.4)

<<note: in both case1 and we increment c1 the only difference is in case1 we update the memorization list values i.e. MPSC(c1) , MPEC(c2), MPSR(r1) and MPER(r2) before shifting the starting column c1 rightward>>

Questions that should come to mind:

1. Why are we having to count a single rose every time for all w*l*w*l rectangles?
2. How have we utilized the fact that the two rectangles will be disjoint?
3. Why do we have to have to traverse through entire side of a line just for altering the line one place to the right or left we must prevent recalculation of those rectangles already found. Don’t we?
4. What about those rectangles of k roses within another rectangle of k roses. They both must have the same k roses which all must lie in the interior most rectangle of k roses. Then why are we calculating. The innermost must have the minimum perimeter. Isn’t it?

Their answers are the following tricks that we applied:

1. Dynamic Programming to pre-compute number of roses.
2. Separating Lines concept
3. Memorization List
4. Contraction & Expansion of rectangle along a particular axis with size constraint.