### PROBLEM LINK

### Panel Members

**Problem Setter:** Sergey Nagin

**Problem Tester:** Istvan Nagy

**Editorialist:** Sunny Aggarwal

**Contest Admin:** Praveen Dhinwa

**Russian Translator:** Sergey Nagin

**Mandarin Translator:** Hu Zecong

**Vietnamese Translator:** VNOI Team

**Language Verifier:** Rahul Arora

### DIFFICULTY:

Easy

### PREREQUISITES:

Simple Simulation, Arrays, Implementation

### PROBLEM:

Given that N persons numbered from 1 to N are invited to a party in the order 1 to N and when i^{th} person joins the party, he must go and stand to the

immediate right of the person numbered A_i (if A_i = 0, then this person just stands at the leftmost position). But as there is no space availability between

two consecutive persons at any given time, space must be created by moving either all the persons standing left of the place to the left one step each, or all

the persons standing right of the place to the right one step each. Calculate the minimum number of steps movement required to accomodate all the N

persons in the party.

### QUICK EXPLANATION

When i^{th} person joins the party, all the persons numbered X where X \lt i are already present in the party in some fixed order. i^{th} person will move all the

people standing left of the place to the left if number of persons standing left of the place is less than the number of persons standing right of the place otherwise he will

move all the people standing right of the place to the right.

### EXPLANATION

This is a simple simulation problem. i^{th} person joins the party and check for the number of steps required to move the persons standing left of the place to the left or to move

the persons standing right of the place to the right. If the number of steps to move the persons to the left is less than the steps required to move the persons to the right, he will

move the persons standing left of the place to the left otherwise he will move the persons standing right of the place to the right.

**How to insert a new person in the existing ordering ?**

Constraints of this problem are quite low. Therefore, we can simply use arrays and can insert element at a position in an array with a worst complexity of O(N)

where N is the size of array.

Please have a look at the following fragment of code for better understanding of solution.

**C++ Code:**

int A[N+1]; int ordering[N+1]; // It will have the ordering of persons at party. int steps = 0; for(int i=1; i<=n; i++) { // lets place the ith person at ith position initilly. // we will move this person to its correct position soon. ordering[i] = i; if( A[i] == 0 ) { // This person will stand at the left most place. // moving this person to the left most place. for(int j=i; j>=2; j--) { swap(ordering[j], ordering[j-1]); } // no steps is required in this case as there //is no person standing to the left of this place. } else { // finding correct position of this person in // the current ordering i.e right to A_i^th person. for(int j=1; j<=i; j++) { if( ordering[j] == A[i] ) { break; } } // minimum of number of steps requires to move the persons left // of the place to the left or the number of steps required // to move the persons right of the place to the right. steps += min(j, (i-1)-j); // moving ith person to it correct position // i.e right of A_ith person. for(int k=i; k>=j+2; k--) { swap(P[k], P[k-1]); } } }

### COMPLEXITY

O(N^2) per test case.

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.

The tester’s solution can be found here.

The editorialist’s solution can be found here.