Re: [algogeeks] quick sort
You can't make it deterministically run in O(nlogn). On Wed, Jan 5, 2011 at 1:25 PM, lee steath...@gmail.com wrote: how can we make quick sort to run in O(logn) time in worst case?? -- 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. -- 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] quick sort
If we modify the PARTITION to use SELECT algorithm given in clrs to find median and partition the array about it, then i think it will be O(nlogn) worst case, because the array will be perfectly divided into 2 equal size arrays each time. But is the practical implementation of SELECT that fast? -- 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] Dynamic Programming
1-D simple dp with state current index you are at On Wed, Jan 5, 2011 at 7:41 AM, Akash Agrawal akash.agrawa...@gmail.comwrote: didn't get the question correct... Can u cite an example... Regards, Akash Agrawal http://tech-queries.blogspot.com/ On Wed, Jan 5, 2011 at 12:36 AM, Decipher ankurseth...@gmail.com wrote: Yuckdonald's is considering opening a series of restaurants along Quaint Valley Highway (QVH).The n possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order,m1;m2; : : : ;mn. The constraints are as follows: 1)At each location,Yuckdonald's may open at most one restaurant.The expected profi t from opening a restaurant at location i is pi, where pi 0 and i = 1; 2; : : : ; n. 2)Any two restaurants should be at least k miles apart, where k is a positive integer. Give an effi cient algorithm to compute the maximum expected total pro fit subject to the given constraints. -- 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. -- 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. -- 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: XOR Rounds
Space complexity is O(N^2), but time complexity will be O(N^3 log K) - this is too slow. -- 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.
[algogeeks] Re: quick sort
There is a killer-case for the quicksort algorithm on which it runs in a quadratic time. However, before running sorting algorithm we can randomly shuffle the array, so time will be reduced to the expected. -- 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] Dynamic Programming
Right. It can be solved simply in O(n^2). To optimize use segment trees. -- 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] Dynamic Programming
Can you elaborate how to put segment tree into picture On Wed, Jan 5, 2011 at 2:57 PM, juver++ avpostni...@gmail.com wrote: Right. It can be solved simply in O(n^2). To optimize use segment trees. -- 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. -- 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] Dynamic Programming
dp[i] - profit from the opening restaurants up to the i-th position. dp[i] = max(dp[i - 1], p[i] + max[dp[j], j = A and distance between i and j at least k]). Segment trees are helpful to find maximum profir for the positions to th elft of the current. So we use tree of maximums. To satisfy the second property (distance at least k), for the current position you should determine position A, where m[i] - m[A] = k, this can be done using binary serach (lower_bound in C++). -- 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] Google Interview Question
dangling pointers ?? maybe.. also corrupted heap On Wed, Jan 5, 2011 at 4:46 PM, bittu shashank7andr...@gmail.com wrote: You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? -- 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. -- thanks --mac -- 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] Google Interview Question
Corrupted stack - buffer overflow. -- 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.
[algogeeks] Google Interview Question
You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. -- 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.
[algogeeks] Re: quick sort
using randomized version of quick sort time complexity even in the worst case is o(nlogn) Regards priyaranjan code-forum.blogspot.com On Jan 5, 12:55 pm, lee steath...@gmail.com wrote: how can we make quick sort to run in O(logn) time in worst case?? -- 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: quick sort
selecting pivot as a near median using order stastics method(O(n)) we can run it in worst case O(nlogn) -- 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] Find a specific number in a special matrix.
@MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. 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. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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] Find a specific number in a special matrix.
I think if x a[n/2][n/2] than we need to search in 1st quadrant otherwise in others. On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar sourabhjak...@gmail.comwrote: aditya solution is correct it is a standard question of young tabuleau it is complexity is log(n) On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR aditya...@gmail.com wrote: @MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. 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. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- 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. -- Cheers Naveen Kumar -- 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] Find a specific number in a special matrix.
@ankit thanks for correcting @naveen yeah that will make it more precise On Wed, Jan 5, 2011 at 7:51 PM, Ankit Babbar ankitbabba...@gmail.comwrote: @ Aditya: Mac's Solution works correctlyfor your example: Start from 24(top right)..245: go left;95: go left; 13: go down; 23:go down: 3 found..:) On Wed, Jan 5, 2011 at 7:37 PM, Naveen Kumar naveenkumarve...@gmail.comwrote: I think if x a[n/2][n/2] than we need to search in 1st quadrant otherwise in others. On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar sourabhjak...@gmail.comwrote: aditya solution is correct it is a standard question of young tabuleau it is complexity is log(n) On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR aditya...@gmail.comwrote: @MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.comwrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. 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. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- 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. -- Cheers Naveen Kumar -- 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. -- Regards, Ankit Babbar -- 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. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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] Google Interview Question
There might be some error in calculating the value of some variable(s) which might be used to retrieve elements in some arrays/maintaining stack/linked list or any other data structure that uses the value of that variable to retrieve information from memory. Carefully checking the values of variables that are used to allocate/deallocate or retrieve memory contents can be helpful. On Wed, Jan 5, 2011 at 5:07 PM, juver++ avpostni...@gmail.com wrote: Corrupted stack - buffer overflow. -- 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. -- Umer -- 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.
[algogeeks] error in code
Hi ,
i m getting error can u find the error in code for following problem??
We will use the following (standard) definitions from graph theory. Let V be
a nonempty and finite set, its elements being called vertices (or nodes).
Let E be a subset of the Cartesian product V×V, its elements being called
edges. Then G=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e1,...,en) be a sequence of
length nof edges
ei∈ E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then
p is called a path from vertex v1 to vertex vn+1 in G and we say that
vn+1is reachable from
v1, writing (v1→vn+1).
Here are some new definitions. A node v in a graph G=(V,E) is called a sink,
if for every node w in G that is reachable from v, v is also reachable from
w. The bottom of a graph is the subset of all nodes that are sinks, i.e.,
bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of
certain graphs.
Input Specification
The input contains several test cases, each of which corresponds to a
directed graph G. Each test case starts with an integer number v, denoting
the number of vertices of G=(V,E), where the vertices will be identified by
the integer numbers in the set V={1,...,v}. You may assume that 1=v=5000.
That is followed by a non-negative integer e and, thereafter, e pairs of
vertex identifiers v1,w1,...,ve,we with the meaning that (vi,wi)∈E. There
are no edges other than specified by these pairs. The last test case is
followed by a zero.
Output Specification
For each test case output the bottom of the specified graph on a single
line. To this end, print the numbers of all nodes that are sinks in sorted
order separated by a single space character. If the bottom is empty, print
an empty line.
Sample Input
3 3
1 3 2 3 3 1
2 1
1 2
0
Sample Output
1 3
2
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public int[][] matrix;
public int n;
public static void main(String args[]){
try{
BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
String s= br.readLine();
while(!s.trim().equals(0))
{
s= s.trim();
String [] dim = s.split([ ]+);
Main graph = new Main();
graph.n= Integer.parseInt(dim[0]);
int edgesCount = Integer.parseInt(dim[1]);
if(edgesCount ==0){
for(int i=0; igraph.n ; ++i)
System.out.print((i+1)+ );
System.out.print(\n);
s= br.readLine();
continue;
}
graph.matrix = new int[graph.n][graph.n];
for(int i=0; igraph.n ;++i){
for(int j=0; jgraph.n; ++j){
graph.matrix[i][j]=0;
}
}
s= br.readLine();
s= s.trim();
dim = s.split([ ]+);
int j=0;
while(jdim.length){
graph.matrix[Integer.parseInt(dim[j])-1][Integer.parseInt(dim[j+1])-1] = 1;
j+=2;
}
int n = graph.n;
int [][] temp = new int [graph.n][graph.n];
for(int i=0 ; igraph.n ;++i){
copy(graph.matrix,temp,graph.n);
graph.processGraph(temp,i);
}
for(int i=0; igraph.n ;++i){
for(j=0; jgraph.n; ++j){
if(graph.matrix[i][j]==1 ){
if(graph.matrix[j][i]==1)
;
else
break;
}
}
if(j==n){
System.out.print((i+1) + );
}
/*else
System.out.println(not founf + i);*/
}
System.out.print(\n);
s= br.readLine();
}
}
catch(Exception e ){
System.out.println(e);
}
}
public void processGraph(int [][] temp,int val){
boolean tmp ;
for(int i=0 ;in ;++i)
for(int j=0; jn ; j++){
tmp = (temp[i][j]==1) || ((temp[i][val]==1)
(temp[val][j]==1));
matrix[i][j] = tmp?1:0;
}
}
public static void copy(int[][] graph , int [][] tmp , int n){
for(int i=0 ; in;++i)
for(int j=0;jn;j++)
tmp[i][j] = graph[i][j];
}
}
--
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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
only 2 stacks, one of them (or both...) should provide functionality for retrieving minimum. -- 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.
[algogeeks] Re: Dynamic Programming
I think your solution will take O(n3) time , as it will require three loops . 1st for index i , 2nd for first max and 3rd for second max . Instead we should take : dp[i] = max(dp[j]) + p[i] , where ji and m[i] - m[j] k . Pls correct me if something is wrong . -- 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.
[algogeeks] Dynamic Programming - Series
We are given a checkerboard which has 4 rows and n columns, and has an integer written in each square. We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or vertically adjacent squares (diagonal adjacency is fine). (a) Determine the number of legal patterns that can occur in any column (in isolation, ignoring the pebbles in adjacent columns) and describe these patterns. Call two patterns compatible if they can be placed on adjacent columns to forma legal placement. Let us consider subproblems consisting of the first k columns 1 = k = n. Each subproblem can be assigned a type, which is the pattern occurring in the last column. (b) Using the notions of compatibility and type, give an O(n)-time dynamic programming algorithm for computing an optimal placement -- 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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Good point. Right. But we can avoid first stack of such structure, having separate variable (Minimum) for this. -- 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] Find a specific number in a special matrix.
Either x is greater or less than the middle vale you have to search 3 quardant. Because the value could be in bottom left or top tight. On Jan 5, 2011 7:14 AM, ADITYA KUMAR aditya...@gmail.com wrote: @ankit thanks for correcting @naveen yeah that will make it more precise On Wed, Jan 5, 2011 at 7:51 PM, Ankit Babbar ankitbabba...@gmail.com wrote: @ Aditya: Mac's Solution works correctlyfor your example: Start from 24(top right)..245: go left; 95: go left; 13: go down; 23:go down: 3 found..:) On Wed, Jan 5, 2011 at 7:37 PM, Naveen Kumar naveenkumarve...@gmail.com wrote: I think if x a[n/2][n/2] than we need to search in 1st quadrant otherwise in others. On Wed, Jan 5, 2011 at 7:20 PM, sourabh jakhar sourabhjak...@gmail.com wrote: aditya solution is correct it is a standard question of young tabuleau it is complexity is log(n) On Wed, Jan 5, 2011 at 6:52 PM, ADITYA KUMAR aditya...@gmail.com wrote: @MAC ur solution is wrong 1 9 24 2 12 33 3 16 49 search for 3 O(logn) solution let the matrix be A[][] and number to be searched is x divide the array from middle in 4 parts lets say it four quadrants now check if xA[n/2][n/2] search in bottom right quadrant if xA[n/2][n/2] search in other 3 quadrants On Sat, Dec 25, 2010 at 8:25 AM, yq Zhang zhangyunq...@gmail.com wrote: Suppose you have a matrix n*m. each column and row of the matrix is already sorted. For example: 1,2,3 2,3,4 4,5,6 All 3 rows and 3 columns of above matrix are sorted. How to find a specific number in the matrix? The trivial O(nlogm) solution is to use binary search for all rows. I am looking for better solution. 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers Naveen Kumar -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Ankit Babbar -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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. -- 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
Re: [algogeeks] Re: Dynamic Programming
int solve(int id) {
if(id==n)
return 0;
int d = dp[id];
if(~d) return d;
d = 0;
for(int i=id+1;in;i++) {
if(dis[i]-dis[id]=k) {
d ?= val[id] + solve(i);
}
}
return d;
}
Its O(n^2), and Juver++, is very correct.
On Wed, Jan 5, 2011 at 10:22 PM, Decipher ankurseth...@gmail.com wrote:
I think your solution will take O(n3) time , as it will require three
loops . 1st for index i , 2nd for first max and 3rd for second max .
Instead we should take :
dp[i] = max(dp[j]) + p[i] , where ji and m[i] - m[j] k . Pls
correct me if something is wrong .
--
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.
--
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.
[algogeeks] Re: Dynamic Programming
Unfortunately, you are wrong. We need one loop for i and that is all. All other things for searching max p[j] is solved by segment tree in O(log 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
I am telling the DP O(n^2) solution, whts wrong in it?? On Wed, Jan 5, 2011 at 10:36 PM, juver++ avpostni...@gmail.com wrote: Unfortunately, you are wrong. We need one loop for i and that is all. All other things for searching max p[j] is solved by segment tree in O(log 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. -- 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.
[algogeeks] Re: Find a specific number in a special matrix.
Other useful information about this structure is herehttp://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf . -- 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: Dynamic Programming
I was replying to the @Decipher post. Not yours. :) Your algorithm seems to be ok. -- 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: Dynamic Programming
ok :):) On Wed, Jan 5, 2011 at 10:43 PM, juver++ avpostni...@gmail.com wrote: I was replying to the @Decipher post. Not yours. :) Your algorithm seems to be ok. -- 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. -- 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: Dynamic Programming
Minor fixes: i loop should be from 0 to id - 1, if you are moving from left to right. initial value of d should be the val[id] not 0. -- 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: Dynamic Programming
Sorry, disregard my first proposition about index i. -- 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: Dynamic Programming
In main just pass answerIs = max(val[0], solve(0)); On Wed, Jan 5, 2011 at 10:49 PM, juver++ avpostni...@gmail.com wrote: Sorry, disregard my first proposition about index i. -- 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. -- 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: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
That's a big save of space! On Jan 5, 2011 9:03 AM, juver++ avpostni...@gmail.com wrote: Good point. Right. But we can avoid first stack of such structure, having separate variable (Minimum) for this. -- 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. -- 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.
[algogeeks] Re: Dynamic Programming - Series
In any column, we can place atmost 2 pebbles.
(a) Considering an isolated column, we can place 1 or 2 pebbles.
Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4}
(b) Have an array dp[n][5][5]. Let dp[i][j][k] store the maximum sum
that can be achieved starting from column 'i' to column 'n-1' (columns
are numbered 0 - (n-1)), where row 'j' and row 'k' of column 'i-1' are
chosen. If j=0 or k=0 (then no cell is chosen). (Rows are numbered 1 -
4).
Here is the C++ code:
#includeiostream
#includecstdio
#includestring.h
using namespace std;
#define MAXN 1000+5
int n;
int a[MAXN][5];
int dp[MAXN][5][5];
int go(int i,int j,int k){
//Without loss of generality, assume always j=k (we can
incorporate that in our code)
if(i==n)return 0;
int ans=dp[i][j][k];
if(ans!=-1)return ans;
ans=go(i+1,0,0);
for(int h=1;h=4;h++)if(h!=jh!=k)ans=max(ans,a[i][h]+go(i
+1,0,h));
if(j!=1k!=3)ans=max(ans,a[i][1]+a[i][3]+go(i+1,1,3));
if(j!=1k!=4)ans=max(ans,a[i][1]+a[i][4]+go(i+1,1,4));
if(j!=2k!=4)ans=max(ans,a[i][2]+a[i][4]+go(i+1,2,4));
return ans;
}
int main(){
scanf(%d,n);
//Set 'dp' array to -1 initially
memset(dp,-1,sizeof(dp));
for(int i=0;in;i++)for(int j=1;j=4;j++) scanf(%d,a[i][j]);
int ans=go(0,0,0);//maximum value
printf(%d\n,ans);
return 0;
}
On Jan 5, 10:00 pm, Decipher ankurseth...@gmail.com wrote:
We are given a checkerboard which has 4 rows and n columns, and has an
integer written in each square. We are also given a set of 2n pebbles,
and we want to place some or all of these on the checkerboard (each
pebble can be placed on exactly one square) so as to maximize the sum
of the integers in the squares that are covered by pebbles. There is
one constraint: for a placement of pebbles to be legal, no two of them
can be on horizontally or vertically adjacent squares (diagonal
adjacency is fine).
(a) Determine the number of legal patterns that can occur in any
column (in isolation, ignoring the pebbles in adjacent columns) and
describe these patterns.
Call two patterns compatible if they can be placed on adjacent columns
to forma legal placement. Let us consider subproblems consisting of
the first k columns 1 = k = n. Each subproblem can be assigned a
type, which is the pattern occurring in the last column.
(b) Using the notions of compatibility and type, give an O(n)-time
dynamic programming algorithm for computing an optimal placement
--
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] quick sort
This is correct. It ensures there can be no degenerate partitions and improves the worse case run time to be asymptotically equal to the average case. In practice you would want to use a simple pivot selection algorithm and only resort to SELECT when the simple algorithm fails to produce a partition within a fixed fraction of 50/50. -- 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.
[algogeeks] Re: Dynamic Programming
Thanks everyone for suggestions and follow my Dynamic Programming - Series for more questions on DP . -- 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.
