Guys,
I was just trying to solve the problem "Mountain Village" in acm
problemset site. I figured out a way to solve it but it turned out to
be extremely inefficient. It exceeded the time limit. Can anyone give
me an idea about how to solve it with better technique and better
timing.
Please help, I do not need any code, just idea/technique to enhance my
skill.
Thanks,
Farhan
Here is the problem:
<Problem>
Mountain Village
After a long summer's march through the rough terrain of northern
America, the indian tribe had found a place where they hopefully would
be left alone. The chief proclaimed that this would be the new place
for their village, despite the rocky nature of the landscape. They set
a temporary camp for the night, content with the piece of land they had
discovered. The very next day however, it stood clear that some effort
planning the locations of the Teepee tents had to be made. It was
simply too great a difference in altitude between the tents, making the
walk along some paths extremely tiresome. Therefore, the chief ordered
his witty son, Fast Thought, to find a connected area in their
vicinity, large enough to host all tents of the tribe, having as small
difference between the highest and lowest point as possible.
The task called for some altitude measurements of their whereabouts,
which caused no problem for Fast Thought, since he was wise in the ways
of trigonometry. He divided the land into squares big enough to host a
tent each and estimated the altitude of each square. Now the problem
was reduced to finding a connected region containing at least as many
squares as there were tents, having the smallest difference between the
highest and lowest altitude. He drew a rectangular matrix A,
representing the area, where the entry ai;j at row i and column j, was
the altitude of the square with coordinates (i; j). He considered an
entry ai;j adjacent to the entries ai, j+1, ai+1, j ; ai, j-1 and
ai-1, j , and called a set of entries connected if for every pair of
entries in the set, there was a connecting path of adjacent entries in
it. Since the size of the tribe altered with time, Fast Thought decided
to solve the problem for a general number of tents. Thus the problem
left to solve for him was to find a set of at least k connected entries
aij in the matrix A, such that the difference between the largest and
the smallest entry in the set was minimized.
Input
On the first line of input there are two integers, r; c <= 40, giving
the dimension of the matrix A. The following r lines, each containing c
integers between 0 and 99, are the entries a i,j of the matrix. The
next line contains a single integer n _ 100, and is followed by n lines
each holding a single positive integer ki <= rc.
Output
For each ki, output one line containing the minimum difference between
the largest and the smallest entry for any connected set of at least ki
entries.
Sample Input
5 10
0 0 3 46 0 46 0 0 12 12
0 0 13 50 49 46 11 10 10 11
0 51 51 49 99 99 89 0 0 10
0 0 48 82 70 99 0 52 13 14
51 50 50 51 70 35 70 10 14 11
6
1
5
10
12
47
50
Sample Output
0
0
3
4
89
99
</Problem>
Here is my code:
<Code>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#ifdef DEBUG
#define DB(X) std::cout << X << '\n';
#define DB_STAT(X) std::cout << #X << " = " << X << '\n';
#else
#define DB(X)
#define DB_STAT(X)
#endif
#define HIGH 0xFFFF0000
#define LOW 0x0000FFFF
typedef std::set<int> SquareSet;
typedef SquareSet::iterator SquareSetIterator;
struct SSet
{
int m_iMaxHeight;
int m_iMinHeight;
int m_iDifference;
SquareSet m_SquareSet;
};
int main(int argc, char** argv)
{
freopen("10486.in", "r", stdin);
int iRows, iColumns, iTests, i, j, k, l, iMax;
int iMatrix[40][40];
int iTest[100];
int iDiffRow[4] = { 0, -1, 0, 1 };
int iDiffColumn[4] = { -1, 0, 1, 0 };
cin >> iRows >> iColumns;
for(i = 0; i < iRows; i++)
for(j = 0; j < iColumns; j++)
cin >> iMatrix[i][j];
cin >> iTests;
iMax = 0;
for(i = 0; i < iTests; i++)
{
cin >> iTest[i];
if(iTest[i] > iMax)
iMax = iTest[i];
}
DB_STAT(iRows);
DB_STAT(iColumns);
DB_STAT(iTests);
DB_STAT(iMax);
std::vector<int> ResultVector(iMax + 1);
//int ResultVector[1601];
//std::vector<struct SVillageSet> VillageSetVector(iMax - 1);
SSet VillageSet[40][40];
SSet* pSSet;
ResultVector[0] = ResultVector[1] = 0;
int iTemp;
for(i = 0; i < iRows; i++)
for(j = 0; j < iColumns; j++)
{
pSSet = &VillageSet[i][j];
pSSet->m_iMaxHeight = iMatrix[i][j];
pSSet->m_iMinHeight = iMatrix[i][j];
pSSet->m_iDifference = 0;
pSSet->m_SquareSet.insert((i << 16 | j));
//DB_STAT((i << 16 | j));
//DB_STAT(pSSet->m_SquareSet.size());
}
int tj, tk, iRow, iColumn, iMinJ, iMinK, iMinDiff, iHeight, iDiff,
iMinDiffCluster;
SquareSet* pSquareSet;
SquareSetIterator Iter, EndIter;
for(i = 2; i <= iMax; i++) // Cluster size
{
iMinDiffCluster = 0x7FFFFFFF;
for(j = 0; j < iRows; j++) // Row
{
for(k = 0; k < iColumns; k++) // Column
{
pSSet = &VillageSet[j][k];
pSquareSet = &(pSSet->m_SquareSet);
iMinDiff = 0x7FFFFFFF;
//DB_STAT(pSquareSet->size());
EndIter = pSquareSet->end();
for(Iter = pSquareSet->begin(); Iter !=
EndIter; ++Iter)
{
// All members of set
//DB("I am in");
iTemp = *Iter;
iRow = (iTemp & HIGH) >> 16;
iColumn = (iTemp & LOW);
for(l = 0; l < 4; l++) // Neighbourhood
{
tj = iRow + iDiffRow[l];
tk = iColumn + iDiffColumn[l];
//DB("iRow " << iRow << "
iColumn " << iColumn << " tj: " << tj
<< " tk: " << tk);
if(tj >= 0 && tj < iRows && tk
>= 0 && tk < iColumns)
{
if(EndIter ==
pSquareSet->find((tj << 16 | tk)))
{
iHeight =
iMatrix[tj][tk];
if(iHeight >
pSSet->m_iMaxHeight)
iDiff =
iHeight - pSSet->m_iMinHeight;
else if(iHeight
< pSSet->m_iMinHeight)
iDiff =
pSSet->m_iMaxHeight - iHeight;
else
iDiff =
pSSet->m_iDifference;
//DB("iDiff "
<< iDiff << " iMinDiff " << iMinDiff);
if(iDiff <
iMinDiff)
{
iMinDiff = iDiff;
iMinJ =
tj;
iMinK =
tk;
}
}
}
}
}
iHeight = iMatrix[iMinJ][iMinK];
if(iHeight > pSSet->m_iMaxHeight)
pSSet->m_iMaxHeight = iHeight;
else if(iHeight < pSSet->m_iMinHeight)
pSSet->m_iMinHeight = iHeight;
pSquareSet->insert((iMinJ << 16 | iMinK));
DB_STAT(pSquareSet->size());
pSSet->m_iDifference = iMinDiff;
if(iMinDiff < iMinDiffCluster)
iMinDiffCluster = iMinDiff;
}
}
ResultVector[i] = iMinDiffCluster;
}
for(i = 0; i < iTests; i++)
cout << ResultVector[iTest[i]] << '\n';
return 0;
}
</Code>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
