Re: [algogeeks] Re: Finding Blocks in a matrix
@ akash solution is complete. :P first try to understand the solution. -- 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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@anshuman sir: yes, I know you have completed the solution. I have just added :) On Sun, May 29, 2011 at 11:02 PM, anshu mishra anshumishra6...@gmail.comwrote: @ akash solution is complete. :P first try to understand the solution. -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: Finding Blocks in a matrix
@Anshu
If you do
add top bottom, left right element to the popped element in qeuue
should you need to do it for each element in the matrix.
So, will that not be O(n3)??
Clarify if i am wrong.
On May 30, 9:52 am, Aakash Johari aakashj@gmail.com wrote:
At the each level, traversed by BFS, you will have to check whether the
vertex in this level has the element same as it found in the previous level.
If it is different, then count it.
On Sun, May 29, 2011 at 10:43 PM, anshu mishra
anshumishra6...@gmail.comwrote:
@piyush
void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and their
value is equal to x and mark their flag false;
}
}
--
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.
--
-Aakash Johari
(IIIT Allahabad)
--
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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@ross : * if their flag is true and their value is equal to x*
On Sun, May 29, 2011 at 11:07 PM, ross jagadish1...@gmail.com wrote:
@Anshu
If you do
add top bottom, left right element to the popped element in qeuue
should you need to do it for each element in the matrix.
So, will that not be O(n3)??
Clarify if i am wrong.
On May 30, 9:52 am, Aakash Johari aakashj@gmail.com wrote:
At the each level, traversed by BFS, you will have to check whether the
vertex in this level has the element same as it found in the previous
level.
If it is different, then count it.
On Sun, May 29, 2011 at 10:43 PM, anshu mishra
anshumishra6...@gmail.comwrote:
@piyush
void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and
their
value is equal to x and mark their flag false;
}
}
--
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.
--
-Aakash Johari
(IIIT Allahabad)
--
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.
--
-Aakash Johari
(IIIT Allahabad)
--
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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@ross no, a particular element has to read only 5 times maximum. 1 reading (i,j) (if its flag is already false skip) 2 read by top element 3. read by bottom element 4 read by left element 5 read by right element coz atleast one of the this operation its flag will be unset(false), then we have to just skip it. -- 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: Finding Blocks in a matrix
@anshu mishra:
Hi, kindly clarify on this small doubt of mine.
Your algo is
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already adjacent to x value = x)
add to queue
}
For the graph,
1 1 2
1 3 1
2 3 4
first,
queue = 1 (at 0,0)
then you would add the 2 1s at (0,1) and (1,0) to the queue.
So far, i can understand.
now, if you start to pop elements, you ll see that there s no element
with
*equal value as 1* adjacent to the popped elements and the queue
would be
empty.
. How does the algo proceed from here and keep track of count?
.
On May 30, 10:22 am, anshu mishra anshumishra6...@gmail.com wrote:
@ross no, a particular element has to read only 5 times maximum.
1 reading (i,j) (if its flag is already false skip)
2 read by top element
3. read by bottom element
4 read by left element
5 read by right element
coz atleast one of the this operation its flag will be unset(false), then we
have to just skip it.
--
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.
Re: [algogeeks] Re: Finding Blocks in a matrix
main()
{
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}
}
}
bfs(mat[][], flag[][], i, j)
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already adjacent to x value = x)
add to queue
}
}
this is thw whole code
--
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: Finding Blocks in a matrix
@anshu mithra:
Hi,
Thanks for clarifying! :)
On May 30, 11:06 am, anshu mishra anshumishra6...@gmail.com wrote:
main()
{
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}}
}
bfs(mat[][], flag[][], i, j)
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already adjacent to x value = x)
add to queue
}
}
this is thw whole code
--
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: Finding Blocks in a matrix
@vishal Hi, I do not get you. Can you please elaborate a little more how you ll use hash? On May 30, 8:50 am, Vishal Thanki vishaltha...@gmail.com wrote: what about using a hash function? On Mon, May 30, 2011 at 10:18 AM, ross jagadish1...@gmail.com wrote: Given a matrix, you need to find the number of blocks in it. A block has the same numbers. EG: 1 1 3 1 2 3 2 2 4 has 4 blocks namely, 1 1 1 2 2 2 3 3 4 1 2 3 4 5 6 7 8 9 has 9 blocks 1 1 1 1 1 3 4 4 5 has 4 blocks, 1 1 1 1 1 3 5 4 4 I used an algorithm as follows, for each element[i,j] in the matrix, enqueue adjacent indices into a queue if they contain the same element. else incremt blockcount; return blockcount; But, this complexity is O(n^3) any better solution exists? -- 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 athttp://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 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.
Re: [algogeeks] Re: Finding Blocks in a matrix
Okay, i thought it this way: iterate through the whole matrix, and take the value as a key to a hash table. and the value corresponding to the key would be the count. increment the count everytime you encounter the same key. it is very easy to implement this in python (using dictionary) but i am not sure what will be the most efficient data structure to implement this in c/c++. Vishal On Mon, May 30, 2011 at 10:31 AM, ross jagadish1...@gmail.com wrote: @vishal Hi, I do not get you. Can you please elaborate a little more how you ll use hash? On May 30, 8:50 am, Vishal Thanki vishaltha...@gmail.com wrote: what about using a hash function? On Mon, May 30, 2011 at 10:18 AM, ross jagadish1...@gmail.com wrote: Given a matrix, you need to find the number of blocks in it. A block has the same numbers. EG: 1 1 3 1 2 3 2 2 4 has 4 blocks namely, 1 1 1 2 2 2 3 3 4 1 2 3 4 5 6 7 8 9 has 9 blocks 1 1 1 1 1 3 4 4 5 has 4 blocks, 1 1 1 1 1 3 5 4 4 I used an algorithm as follows, for each element[i,j] in the matrix, enqueue adjacent indices into a queue if they contain the same element. else incremt blockcount; return blockcount; But, this complexity is O(n^3) any better solution exists? -- 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 athttp://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 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. -- 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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@ross... I have adoubt regarding this question... what should be output if the matrix is like this.. 1 1 2 1 3 1 2 3 4 U reply I will tell you then what doubt I have. On Mon, May 30, 2011 at 10:36 AM, Vishal Thanki vishaltha...@gmail.comwrote: Okay, i thought it this way: iterate through the whole matrix, and take the value as a key to a hash table. and the value corresponding to the key would be the count. increment the count everytime you encounter the same key. it is very easy to implement this in python (using dictionary) but i am not sure what will be the most efficient data structure to implement this in c/c++. Vishal On Mon, May 30, 2011 at 10:31 AM, ross jagadish1...@gmail.com wrote: @vishal Hi, I do not get you. Can you please elaborate a little more how you ll use hash? On May 30, 8:50 am, Vishal Thanki vishaltha...@gmail.com wrote: what about using a hash function? On Mon, May 30, 2011 at 10:18 AM, ross jagadish1...@gmail.com wrote: Given a matrix, you need to find the number of blocks in it. A block has the same numbers. EG: 1 1 3 1 2 3 2 2 4 has 4 blocks namely, 1 1 1 2 2 2 3 3 4 1 2 3 4 5 6 7 8 9 has 9 blocks 1 1 1 1 1 3 4 4 5 has 4 blocks, 1 1 1 1 1 3 5 4 4 I used an algorithm as follows, for each element[i,j] in the matrix, enqueue adjacent indices into a queue if they contain the same element. else incremt blockcount; return blockcount; But, this complexity is O(n^3) any better solution exists? -- 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 athttp:// 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 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. -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * @ross -- 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.
Re: [algogeeks] Re: Finding Blocks in a matrix
it is a simple graph problem. travese the whole matrix using BFS. it will be
O(n^2).
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}
}
--
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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@vishal ur sol wil give wrong answer for this 1 1 2 1 3 1 2 3 4 answer should be 6 but ur sol wil give 4. -- 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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@anshucan u plz elaborate ur solution for a particular case?? On Mon, May 30, 2011 at 10:49 AM, anshu mishra anshumishra6...@gmail.comwrote: @vishal ur sol wil give wrong answer for this 1 1 2 1 3 1 2 3 4 answer should be 6 but ur sol wil give 4. -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@anshu, i got you. my bad!! On Mon, May 30, 2011 at 10:49 AM, anshu mishra anshumishra6...@gmail.com wrote: @vishal ur sol wil give wrong answer for this 1 1 2 1 3 1 2 3 4 answer should be 6 but ur sol wil give 4. -- 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. -- 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.
Re: [algogeeks] Re: Finding Blocks in a matrix
@piyush
void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and their
value is equal to x and mark their flag false;
}
}
--
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.
Re: [algogeeks] Re: Finding Blocks in a matrix
At the each level, traversed by BFS, you will have to check whether the
vertex in this level has the element same as it found in the previous level.
If it is different, then count it.
On Sun, May 29, 2011 at 10:43 PM, anshu mishra anshumishra6...@gmail.comwrote:
@piyush
void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and their
value is equal to x and mark their flag false;
}
}
--
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.
--
-Aakash Johari
(IIIT Allahabad)
--
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.
