A datastructure for Robotic Sort

Posted by amit.codename13 on Stack Overflow See other posts from Stack Overflow or by amit.codename13
Published on 2010-04-17T08:19:53Z Indexed on 2010/04/17 8:23 UTC
Read the original article Hit count: 253

Filed under:

datastructure

|

spoj

I am trying to solve this problem :

https://www.spoj.pl/problems/CERC07S/

I have identified that i need a datastructure in which reversing operations have lesser time complexity. I tried to create one using a doubly linked list, in which (i thought) reversing can be done in O(1) by just changing a value associated with the starting and ending node which indicates the direction of traversing the list. I tried to implement it but got stuck. Maybe the approach is wrong!

Are trees applicable here? If yes, how? Any ideas or links are appreciated?

Thanks in advance.

© Stack Overflow or respective owner

Related posts about datastructure

A datastructure for Robotic Sort

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to solve this problem : https://www.spoj.pl/problems/CERC07S/ I have identified that i need a datastructure in which reversing operations have lesser time complexity. I tried to create one using a doubly linked list, in which (i thought) reversing can be done in O(1) by just changing… >>> More
C# datastructure

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi Whats the best data structure for a 2D array of size unknown x 2. Which means one dimension is dynamic (list of grocery items) and the other is fixed (price and quantity). Thanks >>> More
Best datastructure for frequently queried list of objects

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I have a list of objects say, List. The Entity class has an equals method,on few attributes ( business rule ) to differentiate one Entity object from the other. The task that we usually carry out on this list is to remove all the duplicates something like this : List<Entity> noDuplicates… >>> More
Best datastructure for this relationship...

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a question about database 'style'. I need a method of storing user accounts. Some users "own" other user accounts (sub-accounts). However not all user accounts are owned, just some. Is it best to represent this using a table structure like so... TABLE accounts ( ID ownerID -> ID … >>> More
What would be the datastructure in following scenorio?

as seen on Stack Overflow - Search for 'Stack Overflow'
Please note that there is no limitation of memory. I need to insert int from 1 to 1000. I can do the following operations in constant order of time: push(), pop() and getMax() Please suggest me appropriate datastructure. >>> More

Related posts about spoj

spoj: runlength

as seen on Stack Overflow - Search for 'Stack Overflow'
For RLM problem of SPOJ: This is the problem: "Run-length encoding of a number replaces a run of digits (that is, a sequence of consecutive equivalent digits) with the number of digits followed by the digit itself. For example, 44455 would become 3425 (three fours, two fives). Note that run-length… >>> More
Help making this code run faster for spoj.

as seen on Stack Overflow - Search for 'Stack Overflow'
I've been doing a few of the challenges on the Sphere Online Judge, but I can't seem to get the second problem (the prime generator) to run within the time limit. Does anyone have any tips for increasing the speed of the following code? #include <stdio.h> #include <math.h> int is_prime(int… >>> More
CODE1 at SPOJ - cannot solve it

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to solve the problem Secret Code on SPOJ, and it's obviously a math problem. The full problem For those who are lazy to go and read, it's like this: a0, a1, a2, ..., an - sequence of N numbers B - a Complex Number (has both real and imaginary components) X = a0 + a1*B + a2*(B^2) +… >>> More
CODE1 Spoj - cannot solve it

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to solve the problem Secret Code and it's obviously math problem. The full problem For those who are lazy to go and read, it's like this: a0,a1,a2,...,an - sequence of N numbers B - some number known to us X = a0 + a1*B + a2*(B^2) + a3*(B^3) + ... + an*(B^n) So if you are given B… >>> More
Can you tell me why this generates time limit exceeded in spoj(Prime Number Generator)

as seen on Stack Overflow - Search for 'Stack Overflow'
#include<iostream> #include<string.h> #include<math.h> using namespace std; bool prime[1000000500]; void generate(long long end) { memset(prime,true,sizeof(prime)); prime[0]=false; prime[1]=false; for(long long i=0;i<=sqrt(end);i++) { … >>> More