Re: [algogeeks] Re: Algo for Search in a 2D Matrix

@Anshu pushing adjacent element will cause duplicate entries in the heap try the following example: 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 so we also need to maintain a data structure that can efficiently tell that which cell has been pushed into the heap already. On Thu, Oct 1

Re: [algogeeks] Re: Algo for Search in a 2D Matrix

push the two adjacent element that is one right and below -- 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...@go

Re: [algogeeks] Re: Algo for Search in a 2D Matrix

If O(k*logk) solution is acceptable then it is very simple. maintain a min heap. push a[0][0], i = 0; while ( i < k) { pop an element. ---> O(log(i)) --> coz number of elements in heap is i; push the two adjacent element that is one right and right below. ---> O(log(i)); i++; } last element popped

[algogeeks] Re: remove duplicate words from a string

@Ankur In a trie u first insert the first word ..take the second word..If its not present in the trie u insert it else remove it from original string: removing the word requires left shifting the entire string Alternatively u store the elements in a trie in the initial string and terminate it with

Re: [algogeeks] Re: Find the later version

scan the numbers as string if both strings dont have equal numbers of dots then add trailing 0's with dots to the string with less number of dots now divide both the string into 2 equal halves compare the left half .if unequal then divide recursively and again compare left of the divided s

Re: [algogeeks] Stone Game

your solution seems to be the right one... testcases may be faulty try submitting here both the codes On Thu, Oct 13, 2011 at 5:44 AM, Hatta wrote: > being accepted doesn't imply in being correct > maybe I'm wrong but given this Test Case I think BOB

Re: [algogeeks] Stone Game

being accepted doesn't imply in being correct maybe I'm wrong but given this Test Case I think BOB wins: 3 1 3 2 didn't he (bob!)? On Wed, Oct 12, 2011 at 6:53 PM, Wladimir Tavares wrote: > In the problem Stone Game , I did the following algorithm that was accepted > by spoj: > > #include > i

[algogeeks] Stone Game

In the problem Stone Game , I did the following algorithm that was accepted by spoj: #include int main(){ int n,t,i,j,cont; scanf("%d",&t); while(t--){ scanf("%d",&n); cont=0; for(i=1;i<=n;i++) { scanf("%d",&j); if(j>=i){

[algogeeks] Re: Memorization

This is true when memoization is being used to merely improve asymptotic efficiency of a single computation. (As you say, it's a nice technique for DP, when you can often just remember one or a few previous rows of results.) However this is not the only use. General memoization maintains values p

[algogeeks] Re: Find the later version

it is expected that the version is given as string, in that case, atoi() has be used to convert string to int. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeek

[algogeeks] Re: How to Solve This

First note: 0 * 3 = 0 7 * 3 = 21 4 * 3 = 12 1 * 3 = 3 8 * 3 = 24 5 * 3 = 15 2 * 3 = 6 9 * 3 = 27 6 * 3 = 18 3 * 3 = 9 Important is that the final digits of each line count 0 to 9. Now you can build an answer right to left. Example: 123. Check the table to get the rightmost 1. 7 * 123 = 861 N

[algogeeks] Re: Find the later version

As others have said, you have not completely specified the problem. If you always have exactly 4 base 10 numbers separated by dots, and you are working in C or C++ then you can use sscanf to get the numbers and compare them: // Return: // positive if version s1 is an earlier version than s2, //

[algogeeks] Re: How to Solve This

well , I tried to solve it from Maths though half way through only :( N = number required i.e. (10^k -1)/9 given n = 10x + 3 by eq (10x + 3) * m = N= (10^k - 1)/9 implies k = 2log 3 + log m + log(10x + 3) i.e. k > 1 + log n This gives the lowerbound on minimum number of 1 to be start with, b

Re: [algogeeks] Re: Algo for Search in a 2D Matrix

Here is a solution based on the fact that the matrix is quiet similar to a min heap. each cell is smaller than its down and right neighbor. Note :- This solution modifies the original matrix. Algo - repeat k-1 times set a[0][0] = INFINITY minHeapify the Matrix (see implementat

Re: [algogeeks] Re: Algo for Search in a 2D Matrix

i dont think k*k submatrix approach works at all what if k >=n size of submatrix will be n*n, which is matrix itself heap seems to be a good approach with a coloring scheme that helps in avoiding duplicates in heap ?? On Wed, Oct 12, 2011 at 7:18 PM, vikas wrote: > @Shiva, not necessarily in upp

[algogeeks] Re: Algo for Search in a 2D Matrix

@Shiva, not necessarily in upper half take the transpose of example put by Dave and see by yourself There are few observations for this question: 1. kth smallest will always lie in first k*k matrix 2. it wont be part of sqrt(k)*sqrt(k) matrix Thus rest all need to be searched recursivel

Re: [algogeeks] Re: Find the later version

WE CAN USE RADIX SORT TO FIND THE MAX VERSION :TRAVERSING FROM LEFT TO RIGHT (RADIX WILL BE NUMBERS BETWEEN THE POINTS). It will reduce the search space too. On Tue, Oct 11, 2011 at 1:58 AM, sumit kumar pathak wrote: > * > *regards > - Sumit Kumar Pathak > (Sumit/ Pathak/ SKP ...) > *Smile is on

Re: [algogeeks] How to Solve This

@amol I was not sure that for every number that has 3 in its unit place has one multiple which has all one. So I used that is if the remainder is coming that already appeared stop there coz it will make stuck in a loop. for ex. remainders are 1 3 19 23 37 1 3 19 that will repeat. but it in th

Re: [algogeeks] How to Solve This

@anshu- your code works fine.but can you plz explain how you concluded this codei mean what's the logic behind to check myset.size() > psize ?? ...as you are assuming that it will be increase string and check until this condition satisfies ?? -- Amol Sharma Third Year Student C