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.