Re: [algogeeks] String Problems
I was thinking about a substring matching, but if that's not what you need, then you still have the same number of strings, but finding a matching in a string would take quadratic time on the length of the string, instead of linear time. 2010/5/20 vignesh radhakrishnan rvignesh1...@gmail.com @Marcio, I get your algo now. So a substring match is also a match. I get your approach. Thank you. Any ideas for the second problem? On 20 May 2010 10:45, vignesh radhakrishnan rvignesh1...@gmail.comwrote: @Mario Your estimate of no. of strings, I guess doesn't consider strings of length less than length H or W. it would order(4H^2+4W^2) approximately. I guess I 've understood it right. correct me if I'm wrong On 20 May 2010 07:23, Mario Ynocente Castro ycma...@gmail.com wrote: I don't think 1014 needs any special algorithm, if we've got an H x W matrix, then we've got (4H+4W-2) strings in which you must look, and you can do this with a greedy strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- There are two kinds of people. Those who care for others and The others -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: number calculation
http://code.google.com/codejam/contest/dashboard?c=32016#s=aa=2 2010/5/19 Adrian kri...@gmail.com The only solution I can think of is to use the binomial theorem (http://en.wikipedia.org/wiki/Binomial_theorem) to expand (3+sqrt(5))^n . Then you only need to take into the account the terms where y (sqrt(5)) has an odd power because all others are integers and won't affect the decimals. Then after adding them up you'll end up with something like n * sqrt(5) where n is the total of the coeficients of sqrt(5) and then just do the math and find out the 3 decimals. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] General issues about ACM (uva.onlinejudge.org) tasks and problem 103
After ordering, you can solve it like the Longest Increasing Sequence (LIS)
problem, using Dynamic Programming.
2010/5/19 bob198107 robertosp...@gmail.com
Hi.
First: I'm new in ACM. 2 day took me to find out how to read and write
data in the tasks. There should be some sample code for beginners for
this.
Second: For me it is not clear what should be done, even if I read the
text of the tasks few times. I wonder if I am so intellectually
limited or it has to be so, but I don't know how to bite it.
Third: I sit on problem
103 Stacking Boxes. I sorted input rows (each box lengths
increasingly). Then I thought I have to sort boxes by the capacity or
something like that. So I sorted boxes by perimeter increasingly. And
then check if boxes nest to each other starting from the smallest one.
For sample input data from uva.onlinejudge.org and www.algorithmist.com
it works fine. For my data too. But it has to be wrong cause' of
Wrong answer if I submit the code. I would like my algorithm to
work.
Fourth: Solution from
http://cmagical.blogspot.com/2010/01/dowloads-1submitted-solutions-to...
works but I found place which I don't really understand:
#includestdio.h
#includestdlib.h
const int MAX = 33;
int boxes[MAX][12];
int rawIndex[MAX], v[MAX];
int path[MAX], rawsNumber, dimention;
int compare(const void *a, const void *s) {
return *(int *)a - *(int *)s;
}
int compareRaws(int n, int m){
for (int i = 0; i dimention; i++) {
if (boxes[n][i] = boxes[m][i]) {
return 0;
}
}
return 1;
}
void sortIndexes() {
for (int i = 0; i rawsNumber - 1; i++) {
for (int j = i + 1; j rawsNumber; j++) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
rawIndex[i] ^= rawIndex[j] ^= rawIndex[i] ^=
rawIndex[j];
}
}
}
}
void print(int n){
if (path[n] == -1) {
printf(%d, rawIndex[n] + 1);
return;
}
print(path[n]);
printf( %d, rawIndex[n] + 1);
}
void solveCase() {
int max, indexSize = 0, last;
int par;
sortIndexes();
-- THIS PLACE I
DON'T UNDERSTAND
for (int i = 0; i rawsNumber; i++) {
max = 0;
par = -1;
for (int j = i - 1; j = 0; j--) {
if (compareRaws(rawIndex[i], rawIndex[j])) {
if (v[j] max) {
max = v[j];
par = j;
}
}
}
path[i] = par;
v[i] = max + 1;
if (v[i] indexSize) {
indexSize = v[i];
last = i;
}
}
printf(%d\n, indexSize);
print(last);
putchar('\n');
}
void readCase(){
for (int i = 0; i rawsNumber; i++) {
rawIndex[i] = i;
for (int j = 0; j dimention; j++) {
scanf(%d, boxes[i][j]);
}
qsort(boxes[i], dimention, sizeof(int), compare); // sorting
every read raw
}
}
int main(int argc, char *argv[]) {
while (scanf(%d%d, rawsNumber, dimention) == 2) {
readCase();
solveCase();
}
return 0;
}
It's kind of sorting indexes of raws by comparing values of two fields
i and j for each i and j. Rest of it is the algorithm I can imagine.
So any suggestions or reply to my rubbishy writing pleased welcome.
--
You received this message because you are subscribed to the Google
Groups acm_solver group.
To post to this group, send email to acm_sol...@googlegroups.com.
To unsubscribe from this group, send email to acm_solver
+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/acm_solver?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mario Ynocente Castro
Undergraduate Student of System Engineering
National University of Engineering, Peru
http://sites.google.com/site/ycmario
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
Re: [algogeeks] String Problems
I don't think 1014 needs any special algorithm, if we've got an H x W matrix, then we've got (4H+4W-2) strings in which you must look, and you can do this with a greedy strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Yahoo coding round question
I don't think DP is a good strategy for the N strings case 2010/5/8 sharad kumar aryansmit3...@gmail.com pls check cormen i think thats most efficicent ...check under DP chapter On Sat, May 8, 2010 at 2:30 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: Find the longest common subsequence of given N strings each having length between 0 to M. Can anybody give a good approach to the solutions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] combination problem
It's equivalent to (x1-1)+(x2-1)+. . .+(xk-1)=n-k (You need n=k) yi = xi - 1, so for every 1=i=k, we have that yi is non-negative. Now think about it as having (n-1) objects in a row, and you need to choose k-1 which will be black and the other n-k will be white so, the number of solutions is equal to (n-1)C(k-1). 2010/4/9 GentLeBoY vikrantsing...@gmail.com no. of solutions to linear equation as x1+x2+x3+. . .+xk=n , all variables are positive natural numbers how is it (n-1)C(k-1) plz explain -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Convex hull
Well, I use the Monotone Chain Algorithm ( http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull) 2010/3/26 Umer Farooq the.um...@gmail.com Given a set of points, how can i find the convex hull in O(nlog(n)) ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro 20074016B FIIS - UNI -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] missing integers in an unsorted array
You could use a boolean array to mark which numbers you have on the list. 2010/1/31 Banoo banoo.rekh...@gmail.com hi, can you help me solve the following problem? You are given an unsorted list of n-1 distinct integers from the range 1 to n. Write a linear-time algorithm to find the missing integer. Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro 20074016B FIIS - UNI -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
