I need help with optimising my algorithm of self-organising sequence of numbers with big amount of operations on it.

For input I have been given number of operations that should be executed(t) and after that indexed sequence of natural numbers seperated with a space. So for example:

3 1 2 3

This means that there will be 3 operations executed on sequence {1,2,3}.

There is also defined a pointer, which shows current position. Operations on that sequence that I should implement are:

• R -> removing element c on index PTR+1 and moving PTR forward c times

• X -> inserting right after element c, which is on index PTR (so inserting on PTR+1), element with value of c-1 and of course moving PTR forward c times.

My job is to find ending sequence after performing operations R and X t times so that if its element is even then do the R, else do the X. At the start PTR shows first element(if exists) and it should be all in cycle.

For given example at the start of post the output should be:

0 0 3 1

I know that it might sound confusing, so let me show you how this should work step by step.

t = 1

Starting sequence: 1 2 3

Actual position: PTR -> 1

Operation: X, c=1

Ending sequence: 1 0 2 3

Ending position: PTR -> 0

t = 2

Starting sequence: 1 0 2 3

Actual position: PTR -> 0

Operation: R, c=2

Ending sequence: 1 0 3

Ending position: PTR -> 1

t = 3

Starting sequence: 1 0 3

Actual position: PTR -> 1

Operation: X, c=1

Ending sequence: 1 0 0 3

Ending position: PTR -> 0

The solution is a sequence from PTR in right direction. So output should be: 0 0 3 1

As for circumscriptions:

• starting length of C sequence up to 10^7

• number of t operations up to 10^7

• moving PTR to right up to 10^9 times

I have created my algorithm, which is based on circular doubly linked list. Works, but it’s too slow for some tests. I’d be more than grateful if someone could help me optimise it.

I have implemented it. Here is my code:

#include <stdio.h> #include <stdlib.h> using namespace std; int allCharCounter = 0;  struct List_node{     int value;     struct List_node *next;     struct List_node *prev; };  //inserting at first void insert(List_node** start, int v){     List_node* newNode = new List_node;     newNode->value = v;      if(*start == NULL){          newNode->next = newNode;         newNode->prev = newNode;         *start = newNode;     }else{         newNode->next = *start;         newNode->prev = (*start)->prev;         (*start)->prev->next = newNode;         (*start)->prev = newNode;     } }  //getting input int getNumber(){     int c = getchar_unlocked();     int value = 0;     for(; (c < 48 || c > 57); c = getchar_unlocked());      for(; c > 47 && c < 58 ; c = getchar_unlocked()){         value = 10*value+c-'0';         allCharCounter++;     }     return value; }   int main(){      int numberOfOperations = getNumber();     struct List_node* list = NULL;      //counter of numbers     int numbersInSeq = 0;      //passing values to list     while(!feof(stdin)){         int number = getNumber();         insert(&list, number);         numbersInSeq++;     }      if(list !=NULL){          while(numberOfOperations-- != 0){             int c = list->value;              //insert - X             if(c & 1){                 List_node* newNode = new List_node;                 newNode->value = c-1;                  newNode->prev = list;                 newNode->next = list->next;                 list->next->prev = newNode;                 list->next = newNode;                  numbersInSeq++;                 int moveNext = c%numbersInSeq;                 //int movePrev = numbersInSeq - moveNext;                  for(int i = 0; i < moveNext; i++){                     list = list->next;                 }             }else{                 //remove - R                 c = list->next->value;                 List_node* tmp = list->next;                  list->next = tmp->next;                 list->next->prev = list;                 tmp->next = NULL;                 tmp->prev = NULL;                 free(tmp);                  numbersInSeq--;                 int moveNext = c%numbersInSeq;                 //int movePrev = numbersInSeq - moveNext;                 //moving my list (POS)                 for(int i = 0; i < moveNext; i++){                     list = list->next;                 }             }          }         //printing output         for(int i = 0; i < numbersInSeq; i++){             fprintf(stdout, "%d",list->value);              if(i != numbersInSeq-1){                 fprintf(stdout, "%c",' ');              }             list = list->next;         }      }else{         //in case of empty list return -1         fprintf(stdout, "%d", -1);      }     fprintf(stdout, "%c",'\n');              fprintf(stdout, "%d",allCharCounter);  } 

This code uses circular doubly linked list, output is always correct, but as I said before it was too slow for some test’s. You also may see that by mistake I implemented moving the list(POS) only using next. So I came up with this:

int moveNext = c%numbersInSeq; int movePrev = numbersInSeq - moveNext; if(moveNext < movePrev){     for(int i = 0; i < moveNext; i++){         list = list->next;                       }    }else{     for(int i = 0; i < movePrev; i++){         list = list->prev;     } } 

Injected right after incrementing and decrementing numbersInSeq in both X and R methods. Variable moveNext is a number of iterations that is needed to move pointer to desired place by using next. So the diffrence of it and numbersInSeq is movement by prev. Because of that I know what is more efficient, moving it using next or prev.

I have tested it on example with 50 digits and output was correct. Number of iterations was smaller:

• w/o – 13001

• with – 570

Not only it haven’t passed even one more test there, but also it was too slow for another test(Although I don’t know exactly what was in there, but I can tell you that file with its size is around 34mb).

Maybe you can see what I missed here/wrote badly/don’t know about structure. Is it possible to optimise somehow my code to be faster?