actually there are infinite number of sequences that match it
for example if the absolute differences are 3 2 5 1
one possible sequence is 6 3 5 0 1 one other is 7 4 6 1 2 or 8 5 7 2 3
and you can add any integer value to all elements and the result will still
be valid
actually you can start with
1 is not a prime number!
On Mon, Oct 31, 2011 at 4:07 PM, mc2 . qlearn...@gmail.com wrote:
Hey guys ,
I am trying to solve this DP problem :
http://community.topcoder.com/stat?c=problem_statementpm=10033rd=13513
SRM 422, DIV 2 ,level 2.
Here is my DP solution. But it is not working.
in the
matrix. Let Delta be the difference between maximum and minimum.
2- For each row, find the minimum and maximum entries in that row. If
their difference is exactly Delta, then print that row.
Amir
On Mon, Aug 15, 2011 at 12:00 AM, Karthikeyan palani
karthikeyan...@gmail.com wrote
to find the min/max value
in the matrix.
On 08/14/2011 12:20 PM, shady wrote:
no it is 3*n only read it again
On Mon, Aug 15, 2011 at 12:45 AM, Amir Aavaniamir.aav...@gmail.com wrote:
On 08/14/2011 11:46 AM, aditya kumar wrote:
it can be done in O(3n). in worst case one row will have
Both Will take same time.
--
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/algogeeks/-/hwcTUmMW_zsJ.
To post to this group, send email to algogeeks@googlegroups.com.
*// Using friend functions to overload addition and subtarction operators*
#include iostream.h
class myclass
{
int a;
int b;
public:
myclass(){}
myclass(int x,int y){a=x;b=y;}
void show()
{
coutaendlbendl;
}
*// these are friend operator functions
// NOTE: Both the operans will be be passed
In Amazon First Round all about Linux and Open Source Commands and Usage...
--
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/algogeeks/-/su20uc4k8ZcJ.
To post to this
They Gave me a sheet and asked me to write the commands u know
Then they asked the commands which weren't mentioned by me..like dostounix,
sed with regex with backreference,etc etc
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view
+ End)/ 2):
Lets j be the position of arr [i] in B'
Set Low_Array [i]= Low_Array [i]+ j
The running time of this algorithm is:
n\log n for sorting B+
T(n)= 2T(n/2)+ n\log n = T(n)= n\log^2 n
So, the total running time is: n\log^2 n .
Amir
On 07/26/2011 06:48 AM, Piyush
@venkatesan : im not sure about that! this problem is different
but we can do it in O(n^2)
the DP1 can be built done in O(n^2) as in abhijith's solution
also the DP2 can be built in O(n^2) too. instead of counting the min # of
palindrome strings that can make the range of [low,high]
count how
i think we can do this if the last move is given and that we have processed
the previous moves before, so only O(n) time is required if the last move's
column row or diagonal is filled or not
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
sort jewelries in decreasing order and then the problem can be solved in a
way similar to subset sum problem
On Mon, Dec 13, 2010 at 7:40 PM, Akash Agrawal akash.agrawa...@gmail.comwrote:
You have been given a list of jewelry items that must be split amongst two
people: Frank and Bob. Frank
@aditya: the problem you mentioned is not like this one
if i'm a green eyed there is no reason to kill myself on the second day if
no one kills himself on the 1st day
actually in your solution there is no difference between blue eyed people
and green eyed people so a blue eyed might kill himself
complexity is n^2 . i am not sure how
to compare that
On Tue, Dec 14, 2010 at 11:41 PM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
we can use DP to solve this:
dp[i][j] = coins[i][j] + max ( dp[i-1][j] , dp[i][j-1] )
On Tue, Dec 14, 2010 at 7:24 PM, divya sweetdivya
with an O(nm) preprocessing the queries will take O(1)
for each cell x,y find sum[x,y] which is sum of all elements in rectangle
with coordinates (0,0) (x,y) . this can be done in O(nm) (using
inclusion-exclusion principle) sum[x,y] = a[x,y] + sum[x-1,y] + sum[x,y-1] -
sum[x-1,y-1]
now for each
the result is nth catalan number
http://en.wikipedia.org/wiki/Catalan_number
--
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
we can use DP to solve this:
dp[i][j] = coins[i][j] + max ( dp[i-1][j] , dp[i][j-1] )
On Tue, Dec 14, 2010 at 7:24 PM, divya sweetdivya@gmail.com wrote:
A table composed of N x M cells, each having a certain quantity of
coins. You start from the upper-left corner. At each step you can go
2812.5
On Tue, Dec 14, 2010 at 10:36 PM, bittu shashank7andr...@gmail.com wrote:
void foo1()
{
if(AB)
Then {_/* */}
else
if(CD)
then foo2()
}
How many time foo2() would get called given
AB 25% of the times and CD 75% of the times and foo1() is called
5000 times
since you have M small strings using KMP or RabinKarp will take time O(mn)
but with suffix tree you can do it in O(n+m)
read these and you'll be able to construct one:
http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm
--
You
use segment tree
http://en.wikipedia.org/wiki/Segment_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
use suffix tree it's much faster than simple trie
with ukkonen's method you can build it in O(size of document) and then
searching in it is practically O(1)
http://en.wikipedia.org/wiki/Suffix_tree
http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
On Fri, Dec 10, 2010 at 7:54 PM, ADITYA
;
for (i=0;in;i++){
sum+=C[i];
if (aux[sum]==-1)
aux[sum]=i+1;
else
result=max(result,i+1-aux[sum]);
}
return result;
On Sat, Dec 11, 2010 at 3:30 PM, ADITYA KUMAR aditya...@gmail.com wrote:
@amir can u explain a bit more...
On Tue, Dec 7, 2010 at 10:09 PM
@jai : since sum of all values in C is between -n and n the last step can be
done in O(n) time and O(n) space
On Sun, Dec 5, 2010 at 12:44 PM, jai gupta sayhelloto...@gmail.com wrote:
@fenghuang: the last step will take O(n logn ) . Or there is some better
way?
--
You received this message
actually a greedy approach for this problem exists:
just convert the first row and first column to all zeros
if after this step matrix is not a complete zero matrix then it's impossible
to make it
On Sun, Dec 5, 2010 at 9:10 AM, Prims topcode...@gmail.com wrote:
How do i convert a binary
array:4,5,1,2,3
index: 0,1,2,3,4
real index: 3,4,0,1,2
suppose the index of the least element is k (here k=2)
then when you're applying the binary search the only modification you need
to have is each time you're going to access the ith element of array look at
(i+k)%n th element
@ankur: dp[i][j] number of (prefix) strings that have i As and j Bs is:
dp[i-1][j] number of (prefix) strings that have i-1 As and j Bs appended by
A
+
dp[i][j-1] number of (prefix) strings that have i As and j-1 Bs appended by
B
@ashish: wikipedia has some nice proofs for catalan number
we can use a binary search to search for the bit in O(logn)
the search would look like this:
we first compute
n 0x (which is 16 1s and 16 0s)
if the result is 0 then the left most 1 is in the 16 less significant bits
else it is in the 16 more significant bits
then we can continue this way
take a look at this:
www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
--
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
this can be done in O(n) time and O(n) space:
let count = the number of 1s seen so far - the number of 0s seen so far
so for each element if it is 1 then count++ and if it is 0 count-- (count is
0 at first )
make a map m[] such that m[i] is null if count was never equal to i else it
is the index
@ashish: AAA is the prefix of the string and it is valid as a prefix and
it's only used for strings with length = 6 (where it is a valid prefix)
actually only dp[i][j] where i==j counts the number of such strings and
otherwise there is no string where i!=j and it that case dp[i][j] counts the
convert all numbers to base n since every number is between 1 and n^2 every
number would have 2 digits
this can be done in O(n) since for each number we need only one division
so we have n numbers with 2 digits each digit between 0 and n-1
using radix sort this array can be sorted in O(n)
--
You
make a balanced bst which also has the size of subtree at each node
start from ar[n-1] and insert each element and see what is it's rank in BST
for finding the rank when inserting each time you pick the right subtree add
size of left subtree to rank
O(nlogn)
--
You received this message because
this has been discussed before :* *lexicographically next string
--
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
oops! sorry Gene i didn't see your first post when i was writing that!
--
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
@Anand: it depends on how you think of i
i thought of it as the starting digit of a group but you're thinking of it
as it's last
however both views are correct here since you're talking about my solution
minus 2!
you need to initialize the dp to 0 (and a bit change in IFs so that you
don't refer
@ashish: ankur's solution is not O(n^2)
in the worst case it would take O(n log(max(a)) ) since it goes one pass for
each bit and if a[i] is guaranteed to be a 32 bit integer we can argue that
it is O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm
@jalaj: sorry for delay i was busy these days
the implementation of my method is a bit hard because R2 and R4 which i
mentioned before are not always squares
and in that case we must first break the rectangles into squares and then
perform the search on squares
here breakToSquares function breaks
dp[i][j] is the number of strings that have i As and j Bs
dp[0][0]=1; // s=
for (i=1;i=n/2;i++)
dp[i][0]=1; // s=AAA...
for (i=1;i=n/2;i++)
dp[0][i]=0; // the 2nd constraint
for (i=1;i=n/2;i++)
for (j=1;j=n/2;j++)
if (ji)
dp[i][j]=0; // the 2nd constraint
else
make a bitwise trie
since the height would be 32 (number of bits in an integer) u only need 32
comparisons to find an element
--
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
your 1st Q:
for each vertex run a dfs and count the number of vertices it can reach O(
V^2 + VE )
another solution would be using an algorithm similar to floyd-warshal O(V^3)
a[src][dest] is true if there is an edge src-dest
for (k=0;kn;k++)
for (i=0;in;i++)
for (j=0;jn;j++)
if (a[i][k]
this can be done in O(n) using DP:
for (i=n-1;i=0;i--){
dp[i]=max(dp[i+2],dp[i+3]); // usual
if (a[i]==a[i+1]) // excellent size 2
dp[i]=max(dp[i],2+dp[i+2]);
if (a[i]==a[i+1] a[i+1]==a[i+2])//excellent size 3
dp[i]=max(dp[i],2+dp[i+3]);
if (a[i]==a[i+1] || a[i]==a[i+2] ||
@ashish: i think u meant amir! anyway...
profit for an excellent group is 2 and for a good group it's 1
dp[i] is the max profit for memorizing a[i], a[i+1], ... , a[n]
dp is initialized to 0
so for example if a[i]==a[i+1]==a[i+2] it means that we can group a[i]
a[i+1] a[i+2] together
suppose n is the size of S and m is the size of T
make to pointers p1=0 and p2=0
make another array C[]={0,0,...} which c[i] counts the number
of occurrence of T[i] in S[p1],S[p1+1]...S[p2]
n1=0 is the number of nonzero elements in C so each time n1==m means that
range p1..p2 can be an answer
here's an algorithm that can find the the max black rectangle in O(n^3)
here sum[i][j] is the number of contiguous 1s in the ith row from j column
until the end of the row
for (i=0;in;i++){
sum[i][m]=0;
for (j=m-1;j=0;j--){
if (a[i][j]==1)
sum[i][j]=1+sum[i][j+1];
else
sum[i][j]=0;
}
}
so now
we can do this in a much better time than divya's algorithm since he does
the shortest path algorithm E+1 times
here's my approach:
find the shortest path using dijkstra since in dijkstra we have the shortest
path to each vertex
now look at the edges that end at the destination if the shortest
the rank of median in the merged list of the two lists is (N1+N2)/2
so if it's rank in list A is i and it's rank in list B is j
then i+j=(N1+N2)/2
(it's rank in the list that it does not belong is i when A[i]medianA[i+1]
)
we do an changed binary search as follows:
pick the middle element of A
both problems can be done in O(n)
pick the first two elements count the number of their appearances in the
array ( O(n) )
if they are not the result we now that there is an element that is repeated
n times in 2n-1 elements and we can do the moore's algorithm for finding it
here's a link to this
number the elements in clockwise order from 1..n suppose n is 12
then start from a point here we start from the point 1 then we find the
farthest point from it in O(n) suppose that's point 5
now if we want to find the farthest point from point 2 since we moved
clockwise the farthest point must
@Rahul: the worst case running time for your algo is O(nlogn)
but here's another approach:
suppose we're searching for x
binary search on the diameter of the matrix (note that the diameter is
sorted)
if x is not on the diameter
when you find i such that a[i][i]xa[i+1][i+1]
split the matrix to
i think that the best method would be a balanced binary search tree which
counts the number of appearances for each element
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
i just find out that after finding the convex hull we can do the rest in
O(h)
(See Jalaj Jaiswal's post: Computational Geometry)
On Tue, Jun 29, 2010 at 1:31 AM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
@Amit: in most of the algos for convex hull the result would
is the 2nd shortest path is edge-disjoint from the shortest path or not?
--
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
@Amit: in most of the algos for convex hull the result would be the points
on the hull in clockwise or counter clockwise order
now we have a point P that we want to find the farthest point from it now
imagine the list as if it's circular and the range where binary search is
applied on starts after
if the matrix is m*n
for each item A[i][j]
search for X-A[i][j] (this can be done in O(m+n) )
so the overall time is O( m*n*(m+n) )
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
make a max-heap of size 1 million and insert the first 1 million numbers in it
for each new number from hard disk compare it to the maximum element
of the heap if it's bigger than max check next element else
extract-max from heap and insert the new element
the running time would be 1 trillion x
sort the array
for each element a[i]
find two elements that sum to -a[i] (this can be done in O(n) )
the overall time is O(n^2)
On 6/23/10, Raj N rajn...@gmail.com wrote:
Given a list of n integers?(negative and positive), not sorted and
duplicates allowed, you have to output the triplets
i think that if you implement the elements of a string in set you can find
its children easily (specially if you map each set to the real strings) in
O( n . max length of a string . d)
where n is the number of strings and d is running time of set.delete()
after making the graph since the maximum
using divide and conquer you can do it in O(nlogn) your recursive function
must return three values the max and min value in this range and the maximum
difference
but this can also be solved in O(n)
start from the end of array if you loop backward you can determine the
max(a[i]) for i=j
and then
here's a linear time solution:
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
On Fri, Jun 18, 2010 at 4:58 PM, Chunyuan Ge hhy...@gmail.com wrote:
good point, i am wrong, sorry
On Fri, Jun 18, 2010 at 5:54 PM, Rohit Saraf
if you can access parent in your tree find the path from the nodes to the
root
then process the two lists from their end and find the last equivalent node
in lists and thats the lowest common ancestor
the running time is O(height of tree) which is the max length of the two
lists
On Thu, Jun 17,
@algoose chase: you're right thx for the test case
On Wed, Jun 16, 2010 at 11:45 AM, Algoose Chase harishp...@gmail.comwrote:
@ Amir:
I think you cannot find two numbers in B and C such that their sum is -A[k]
in O(n) in all cases with the logic that you mentioned.
for instance you can try
here's a recursive solution
int depth(Node n){
if (n==NULL)
return 0;
else
return 1 + max( depth( n.right ) , depth( n.left ) );
}
calling depth(root) will yield the height of the tree
On 6/15/10, ajay kumar ajaykr@gmail.com wrote:
Write a pseudo code 4 that..using
you didn't put an '\0' at the end of the string
strlen looks for a '\0' in the string and here it happened to be 8
bytes after the starting position of s
On 6/15/10, mohit ranjan shoonya.mo...@gmail.com wrote:
Hi All,
char s[]={'a', 'b', 'c', 'd'};
printf(%d\n, strlen(s));
o/p is 8
can
sort all arrays
for each number in A , A[k]
find two numbers in B and C such that their sum is -A[k]
this can be done in O(n) time:
set i at the beginning of B and j at the end of C
while in or j=0
if ( B[i] + C[j] == -A[k] ) return true
if ( B[i] + C[j] -A[k] ) increase i
else decrease
yes we need to maintain an array that shows the real indexes before sorting
and then loop on the elements and find the minimum index that appeared
before a number in the sorted array and subtract it from it's index
and find the maximum difference
On 6/12/10, divya jain sweetdivya@gmail.com
this can be done easily using dynamic programming:
dp[i] = a[i] + max( dp[i+2], dp[i+3], dp[i+4] , ... )
for (i=n-1 ; i=0 ; i--)
{
max=0;
for (j=i+2 ; jn ;j++)
if (dp[j]max)
max=dp[j];
dp[i]=a[i]+max;
}
On 6/11/10, BALARUKESH sbalarukesh1...@gmail.com wrote:
I hope
since we have to visit each value at least once we have to do at least O(n)
steps so there cant be a solution in time less than o(n)
but if the range of the values is limited we can use another array to count
the number of occurrences of each value
and the complexity would be:
o(n) time
o(max of
total is the number of elements reqd in first partition.
present is the no of elements already there in first partition.
the array stores difference between sums. GET the minimum of all
these
and backtrack.
On 5/15/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com
@karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your
diff would be 95 but the best result is 91
i think we can solve this problem by dynamic programming but not a simple
one! since the size of the two subsets must be equal.
so it's DP solution has at least 3 dimensions: tow
this equation is true for 32 but not for 64 so i used a linear search
for 43 the right side is 43.410118 and for 44 its 43.675453
so this equation means n44
On Sat, May 1, 2010 at 9:43 AM, Amit Agarwal lifea...@gmail.com wrote:
I could not get you properly. This is an equation comes from the
On Fri, Apr 30, 2010 at 4:35 PM, divya sweetdivya@gmail.com wrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair
#include time.h
in time.h there's a function named clock() which counts cpu clocks since the
beginning of your program
it also contains a constant named CLOCKS_PER_SEC
so if you divide clock() by CLOCKS_PER_SEC at the end of your code you'll
get the running time
(remember to cast the result to
72 matches
Mail list logo
