In this HackerEarth Rotations and Inversions, problem-solution Rahul has recently learnt about array inversions. An array a has N integers, indexed from 0 to N - 1. Formally, the number of inversions is the number of pairs (i, j) such that 0 <= i < j < N and a[i] > a[j].
Now, he wants to find the lexicographically smallest left rotation of the array such that number of inversions are maximized. The index of rotation is defined as the number of elements from the front that need to left rotated. For example, given the array with elements a[0], a[1], a[2], ..., a[N - 1], the rotation with index 1 will be a[1], a[2], ..., a[N - 1], a[0]; the rotation with index k will be a[k], a[k + 1], ..., a[N - 1], a[0], ..., a[k - 1].
Note that in case, multiple lexicographically equal rotations are found to have the largest number of inversions, you should print the smallest index of rotation.
An array a of integers is lexicographically smaller than another array b if a[i] = b[i] for all indices 0 ≤ i < k and a[k] < b[k].
HackerEarth Rotations and Inversions problem solution.
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.List;
import java.io.OutputStream;
import java.util.Collections;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;
import java.util.Arrays;
import java.util.TreeMap;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Collection;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InReader in = new InReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
RotationsAndInversions solver = new RotationsAndInversions();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}
}
class RotationsAndInversions {
int [] a;
private int compress() {
List<Integer> b = new ArrayList<Integer>();
for (int i = 0; i < a.length; i++) {
b.add(a[i]);
}
Collections.sort(b);
int [] ba = ArrayUtils.unique(CollectionUtils.toArray(b), 0, b.size());
for (int i = 0; i < a.length; i++) {
a[i] = Arrays.binarySearch(ba, a[i]) + 1;
}
//System.out.println(Arrays.toString(a));
return ba.length;
}
public void solve(int testNumber, InReader in, OutputWriter out) {
int n = in.readInt();
a = IOUtils.readIntArray(in, n);
int maxval = compress();
//two pointer approach with BIT
BIT tree = new BIT(maxval);
int i = 0, j = 0;
long ans = -1, inv = 0;
ArrayList<Integer> good = new ArrayList<>();
while (i < n && j < 2 * n) {
if (i > 0) {
//remove the first index of last window
inv -= tree.freqTo(a[i - 1] - 1);
tree.update(a[i - 1], -1);
}
//include the new index of window
tree.update(a[j % n], 1);
//update the number of inversions
//j - i + 1 gets the size of current window
inv += j - i + 1 - tree.freqTo(a[j % n]);
//if current window has size atleast n
if (j >= n - 1) {
if (ans == -1 || inv == ans) {
good.add(i);
ans = inv;
} else if (inv > ans) {
//found better answer
good.clear();
good.add(i);
ans = inv;
}
//System.out.println(i + " " + j + " " + inv);
i++;
}
j++;
}
boolean isGood[] = new boolean[2 * n];
for (int goods : good)
isGood[goods] = true;
int a2[] = new int[2 * n];
for (int k = 0; k < n; k++) {
a2[k] = a2[k + n] = a[k];
}
int[] sa = SuffixArray.suffixArray(a2);
int[] lcp = SuffixArray.lcp(sa, a2);
int ind = -1;
for (int idx = 0; idx < 2 * n; idx++) {
if(!isGood[sa[idx]]) continue;
ind = sa[idx];
if(idx < 2 * n - 1) if(lcp[idx] < n) break;
}
out.printLine(ind + " " + ans);
}
}
class ArrayUtils {
public static int[] unique(int[] array, int from, int to) {
if (from == to)
return new int[0];
int count = 1;
for (int i = from + 1; i < to; i++) {
if (array[i] != array[i - 1])
count++;
}
int[] result = new int[count];
result[0] = array[from];
int index = 1;
for (int i = from + 1; i < to; i++) {
if (array[i] != array[i - 1])
result[index++] = array[i];
}
return result;
}
}
class CollectionUtils {
public static int[] toArray(Collection<Integer> collection) {
int[] array = new int[collection.size()];
int index = 0;
for (int element : collection)
array[index++] = element;
return array;
}
}
class InReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InReader(InputStream stream) {
this.stream = stream;
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuffer res = new StringBuffer();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
class IOUtils {
public static int[] readIntArray(InReader in, int size) {
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}
public static long[] readLongArray(InReader in, int size) {
long[] array = new long[size];
for (int i = 0; i < size; i++)
array[i] = in.readLong();
return array;
}
}
class BIT {
int maxVal;
long[] BIT;
boolean mod;
public BIT(int n) {
this.BIT = new long[n + 1];
maxVal = n;
mod = false;
}
public void update(int idx, long val) {
while (idx <= maxVal) {
//BIT[idx] = Math.max(BIT[idx], val);
BIT[idx] += val;
//if(mod && BIT[idx] >= MOD) BIT[idx] %= MOD;
idx += (idx & -idx);
}
}
public long freqTo(int idx) {
long sm = 0;
while (idx > 0) {
//sm = Math.max(sm, BIT[idx]);
sm += BIT[idx];
//if(mod && sm >= MOD) sm %= MOD;
idx -= (idx & -idx);
}
return sm;
}
}
class SuffixArray {
public static int[] suffixArray(int[] str) {
int n = str.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++)
order[i] = n - 1 - i;
Arrays.sort(order, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return str[o1] - str[o2];
}
});
// sa[i] - suffix on i'th position after sorting by first len characters
// rank[i] - position of the i'th suffix after sorting by first len characters
int[] sa = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
sa[i] = order[i];
rank[i] = str[i];
}
for (int len = 1; len < n; len *= 2) {
int[] r = rank.clone();
for (int i = 0; i < n; i++) {
// condition s1 + len < n simulates 0-symbol at the end of the string
// a separate class is created for each suffix followed by 0-symbol
rank[sa[i]] = i > 0 && r[sa[i - 1]] == r[sa[i]] && sa[i - 1] + len < n && r[sa[i - 1] + len / 2] == r[sa[i] + len / 2] ? rank[sa[i - 1]] : i;
}
// Suffixes are already sorted by first len characters
// Now sort suffixes by first len * 2 characters
int[] cnt = new int[n];
for (int i = 0; i < n; i++)
cnt[i] = i;
int[] s = sa.clone();
for (int i = 0; i < n; i++) {
// s[i] - order of suffixes sorted by first len characters
// (s[i] - len) - order of suffixes sorted only by second len characters
int s1 = s[i] - len;
// sort only suffixes of length > len, others are already sorted
if (s1 >= 0)
sa[cnt[rank[s1]]++] = s1;
}
}
return sa;
}
// longest common prefixes array in O(n)
public static int[] lcp(int[] sa, int[] s) {
int n = sa.length;
int[] rank = new int[n];
for (int i = 0; i < n; i++)
rank[sa[i]] = i;
int[] lcp = new int[n - 1];
for (int i = 0, h = 0; i < n; i++) {
if (rank[i] < n - 1) {
int j = sa[rank[i] + 1];
while (Math.max(i, j) + h < s.length && s[i + h] == s[j + h]) {
++h;
}
lcp[rank[i]] = h;
if (h > 0)
--h;
}
}
return lcp;
}
}Second solution
#include <bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (int i = (n) - 1; i >= 0; i--)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar, val) memset(ar, val, sizeof(ar))
#define uint64 unsigned long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define PI 3.1415926535897932385
#define EPS 1e-7
#define MOD 1000000007
#define INF 1500111222
#define MAX 400111
#define MAXK 18
struct BITree {
int n;
vi value;
BITree(int n) {
this->n = n;
value = vi(n + 1, 0);
}
int get(int lo, int hi) {
return get(hi) - get(lo - 1);
}
int get(int i) {
int res = 0;
while (i > 0) {
res += value[i];
i -= (-i & i);
}
return res;
}
void update(int i, int val) {
while (i <= n) {
value[i] += val;
i += (-i & i);
}
}
};
int n, m, a[MAX], p[MAX][MAXK];
int64 inver[MAX];
struct Entry {
int id;
ii val;
bool operator < (const Entry &en) const {
if (val == en.val)
return id < en.id;
return val < en.val;
}
} L[MAX];
void calSuffix() {
int k = 16;
rep(i, n) p[i][0] = a[i];
fr(j, 1, k) {
int len = 1 << (j - 1);
rep(i, n) {
L[i].val.ff = p[i][j - 1];
L[i].val.ss = (len + len <= n) ? p[(i + len) % n][j - 1] : -1;
L[i].id = i;
}
sort(L, L + n);
p[L[0].id][j] = 0;
fr(i, 1, n - 1) p[L[i].id][j] = p[L[i - 1].id][j] + (L[i].val != L[i - 1].val);
}
}
void solve() {
BITree tree(n);
int64 maxRes = 0, curRes = 0;
rep(i, n) {
curRes += tree.get(a[i] + 1, n);
tree.update(a[i], 1);
a[i + n] = a[i];
}
inver[0] = maxRes = curRes;
for (int i = n, j = 0; j < n - 1; i++, j++) {
curRes -= tree.get(0, a[j] - 1);
curRes += tree.get(a[i] + 1, n);
inver[j + 1] = curRes;
maxRes = max(maxRes, curRes);
}
//printf("max %d\n", maxRes);
calSuffix();
//rep(i, n) printf("%d: [%d] %d, inver = %d\n", i, L[i].id, a[L[i].id], inver[L[i].id]);
int maxIndex = 0;
rep(i, n) {
int id = L[i].id;
if (inver[id] == maxRes) {
maxIndex = id;
break;
}
}
printf("%d %lld\n", maxIndex, maxRes);
}
void compress() {
map<int, int> idx;
rep(i, n) idx[a[i]] = 1;
int m = 0;
for (map<int, int>::iterator it = idx.begin(); it != idx.end(); it++)
it->ss = ++m;
rep(i, n) a[i] = idx[a[i]];
}
bool compare(int x, int y) {
rep(i, n) {
if (a[x] != a[y])
return a[x] < a[y];
x = (x + 1) % n;
y = (y + 1) % n;
}
return false;
}
void solveBruteForces() {
int64 maxRes = -1;
int maxIndex = -1;
rep(x, n) {
BITree tree(n);
int64 res = 0;
rep(i, n) {
int id = (x + i) % n;
res += tree.get(a[id] + 1, n);
tree.update(a[id], 1);
}
if (res > maxRes || (res == maxRes && compare(x, maxIndex))) {
maxRes = res;
maxIndex = x;
}
}
printf("%d %lld\n", maxIndex, maxRes);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
#endif
int cases;
scanf("%d", &cases);
assert(1 <= cases && cases <= 10);
while (cases--) {
scanf("%d", &n);
assert(1 <= n && n <= 1e5);
rep(i, n) {
scanf("%d", &a[i]);
assert(1 <= a[i] && a[i] <= 1e9);
}
compress();
solve();
//solveBruteForces();
}
return 0;
}
0 Comments