## Saturday, October 29, 2016

### Hacker Rank - New Year Chaos

Problem:

Analysis:

This is basically counting the number of swapping. This sound very familiar, like an insertion sort would have solved this, but the problem stretch me to find an $O(n)$ solution.

Solution:

In my solution, I maintain a sequence for what I expect, accounting for all the bribe I have seen so far. As an example, let's solve the problem for input 3,2,1,6,5,4

Initially, I expect the sequence simply be 1,2,3,4,5,6

I see 3, the expected position is 3, but the seen position is 1, therefore, there must be two bribes going on for 3 to get to the first position, therefore, the bribe count is 2, and my new expected sequence is:

3,1,2,4,5,6

Now I see 2, the expected position is 3, but the seen position is 1, therefore, there must be one bribe going on for 2 to get to the second position, therefore the bribe count is 3, and my new expected sequence is:

3,2,1,4,5,6

Now I see 1, the expected position is 3, and the seen position is 3, nothing need to be done for him.

The procedure moves on and calculate the final bribe count to be 6. In order to efficiently get the expected position for a person as well as the expected person at his previous position, I maintained a two way map for this sequence.

Code:

#include "stdafx.h"

// https://www.hackerrank.com/challenges/new-year-chaos

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int HACKER_RANK_NEW_YEAR_CHAOS()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n;
cin >> n;
vector<int> expect_person;
vector<int> expect_position;
vector<int> actual;
expect_person.resize(n);
expect_position.resize(n);
actual.resize(n);
for (int j = 0; j < n; j++)
{
expect_person[j] = j;
expect_position[j] = j;
cin >> actual[j];
actual[j]--;
}
bool good = true;
int bribe_count = 0;
for (int p = 0; p < n; p++)
{
int seen_person = actual[p];
int position_difference = expect_position[seen_person] - p;
if (position_difference > 2)
{
good = false;
break;
}
bribe_count += position_difference;
if (position_difference >= 1)
{
int current_position = expect_position[seen_person];
int previous_position = current_position - 1;
int previous_person = expect_person[previous_position];
expect_person[previous_position] = seen_person;
expect_position[seen_person] = previous_position;
expect_person[current_position] = previous_person;
expect_position[previous_person] = current_position;
}
if (position_difference == 2)
{
int current_position = expect_position[seen_person];
int previous_position = current_position - 1;
int previous_person = expect_person[previous_position];
expect_person[previous_position] = seen_person;
expect_position[seen_person] = previous_position;
expect_person[current_position] = previous_person;
expect_position[previous_person] = current_position;
}
}
if (!good)
{
cout << "Too chaotic" << endl;
}
else
{
cout << bribe_count << endl;
}
}
return 0;
}