@Nishaanth
T1 has millions of nodes. Suppose all the nodes of T1 are equal to root of
T2. Then u will have to check every where in T1. Putting height as
constraint, u will have to check only those nodes whose height is equal to
T2. It will reduce time complexity.
Well m not able to think of
@priya...ya thats wat i meant by interleaving of operations(non-atomic
operations). you can understand the results if you can trace the register
values.
On Sat, Jan 8, 2011 at 10:18 PM, Priyanka Chatterjee dona.1...@gmail.comwrote:
@harshal, sundi: Use some compiler to check, i checked on gcc ,
someone - going by the exact words of the problem description.
Just see all the 8 possible winning combinations(row,column, 2
diagonals)...if anyone combination is filled by the same player..then there
is a winner.
I know it sounds trivial, correct me if i am wrong.
On Sat, Jan 8, 2011 at 11:16
In essence what you say boils down to DFS , isnt it ?
On Sat, Jan 8, 2011 at 10:15 PM, Algoose chase harishp...@gmail.com wrote:
Will this work ?
Find the node x, then the node y within the sub tree rooted at x and then z
within the sub tree rooted at y since they must within a unique path
hi all,
Is there a way to find a formula for the nth element of a linear recurrence
? Instead of going linearly one by one
c1, c2, c3 are the three constants.
a(n+3) = c1*a(n+2) - c2*a(n+1) + c3*a(n)
thanks.
shady
--
You received this message because you are subscribed to the Google
And what else? List doesn't represent the original tree structure.
--
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
There are 4 kids). So 1, 2, 3 are connected into a circle. There is no place
for the remaining 4-th)
--
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
yes,u can use matrix exponentiation
On Sun, Jan 9, 2011 at 3:49 PM, shady sinv...@gmail.com wrote:
hi all,
Is there a way to find a formula for the nth element of a linear recurrence
? Instead of going linearly one by one
c1, c2, c3 are the three constants.
a(n+3) = c1*a(n+2) -
You may find this http://en.wikipedia.org/wiki/Binary_tree#Encodings
useful.
--
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
And this: http://www.cs.usfca.edu/~galles/cs245/lecture/lecture9.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
Your approach is failed! Read my previous post.
There is a simple counterexample when doing dfs from x we cannot reach
target node cause z can be placeed into another subtree, so
x is not its ancestor.
--
You received this message because you are subscribed to the Google Groups
Algorithm
There is very useful technique for this kind of problem.
A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3).
Let's introduce matrix B:
C1 -C2 C3
100
010.
A(n-1) A(n)
B x A(n-2) = A(n-1)
A(n-3) A(n-2)
and so on..
So to find A(n) you should muultiply
What do you mean by N term? Is it a size of the matrix N*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
You are wrong, this doesn't depend on the order which is used by printf.
In C/C++ order of evaluating function's parameters is undefined.
So you may receive different results in different compilers.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
@lalit
hi its because whenever we talk about multi-threading we
need to take care of synchronization as the problem clearly says
application made only single threaded means not synchronized
otherwise as a programmer its his job to make a app..for multithreaded
environment so that such problem
I am not familiar with such techniques, can you please refer to some article
where such techniques are explained, ...
Regards,
Shady
On Sun, Jan 9, 2011 at 5:44 PM, juver++ avpostni...@gmail.com wrote:
There is very useful technique for this kind of problem.
A(n) = C1 * A(n-1) - C2 * A(n-2)
You find this so useful
http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html
On Sun, Jan 9, 2011 at 6:10 PM, shady sinv...@gmail.com wrote:
I am not familiar with such techniques, can you please refer to some article
where such techniques are explained, ...
Regards,
Shady
On
Convert in O(n) time and O(1) space :
a1,a2,a3,a4,.aN,b1,b2,b3,b4,.,bN to
a1,b2,a2,b2,a3,b3,a4,b4,..aN,bN.
--
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
i think its DP Problemstill thinking on the soultion..
@ankur..ur approach nearly matches to mine..what i thought..but we
need actual solution..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
somebody might enlighten for 3rd year as well (INDIA)
On Sun, Jan 9, 2011 at 6:53 PM, abhishesh srivastava
abhishesh.srivast...@gmail.com wrote:
Can anyone please tell me about the summer internship programs of various
institute.
I want to know how to register and about various summer
No its a single array . You have to convert first array into second in
O(n) time and O(1) space .
--
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,
Post your resume on some Job search website or try LinkedIn(Job search
option) . In the search engine (of that website) put trainee or
software trainee . You might find some useful result there . Or google
search internship .
--
You received this message because you are subscribed to the Google
so if its in another subtree, whats the problem?
If z is not reachable print 'no'.
On Sun, Jan 9, 2011 at 5:32 PM, juver++ avpostni...@gmail.com wrote:
Your approach is failed! Read my previous post.
There is a simple counterexample when doing dfs from x we cannot reach
target node cause z
It doesn't matter how to make transitions: from current position make all
necessary moves,
or determine all positions from which we can achieve i-th position.
So your method is only the one of possible.
--
You received this message because you are subscribed to the Google Groups
Algorithm
x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1
cannot be reached while DFS from node 2
https://lh3.googleusercontent.com/_qdJSDBXyZKE/TSi5XyCrEzI/ARg/PB7anNiPA2c/graph.png
--
You received this message because you are subscribed to the Google Groups
#includestdio.h
int main()
{
int i=2;
for(printf(cat );printf(rat )i--;printf(mat ))
{
printf(bat );
}
}
ouput : cat rat bat mat rat bat mat rat
can anybody plz explain how we get this output??
--
Regards,
$iva
--
You received this message because you are subscribed to the
This is simple.
cat - initilization step of for loop
rat - first loops's if passed, so i == 1 now
bat - loop's body
mat - loop's post operations
rat - second loop's if passed, i == 0 now
bat - loop's body
mat - loop's post operations
rat - thirrd calculation of the loop statement, first term
the printf function returns 1 when it prints a string..
for (1;1i--;1)
{
printf(bat);
}
note that i=2 has been cunningly initialized before. and the decrement of i
has been done in middle expression of the for loop
hence, actually its like
for(;i--;)
{
}
how many times will this execute?
For each row, column and both diagonals keep track amount of equal marks.
Update these counts in O(1) when player makes move.
To determine winner, iterater over each column, row and diagonals to check
whether there is N equal marks.
--
You received this message because you are subscribed to the
please describe the tree...give an elaborate explanation to your input
On Sun, Jan 9, 2011 at 8:02 PM, juver++ avpostni...@gmail.com wrote:
x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1
cannot be reached while DFS from node 2
I have solved the last one :)
how can i solve this one:
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4805
using LCA, I used this algorithm:
http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor
but i dont know how to count the weights of the edges.
I
See at the image. It is enough to see tre structure of the tree.
--
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
Run dfs/bfs from the root (node 0). Store distance from the root to each
node at the node's data.
Then the final path's weight between i and j is: dist[i] + dist[j] -
dist[lca(i, j)].
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
thanks that was a very nice tutorial.
but i am still stuck with
S(n,3) = A(n+3) = 6*A(n+2) - 11*A(n+1) + 6*A(n) --- 1
S(n+1,4)=S(n,3)+4*S(n,4) 2nd stirling number
3*S(n+1,4) = 0, 0, 3, 30, 195, 1050, 5103, 23310
what will be the matrix for the
Use a linked list (maintain both head and tail positions) and treat it
as a queue insert/delete front or back... whatever...
For each insert, see if it's less than the current min and maintain
min... If you're deleting the current min, you may traverse from head
to tail and recompute the
knapsack typically tries to maximize one attribute while minimizing
some other (or optimal max for both or similar such conditions)... for
this problem, all we need to do is find one subset that adds up to the
given number... there's no second criteria to maximize/minimize...
Please correct me if
All operations should constant at least on average.
So your idea is not suitable.
--
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
As I've stated, problem is similar to the 0-1 knapsack.
Find subset of elements which sums up to a given value.
Possible transitions - to take or not to take particular element.
That's why it's 0-1 knspsack.
--
You received this message because you are subscribed to the Google Groups
Algorithm
Start from the root and do a breadth first traversal until you hit x
or Z...
Once you have x or Z, treat that node as root and traverse breadth
first on that sub-tree till you reach the other node (i.e, if you hit
X first, see if you can reach Z from X)... At the same time, if you
encounter Y
Start from the root and do a breadth first traversal until you hit x
or Z...
Once you have x or Z, treat that node as root and traverse breadth
first till you reach the other node (if you hit X first, see if you
can reach Z from X)... At the same time, if you encounter Y during the
sub-tree
why's the linked list option not constant (at least for most cases)?
the time's not constant only for delete operation (that too only if
you delete the current min)... otherwise, everything is a O(1)
operation...
get_min() already has the min...
push_rear(), pop_front() - you're maintaining the
Hey guys .. saw this discussion and wanted to add something .. I wrote the
below program in college .. and I kindof have forgotten wat was the logic
(see the problem with badly written code :P ), It works on a pattern which I
found in this problem, I checked it and feel it works in order O(n) as
When you remove element from the front of queue, you should update min value
for all remaining nodes.
So it's linear.
--
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
Sorry for the confusion,
Given series : http://oeis.org/A032263/list
How to get the nth number of the series in O(log(n)) ?
Regards,
Shady
On Mon, Jan 10, 2011 at 12:36 AM, shady sinv...@gmail.com wrote:
thanks that was a very nice tutorial.
but i am still stuck with
S(n,3) = A(n+3) =
It can be done in O(n) time and O(1) space.
Logic:
1. Start at i = 0.
2. Take first half of the array and exchange elements at i=2 to n/2
with n/2+1
3. n = n/2, start = n/2+1
4. Repeat steps 2 and 3 until n becomes 0.
On Jan 9, 7:41 am, Decipher ankurseth...@gmail.com wrote:
No its a single
About Me:
Currently work as SDE in Microsoft . Constant participant in programming
contest around the world Handle : FameofLight. Successfully conducted many
programming contest in college , including Alkhwarizm [ First Indian Contest
to Publish a Editorial : I should take credit for this , as
@Juver++
I am not sure if your input represents a path as asked in the problem.
We typically think of a path within a binary tree as a downward path(from
root to a leaf) thats not spread across different branches.
Of course, if you consider that example as a valid case, then DFS wont work
!
On
@juver and prateekthanks a lot for the detailed and nice
explanation :)
On Jan 9, 8:03 pm, juver++ avpostni...@gmail.com wrote:
This is simple.
cat - initilization step of for loop
rat - first loops's if passed, so i == 1 now
bat - loop's body
mat - loop's post operations
rat - second
Thanks, i finished it. :)
it wasdist[i] + dist[j] - 2*dist[lca(i, j)]
this problem is difficult :(
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4809
I dont have idea how to solve it.
--
You received this message because you are subscribed to the Google Groups
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9,
Then it is O(n) worst case. While juver's algo is amortized constant time in
worst case.
On Jan 9, 2011 10:26 PM, SVIX saivivekh.swaminat...@gmail.com wrote:
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
52 matches
Mail list logo
