[algogeeks] finding closest points
Given a set of points in 2D space, how to find the k closest points for a given point, in time better than nlgn. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] SPOJ STRDIST
http://www.spoj.pl/problems/STRDIST/
Getting WA repeatedly. Can someone help me with the below code.
#include
#include
#include
#include
using namespace std;
int main()
{
int k,l;
scanf("%d %d",&k,&l);
string str1 = "";
string str2 = "";
if (k>0)
cin >> str1;
if(l>0)
cin >> str2;
str1 = "0" + str1;
str2 = "0" + str2;
int m,n;
m = k;
n = l;
int pos[][3] = {
{2,1,0},
{0,2,1},
{1,0,2}
};
int I,I1,I2;
int posIdx = 0;
int dp[3][n+1];
for (int i = 0 ; i < 3; i++)
for (int j = 0 ; j <=n; j++)
dp[i][j] = 200;
dp[0][0] = 0;
for (int i = 0 ; i <= m; i++)
{
if (i >= 2)
{
I = pos[posIdx][0]; I1 = pos[posIdx][1]; I2 =
pos[posIdx][2];
}
else
{
I=i;I1=i-1;
}
for (int j = 0 ; j <=n; j++)
{
if (i == 0 && j == 0) continue;
if ( j - i > 105)
break;
bool updated = false;
if (j > 0)
{
dp[I][j] = min(dp[I][j],dp[I][j-1] + 1);
updated = true;
}
if (i > 0)
{
if (updated)
dp[I][j] = min(dp[I][j],dp[I1][j] + 1);
else
dp[I][j] = dp[I1][j] + 1;
}
if (i > 0 && j > 0 && str1[i] == str2[j])
{
dp[I][j] = min(dp[I][j],dp[I1][j-1]);
}
if (str1[i] == str2[j-1] && str1[i-1] == str2[j] &&
i>=2 && j>=2)
{
dp[I][j] = min(dp[I][j],dp[I2][j-2] + 1);
}
if (i > 0 && j > 0 && str1[i] != str2[j])
{
dp[I][j] = min(dp[I][j],dp[I1][j-1] + 1);
}
}
if (i >= 2)
{
posIdx = (posIdx + 1)%3;
}
}
printf("%d\n",dp[k%3][l]);
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] exon chaining
Can some one help in finding out the bug in the below code.
Input: (left,right,weight) representing intervals
Output: maximum weight of non-overlapping intervals
#include
#include
#include
#include
struct point
{
int value;
bool isLeft;
long int weight;
int index;
struct point* prev;
};
typedef struct point* NODEPTR;
bool compare (NODEPTR A,NODEPTR B)
{
return (A->value < B->value);
}
int main()
{
int numIntervals;
cin >> numIntervals;
// read the intervals and sort the list
vector points;
for (int i=0; i < numIntervals; i++)
{
NODEPTR p1 = new point;
p1->isLeft = true;
p1->weight = 0;
p1->prev = NULL;
cin >> p1->value;
points.push_back(p1);
NODEPTR p2 = new point;
p2->isLeft = false;
p2->prev = p1;
cin >> p2->value;
cin >> p2->weight;
points.push_back(p2);
}
sort(points.begin(),points.end(),compare);
vector::iterator it;
int idx=1;
for (it=points.begin(); it!=points.end(); ++it)
{
(*it)->index = idx++;
}
/*for (it=points.begin(); it!=points.end(); ++it)
{
if ((*it)->prev != NULL)
cout << (*it)->prev->value << " " << (*it)->value << "
" << (*it)-
>weight << " " << (*it)->prev->index << endl;
}*/
int score[2*numIntervals + 1];
for (int i=0; i <= 2*numIntervals; i++)
{
score[i] = 0;
}
int i = 1;
for (it=points.begin(); it!=points.end(); ++it)
{
// right end of the interval
if (false == (*it)->isLeft)
{
int j = (*it)->prev->index;
int t1 = score[j] + (*it)->weight;
int t2 = score[i-1];
if (t1 < t2)
score[i] = t2;
else
score[i] = t1;
}
else
{
score[i] = score[i-1];
}
i++;
}
cout << "Max weight is " << score[2*numIntervals] << " " <<
2*numIntervals << endl;
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Compositions of a number
Can you tell me the name of the equivalent SPOJ problem ? On Mar 21, 6:23 pm, Azazle simon wrote: > Dude, its spoj pbm and see eular diagram > > On 3/20/11, ganesha wrote: > > > > > > > Given a number n, write a program to output its various compositions > > where order is not important. > > > For eg, for 5, it will be > > > 1 + 4 > > 1 + 1 + 3 > > 1 + 1 + 1 + 2 > > 1 + 1 + 1 + 1 + 1 > > 1 + 2 + 2 and so on > > > Order is not important implies 1 + 4 is same as 4 + 1. > > > Modify the program such that the order is important. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Sent from my mobile device- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Compositions of a number
Given a number n, write a program to output its various compositions where order is not important. For eg, for 5, it will be 1 + 4 1 + 1 + 3 1 + 1 + 1 + 2 1 + 1 + 1 + 1 + 1 1 + 2 + 2 and so on Order is not important implies 1 + 4 is same as 4 + 1. Modify the program such that the order is important. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
