I am new to the world of programming. I have to solve the problems on
the spoj.pl , but I have no idea that how I would implement the
algorithms in any programming language. Pls help me.
I need a solution of this problem.
Thanx
scanfile
--
You received this message because you are subscribed
Design an efficient algorithm to report all the points within x1 and x2 from
a list of N integers.
What data structure will you use to implement this algorithm?
Find the order of complexity . ( An O(N) solution is not asked)
--
Thanks Regards,
Priyanka Chatterjee
Third Year Undergraduate
With only this info and without preprocessing , you need to scan all the N
integers in the list atleast once. Hence cannot be better than O(n).
If preprocessing is allowed you can compute the answers for all n^2 pairs of
x1,x2 and when some one asks , return the corresponding list.
In that case it
is the list is sorted...or in some order...
i feel unless the point in the list in some order eg: sorted,
it will be difficult to get soluiton less than O(n)
On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote:
Design an efficient algorithm to report all the
I guess she was asking that the per query complexity should be better that
O(n).
If that is the case then you can use any of these
Simple RMQ O(sqrt(n))
Segment/Interval Trees O(lgn)
Binary Indexed Trees O(lgn)
On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
I think it can be done in logn time ( I assume the list is sorted, is there
an order log n sorting algo, then i can even sort it in log n time ? ( I am
new to algorithms ) ).
1. binary search for low=x1.
2. binary search for high=x2.
both will take log n time. Print all values between them then
ok...sorry u asked the data structure..
On Wed, Mar 31, 2010 at 11:54 AM, BlackdiamonD patidarc...@gmail.comwrote:
is the list is sorted...or in some order...
i feel unless the point in the list in some order eg: sorted,
it will be difficult to get soluiton less than O(n)
On Wed,
you can go through this.:
http://www.topcoder.com/tc?d1=tutorialsd2=alg_indexmodule=Static
and you can follow: Art of Uva online judge
for getting started in this contest...
On Wed, Mar 31, 2010 at 12:05 AM, scanfile rahul08k...@gmail.com wrote:
I am new to the world of programming. I have to
what if your sort the element.first time..
applying binary search on list for x1 (getting minimum index )
applying binary search on list for x2(getting maximum index)
element between this index will be the answer.
complexity:O(log(N)) for getting the range. (not considering the sorting)
On
What do you mean by points ? .. Are you referring to the integer values
stored ?
.
1.) If the question is, given N integers.. and given x1 and x2, report all
integers x (x1=x=x2), you can't do better than O(N), as going through
input itself takes O(N).
.
2.) if the question is, given N integers
Algorithm :
1 Do inorder traversal and at the time of reading data from tree, add
data to doubly link list.
(Inorder traversal will give you sorted order data and it can be
added to DLL. Thus, we can get sorted DLL.)
Code :
struct node
{
struct node *left;
int data;
struct node *right;
};
First learn a language of your choice and then you can start solving over
there
On Wed, Mar 31, 2010 at 12:05 AM, scanfile rahul08k...@gmail.com wrote:
I am new to the world of programming. I have to solve the problems on
the spoj.pl , but I have no idea that how I would implement the
Hii,
what is Art of Uva online judge Does it contain some
training material like USACO
--
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
We can make a query tree and then each query will take O(log n+k) time.
On Wed, Mar 31, 2010 at 12:48 PM, Anil Kishore anil.dai...@gmail.com wrote:
What do you mean by points ? .. Are you referring to the integer values
stored ?
.
1.) If the question is, given N integers.. and given x1 and
How much time to u have? If you have got more than a month and u don't know
any language; then I'll suggest you to learn a programming language like C++
or Java.
In my opinion, C++ is the best language for these kind of problems :)
Regards
Umer.
On Wed, Mar 31, 2010 at 5:12 PM, naga vinod kumar
ok i previously i written wrong it is :*Art-of-Programming*-Contest-SE-for-
*Uva
book for basic of programming and some of the solving methods for problems.
here is the Link
Art_of_Programming_Contest_SE_for_uva.pdfhttp://online-judge.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf
*
On Wed,
@web-hav
*I think the actual problem is in place changing a bst into a DLL(Doubly
linked list) without using extra space .*
If you are allowed to use extra space then problem is pretty simple and your
code solves its purpose.
Shrish Chandra Mishra
CSE NIT,Allahabad
On Wed, Mar 31, 2010 at
The list of N integers is not sorted.
The solution is asked for a particular query.
@Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment
Interval trees*. May be you opted for the correct data structure. Please
give the algorithm.
@All: Doing a sorting for O(n logn) and
@All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in
O(logn) will be less efficient than the simple solution of O(n). Think on
the data structure that can optimize it.
Is it possible in time complexity O(n)?
If you want to do the operation just once then it cannot
*Binary Indexed Trees* or *Segment Interval trees*. building them also it
will take O(n log(n))
..i feel for a particular query it will be difficult less than O(n) .because
.u must know all the element.
On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee dona.1...@gmail.comwrote:
The list of
20 matches
Mail list logo
