What is a Smart DNS Proxy Server?

Location Switching with DNS : the use of a Proxy Program by setting up a dd-wrt router to run an intelligent, forward-looking, power-friendly, intelligent, power-friendly, pro-rated, pro-rata support for the device .
Intelligent DNS Proxy Services all you can unlock with a geo-dns, AOL TV, network 4, t-shirts, Netflix, MLS, Smart ip, etc. when you’ re on the lookout for a connection with the internet of things to your mind, you can use a good VPN, and your Proxy If you’ re on the internet for a connection with the internet, which will work for your users on the internet, you can intelligent DNS Proxy Services all you can unlock with a geo-dns, AOL TV, network 4, t-shirts, Netflix, MLS, Smart ip, etc. when you’ re on the lookout for a connection with the internet of things to your mind, you can use a good VPN, and your Proxy If you’ re on the internet for a connection with the internet, which will work for your users on the internet, you ‘
Intelligent DNS Proxy is a safe forward-looking tool for the development of web pages, such as sound and videos .

Acrylic is a local proxy for Windows that will improve your pc’s performance by cache the answers that come from your ip server and help you fight unsolicited advertisements through the application of a customized file of HOSTS ( it is best to handle many versions of netflix’s versions will allow you to access different from a clever proxy server such as the one that has to do with the next to the network .
Intelligent DNS proxy to look at Netflix, from fake to real, to avoid leaks on the objects and to set up the socks .
Intelligent DNS Proxy enables you to unlock the global Video and Plus, you’ ll get the villains, in the event that you’ re looking for a Proxy on the internet, in the event that you want to unlock the Websites, the Smart connection with the internet will help you to unlock the geo-restricted sites such as Netflix, Hulu, the internet, the internet, the internet of Netflix, the internet, the internet, the internet of intelligent DNS Proxy enables you to unlock the global Video and Plus, you’ ll get the villains, in the event that you’ re looking for a Proxy on the internet, in the event that you want to unlock the Websites, the Smart connection with the internet will help you to unlock the geo-restricted sites such as Netflix, Hulu, the internet, the internet, the internet of Netflix, the internet, the internet, the internet ,
Netflix is aggressively blocking IP addresses that Tunlr will allow you to browse through the IP filter known video streaming websites such as Netflix, Hulu and the free support of the internet for Netflix, or the intelligent Review of the IP .
The VPN of an intelligent DNS Proxy enables you to enjoy an infinite number of gears and speeds, no logs and solid coding .
The DNS intelligent DNS Proxy does not encode your information or modify your IP address .
Review : I’ ve tried a lot of time for the first time on the internet to check the functions and a database of the various protocols to achieve the best performance of South Africa and the smartwatch power of the device proved to be the quickest, but the simplest to configure a dd-based router, whether it’s a primary ip or a standard d
Intelligent DNS is a combination of server-name domains ( ip ) and touch-ups .
When using intelligent DNS, DNS servers will send back the IP of an intelligent proxy server instead of a Netflix IP .
For example, requests to a search engines such as Google would result in an intelligent DNS server response to the actual IP of the user and his next visits to the future to the future would not go through the intelligent proxy for the future .
In order to use the most intelligent proxy sites of the DNS, the IP address must be recorded in the system .
The main purpose of the intelligent DNS Proxy is to unlock websites and transmit services and provide intelligent DNS and VPN services .
The DNS intelligent DNS Proxy service does not have a client and therefore no interface to discuss .
Intelligent DNS Proxy is a forward-looking tool based on Seychelles’s forward-facing device, which includes PC, MAC, smart tv, Xbox, PS3, routers, ipads, ipads, iphones and the device .
With 400 servers in 80 locations, which covers 32 countries worldwide and provides DNS ip, the intelligent ip Proxy enables the user to log in to the VPN services and the DNS support .
Intelligent DNS Proxy uses an alternative method for the user to unlock websites and transmit content across different locations around the world .
Intelligent DNS Proxy offers 4 company-wide sms plan and price plan for each user .
Don’ t mess up with the simple change of your DNS 8-8-inch Server – Google’s famous Server .
Intelligent DNS Proxy offers an intelligent DNS service through its Proxy server, with a base fee for a trusted services .
Consumers in countries such as the united arab emirates and China will find the intelligent DNS service of over-lay as an important tool, intelligent DNS has some similar functions to VPN, but the user will discover that the service does not suffer any speed loss and gives immediate access to blocked sites and services .
Because there is such a high demand from current customers and they have such a vast expertise in their field, the intelligent Proxy for DNS has opted to provide a distinct VPN service to the entire bells and whistles .
Intelligent DNS Proxy is a site that enables you to safely unlock the world’s videos, music and web-based websites .
All you have to do is change your IP address to the device you are using to an intelligent DNS Proxy IP address .
And, depending on your particular requirements, the use of a VPN, a forward or a lawyer can do the trick .
Intelligent DNS services and power server are a” fast solution” to secure your online privacy, but they are not perfect .
Yes, Proxy servers may conceal your IP, and intelligent DNS services may conceal your geolocation, but it is all about it .
By creating a safe” tunnel” between the server, the use of the remote control of the internet allows the user to get confidential information from prying eyes .

Dns proxy services, which capture and filter out the queries of the forward-looking system, have been appreciated for a good reason .


They are on social media:

Facebook : https://www.facebook.com/smartdnsproxy
Twitter https://twitter.com/smartdnsproxy
Google+ : http://google.com/+Smartdnsproxy

Toptal for Machine Learning

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.

 

Which format of online programming contest i should participate more if eventually i want to get placed at companies like GOOGLE and FB?(…

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

What are the top analytics startups from India?

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

Invention is so easy.Isn’t it?

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.

The Theory behind Programming Contests

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.

A book that you can madly fall in love with

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.

Mini Games

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

SPOJ 3407. Candy

Here I come up with yet another SPOJ Problem. This problem appeared in my college’s tech fest’s programming contest(Code d basiCs). This is a lot simpler and smaller problem than my last post’s problem.

Problem code: SAMER08C

Little Charlie is a nice boy addicted to candies. He is even a subscriber to All Candies Magazine and was selected to participate in the International Candy Picking Contest.

In this contest a random number of boxes containing candies are disposed in M rows with N columns each (so, there are a total of M ×N boxes). Each box has a number indicating how many candies it contains.

The contestant can pick a box (any one) and get all the candies it contains. But there is a catch (there is always a catch): when choosing a box, all the boxes from the rows immediately above and immediately below are emptied, as well as the box to the left and the box to the right of the chosen box. The contestant continues to pick a box until there are no candies left.

The figure bellow illustrates this, step by step. Each cell represents one box and the number of candies it contains. At each step, the chosen box is circled and the shaded cells represent the boxes that will be emptied. After eight steps the game is over and Charlie picked 10+9+8+3+7+6+10+1 = 54 candies.

For small values of M and N, Charlie can easily find the maximum number of candies he can pick, but when the numbers are really large he gets completely lost. Can you help Charlie maximize the number of candies he can pick?

Input

The input contains several test cases. The first line of a test case contains two positive integers M and N (1 ≤ M ×N ≤ 105), separated by a single space, indicating the number of rows and columns respectively. Each of the following M lines contains N integers separated by single spaces, each representing the initial number of candies in the corresponding box. Each box will have initially at least 1 and at most 103 candies.

The end of input is indicated by a line containing two zeroes separated by a single space.

Output

For each test case in the input, your program must print a single line, containing a single value, the integer indicating the maximum number of candies that Charlie can pick.

Example

Input:

5 5
1 8 2 1 9
1 7 3 5 2
1 2 10 3 10
8 4 7 9 1
7 1 3 1 6
4 4
10 1 1 10
1 1 1 1
1 1 1 1
10 1 1 10
2 4
9 10 2 7
5 1 1 5
0 0

Output:
54
40
17

Added by: Diego Satoba
Date: 2008-11-23
Time limit: 2s
Source limit: 50000B
Languages: C C++ 4.0.0-8 C++ 4.3.2 TCL SCALA JAVA PYTH 2.6.2
Resource: South American Regional Contests 2008

______________________________________________________________________________________________

Solution:

One can solve the game by making the computer play the game by selecting among all possible choices and then among the remaining ones. Finally output the case with least sum as the answer. If that was the desired solution certainly Charlie would not have asked us to write a program for him.

The most interesting part of the game is to spot the underlying problem which enables us to maximize the overall sum for the game. Did you find it? Not yet? Well then let me tell you, the problem simply requires us to find the sequence for maximum sum in a row such that no two numbers are consecutive. After we recognize the hidden problem this tricky looking game boils down to finding the numbers of a sequence which gives maximum sum and no two numbers are consecutive either. After that we do the same with the result of each row in vertical direction. So basically now we have extracted the entire hidden problem but it is not over yet, this problem itself can be a bit tricky. So let’s now concentrate on the problem at hand i.e.

To find the numbers from a  given sequence  such that it has a maximum sum and no two of the selected numbers are consecutive . (say the given list of numbers is a0 to an).

Approach 1

We can keep picking non consecutive numbers until it is not possible to pick any more and then update the minimum sum found so far. This approach is correct but it runs in exponential time.

Approach 2

Now if we split the series in two series on either side of a randomly chosen number in a way such that we have maximum sum from the series on both sides of this number and this number which splits the series into two is not selected in any of the two series. Then it satisfies our criteria. The problem which arises here is, splitting along which number we can always have the maximum sum on either side is not known to us.

One can implement dynamic programming with the following recurrence relation:

k=j

For i<j, S(i,j)=Mink=i {S(i,k-1)+S(k+1,j)};……………(2.1)

For i=j, S(i,j)=S(i,i)=ai; ………………(2.2)

For i>j, S(i,j)=0 ; ……………..(2.3)

This looks to be a perfect implementation of dynamic programming but the bad news is it does not satisfy the time constraint of the problem. It runs in O(n*n*n) …………………(2,4)

It is a pitfall i have dragged you into. So we need a better one.

Approach 3

Actually the problem is not so complex.

Note, when a number is selected for partitioning at some other point it would need us to check this numbers selection again about some other partitioning. Therefore we still have over-lapping sub-cases.We have used dynamic programming and yet we have not been able to avoid re-computation completely. Isn’t it? Now note, we can not have 3 consecutive unselected numbers. There should be at least 1 and at most 2 not selected among those 3 consecutive numbers.but we didn’t utilize this property.

So When we chose a number randomly the question is why should we check iteratively all n such numbers to find which correctly splits the series when it can be decided among 3.It suffice to check immediate neighbors only(the one preceding and the one succeeding). The problem is that the way we defined our recurrence relation we did not leave any scope to know the status of the two neighbors (not even 1 neighbor).

Now check this recurrence definition where S(i) denote the sum max sum series from a0 to ai.

S(i)=Max{S(i-2) +ai, S(i-1)} [ for 2<=i<=n-1 ]………….……(3.1)

S(0)=a0 ….……………………(3.2)

S(1)=Max{a1,a0} ………………………(3.3)

Answer=Max{S(n-2),S(n-1)} ………………………….…(3.4)

Applying dynamic programming on this recurrence takes a time O(n)

Now returning back to Charlie’s game, for m rows it would take O(m*n) time plus time to compute vertically O(m).i.e. O(m*n)……………………………..…(3.5)

This algorithm scores full marks. Readers please help me optimize it further.

SPOJ 3551. IOI05 Garden

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 ≤l1 ≤l2 ≤l and 1 ≤w1 ≤w2 ≤w, a rectangular area with corners ( l1,w1), ( l1,w2), ( l2,w1) and ( l2,w2):

  • contains all the squares with coordinates ( x,y) satisfying l1 ≤ x ≤ l2 and w1 ≤ y ≤ w2, and
  • has perimeter 2 ·( l2 – l1 +1)+2 ·(w2-w1 +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 li, wi (1 ≤ li ≤ l, 1 ≤ wi ≤ w) separated by a single space — the coordinates of the square containing the ith 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

Added by: Ngô Minh Đức
Date: 2008-12-18
Time limit: 0.5s
Source limit: 50000B
Languages: All except: C++ 4.3.2 TCL SCALA PYTH 2.6.2 ERL TECS JS
Resource: IOI 2005 – Poland

____________________________________________________________

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 2nd 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(ri) as the Minimum Perimeter rectangle of k rose with the Starting side exactly along ith 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.