Inserting and deleting elements in a list

Question

In my code, I use fast method of reading input and a custom model of list. After reading the input into my 'list'.

The problem is that, when I test my code, most answers are correct, but for some INPUT my algorithm works slow. I unfortunately don't know the input data, but 6 from 12 tests finished with the wrong time. Maybe for some input data, some of the loops do not stop.

Where time is 1.01 or 2.01 -> wrong

where time is 1.01 or 2.01 -> wrong

TASK

Consider any indexed sequence of natural numbers C, which define the concept of the present position. Next, we introduce two operations on the elements of this sequence: If amount of sequence of natural numbers is even number ->

R, remove the item 'c' on index POS + 1, then move the pointer POS on 'c' elements to the right, otherways ->

X, inserting element 'c' on the position (POS + 1) value 'c-1' from POS, and then moving the pointer on the POS 'c' elements to the right.

INPUT:

the number of times of repetition scheme of operations R and X, the sequence of natural numbers 'C'

OUTPUT:

numbers after operations from the position of index

LIMITS

The time complexity of O (tn), where 'n' is the length of 'C' and 't' - times of repetition operations R and X.

#include<iostream>
#include<stdlib.h>
#define gc getchar_unlocked
struct Element
{
 unsigned int c;
 Element* next;
 Element(unsigned int value)
 {
 c = value;
 next = NULL;
 }
};
void scan_integer(unsigned int* o )
{
 unsigned int c = gc();
 int x = 0;
 for( ; ((c<48 || c>57)); c = gc() );
 for( ;c>47 && c<58; c = gc() ) {
 x = (x << 1) + (x << 3) + c - 48;
 }
 *o = x;
}
int main()
{
 unsigned int rounds;
 scan_integer(&rounds);
 if(!feof(stdin))
 {
 unsigned int elements = 0;
 unsigned int tmp;
 scan_integer(&tmp);
 Element* first = new Element(tmp);
 elements++;
 Element* current = first;
 while(!feof(stdin))
 {
 scan_integer(&tmp);
 current->next = new Element(tmp);
 current = current->next;
 elements++;
 }
 current->next = first;
 current = first;
 for(int i = 0; i < rounds; i++)
 {
 if(elements == 0){
 fprintf(stdout, "%u", -1);
 break;
 }
 unsigned int value;
 if(current->c & 1)
 {
 value = current->c;
 Element* newC = new Element(value-1);
 newC->next = current->next;
 current->next = newC;
 elements++;
 }
 else
 {
 value = current->next->c;
 Element* toDelete = current->next;
 current->next = toDelete->next;
 delete toDelete;
 elements--;
 }
 if(elements > 0 && value != 0){
 for(int j = 0; j < value; j++){
 current = current->next;
 }
 }
 }
 if (elements == 0) {
 fprintf(stdout, "%u", -1);
 }
 if(elements > 0)
 {
 first = current;
 fprintf(stdout, "%u", current->c);
 current = current->next;
 while(first != current)
 {
 fprintf(stdout, " %u", current->c);
 current = current->next;
 }
 }
 }else{
 return -1;
 }
 return 0;
}

• vnp: Could you add a link to the original challenge?
• Vitalii Syrotynskyi: @vnp it's on Polish
• vnp: That's fine (although I hoped it is in Russian). Some parts of the problem statement are very unclear. Is there a difference between POS and IND? Why Element(value - 1) when problem says 1 - c? What should happen when moving pointer falls off the end of sequence?
• Vitalii Syrotynskyi: @vnp No, there isn't difference between POS and IND, it's my mistake. And '1 - c' in task is also my mistake, 'c -1 is correct'. Sorry.
• Vitalii Syrotynskyi: @vnp the problem is in time of the algorithm. For some data it's good, as you can see on the picture, but for some not. And I want to find some, maybe, new idea of solving this algorithm or to make my one faster. To my mind the main problem is in this part, but I have no ideas how to change it. if(elements > 0 && value != 0){ for(int j = 0; j < value; j++){ current = current->next; }

Answer 1

Let's start with the code style, even though not asked explicitly.

It says C++, but apart from using a constructor on the struct and using new/delete, that is pure C what you have written there.

Especially the C style input and output handling is overcomplicated, with regards to how much simpler the C++ interfaces are to use.

---

As for your implementation, you don't need a linked list. In fact, you don't need to store the input nor the output sequence at all, at least not for the algorithm itself.

Take a look at the problem carefully again, and try to think about how you can rephrase the operations, when do you need to consume input, and what the earliest point is, at which you can create output. Last but not least, how long do you even need to store each specific piece of information.

The first observation:
Whenever an operation has finished, the value at POS is no longer mutated, and no further insertions or deletions occur prior to POS.

The second observation:
During an operation at POS, no value other than POS has an effect on that operation. At most POS+1 is either removed or added in.

The third observation:
As all numbers are guaranteed to be natural numbers, even c - 1 > 0 must hold. Which means that in any case, POS+1 is always output in the same operation as which it is mutated in.

---

With that in mind, it's actually quite simple to solve this problem:

#include <iostream>
#include <vector>
int main()
{
 std::vector<int> input;
 int rounds = 0;
 bool even = false;
 // Collect the input
 std::cin >> rounds;
 int temp;
 while(std::cin >> temp) {
 input.push_back(temp);
 }
 even = (input.size() % 2) == 0;
 std::vector<int>::iterator it = input.begin();
 // Special handling for first element
 std::cout << *it;
 it++;
 for(int round = 0; round < rounds; round++) {
 // Number of steps to the right
 int steps = *it;
 if(even) {
 // Operation "R"
 // Skip one
 it++;
 // And pass through from input
 for(int i = 0; i < steps; i++, it++) {
 std::cout << " " << *it;
 }
 } else {
 // Operation "X"
 // Directly output `POS+1`
 std::cout << " " << *it - 1;
 // But pass through one less input in return
 for(int i = 0; i < steps - 1; i++, it++) {
 std::cout << " " << *it;
 }
 }
 even != even; 
 }
 for(; it != input.end(); it++) {
 std::cout << " " << *it;
 }
}

It is unfortunately still necessary to store the entire input in memory, in order to count the elements. If it wasn't for that, you could just copy from input to output element wise.

But what's important: The data structure used is now a plain vector, which removes a lot of unnecessary stress on the memory system, as the storage method is a compact as it gets.

There are also no mutations to that data structure at all, it only serves to replay the input after counting all elements.

Answer 2

The program spends most of the time in list maintenance - allocating, deleting, and traversing the nodes. The solution is to not have the list in the first place.

You are only required to skip values to the right, therefore there is no point to keep the values at the left of the current index. Print them as necessary, and forget:

 while count < operations
 read a value n
 if n is even,
 read and print next n values
 else
 print (n - 1)
 read and print next (n - 1) values
 increment count
 read and print the rest

• Ext3h: Wrong condition on the if..else.., it's not the value at the current input position, but the total number of elements in the sequence. So you still can't do it without buffering the input in whole.