CSES 3152 Bubble Sort Rounds II

Published on

Problem Statement

Given an array $a$ of $n$ integers, find out the contents of the array after $k$ bubble sort rounds.

$1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 10^9, 1 \leq a_i \leq 10^9$

Tutorial

Note that if $k = 10^9$, then the array becomes fully sorted. Hence the problem is strictly stronger than regular sorting.

First, observe that if we perform one round of bubble sort on array $a$, for each index $i$, the number of indices $j$ such that $j < i$ and $a_j > a_i$ will decrease by one. This means we can compute how many values greater than $a_i$ are to its left after $k$ bubble sort rounds.

So, the problem is transformed into the following:

We have an array

$$p_i = \max\left(0, -k + \sum\limits_{1 \leq j < i} \left[a_j > a_i\right]\right)$$

and we are asked to reorder the array $a$ into array $b$ such that:

$$p_i = \sum\limits_{1 \leq j < i} \left[b_j > b_i\right]$$

then, $b$ is the final answer.

We can sort $(a_i, p_i)$ in decreasing order, then insert each $a_i$ at position $p_i$, but this takes $O\left(n^2\right)$ in total. We can optimize it using a balanced tree to achieve $O\left(n \log n\right)$, which is fast enough.

// rbtree (https://rbtr.ee)
// n@rbtr.ee
import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;

public class Main {
  static final boolean MULTI_TESTS = false;
  static final boolean SPECIAL_TESTS = false;
  static final Bin bin;
  static final int INF32 = 1073741823;
  static final long INF64 = 4611686018427387903L;
  static final Random rng = new Random();

  static int n, k;
  static int[] a, all;
  static HashMap<Integer, Integer> id;
  static Fenwick<Integer, Opt> o;
  static pair<Integer, Integer>[] q;

  static class TNode {
    int val;
    int size;
    long priority;
    TNode left, right;

    TNode(int val) {
      this.val = val;
      size = 1;
      priority = rng.nextLong();
    }
  }

  static int size(TNode t) {
    return t == null ? 0 : t.size;
  }

  static void updateSize(TNode t) {
    if (t != null) t.size = size(t.left) + size(t.right) + 1;
  }

  static TNode[] split(TNode t, int key) {
    if (t == null) return new TNode[]{null, null};
    int cur = size(t.left);
    if (key <= cur) {
      TNode[] leftSplit = split(t.left, key);
      t.left = leftSplit[1];
      updateSize(t);
      return new TNode[] { leftSplit[0], t };
    } else {
      TNode[] rightSplit = split(t.right, key - cur - 1);
      t.right = rightSplit[0];
      updateSize(t);
      return new TNode[] { t, rightSplit[1] };
    }
  }

  static TNode merge(TNode left, TNode right) {
    if (left == null) return right;
    if (right == null) return left;
    if (left.priority > right.priority) {
      left.right = merge(left.right, right);
      updateSize(left);
      return left;
    } else {
      right.left = merge(left, right.left);
      updateSize(right);
      return right;
    }
  }

  static TNode insert(TNode root, int pos, int val) {
    TNode newNode = new TNode(val);
    TNode[] splitNodes = split(root, pos);
    TNode merged = merge(splitNodes[0], newNode);
    return merge(merged, splitNodes[1]);
  }

  static void inorder(TNode t) {
    if (t == null) return;
    inorder(t.left);
    bin.print(all[t.val] + " ");
    inorder(t.right);
  }

  public static int ENGINE(int TEST_NUMBER) {
    n = bin.Int();
    k = bin.Int();
    a = new int[n];
    for (int i = 0; i < n; ++i) a[i] = bin.Int();
    all = Arrays.copyOf(a, n);
    Arrays.sort(all);
    all = Arrays.stream(all).distinct().toArray();
    id = new HashMap<>();
    for (int i = 0; i < all.length; ++i) id.put(all[i], i);
    for (int i = 0; i < n; ++i) a[i] = id.get(a[i]);
    o = new Fenwick<>(all.length, new Opt());
    q = new pair[n];
    for (int i = 0; i < n; ++i) {
      q[i] = new pair<>(a[i], Math.max(0, o.prod(all.length - 1) - o.prod(a[i]) - k));
      o.apply(a[i], 1);
    }
    Arrays.sort(q, Comparator.reverseOrder());
    TNode root = null;
    for (int i = 0; i < n; ++i) root = insert(root, q[i].y, q[i].x);
    inorder(root);
    bin.println();
    return 0;
  }

  public static class Opt implements Fen_Opt<Integer> {
    public Integer op(Integer a, Integer b) { return a + b; }
    public Integer e() { return 0; }
  }

  public static void main(String[] args) {
    int t = 1;
    if (MULTI_TESTS && !SPECIAL_TESTS) t = bin.Int();
    for (int i = 1; i <= t || SPECIAL_TESTS; ++i)
      if (ENGINE(i) != 0) break;
    bin.close();
  }

  static {
    try {
      bin = new Bin();
    } catch (IOException e) { throw new RuntimeException(e); }
  }

  static final class pair<Ty1 extends Comparable<Ty1>, Ty2 extends Comparable<Ty2>>
    implements Comparable<pair<Ty1, Ty2>> {
    public Ty1 x;
    public Ty2 y;

    public pair() {}

    public pair(Ty1 a, Ty2 b) {
      x = a;
      y = b;
    }

    public int compareTo(pair<Ty1, Ty2> c) {
      if (x.compareTo(c.x) != 0) return x.compareTo(c.x);
      return y.compareTo(c.y);
    }
  }

  static final class Bin extends PrintWriter {
    private final BufferedReader in;
    private StringTokenizer token;
    public Bin() throws IOException { this(System.in, System.out); }
    public int Int() { return Integer.parseInt(next()); }
    public double Double() { return Double.parseDouble(next()); }
    public long Long() { return Long.parseLong(next()); }
    public BigInteger Big() { return new BigInteger(next()); }
    public BigDecimal BigDecimal() { return new BigDecimal(next()); }

    public Bin(InputStream input, OutputStream output) throws IOException {
      super(output);
      in = new BufferedReader(new InputStreamReader(input));
    }

    public Bin(String input, String output) throws IOException {
      super(output);
      in = new BufferedReader(new FileReader(input));
    }

    public String next() {
      try {
        while (token == null || !token.hasMoreTokens()) token = new StringTokenizer(in.readLine());
        return token.nextToken();
      } catch (Exception e) { return null; }
    }
  }

  public static class Fenwick<Ty, Opt extends Fen_Opt<Ty>> {
    private Object[] data;
    private int n;
    private Opt o;

    public Fenwick(int n, Opt op) {
      data = new Object[n];
      this.n = n;
      o = op;
      Arrays.fill(data, o.e());
    }

    void apply(int x, Ty v) {
      while (x < n) {
        data[x] = o.op((Ty)data[x], v);
        x |= x + 1;
      }
    }

    Ty prod(int x) {
      Ty e = o.e();
      ++x;
      while (x > 0) {
        e = o.op(e, (Ty)data[x - 1]);
        x &= x - 1;
      }
      return e;
    }
  }

  public interface Fen_Opt<Ty> {
    Ty op(Ty a, Ty b);
    Ty e();
  }
}

Besides, we can solve this problem in another simple way.

We can imagine doing $k$ bubble sort rounds in parallel. This means we only maintain the values of first $k$ largest elements.

Code

// rbtree (https://rbtr.ee)
// n@rbtr.ee
import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;

public class Main {
  static final boolean MULTI_TESTS = false;
  static final boolean SPECIAL_TESTS = false;
  static final Bin bin;
  static final int INF32 = 1073741823;
  static final long INF64 = 4611686018427387903L;
  static final Random rng = new Random();

  static int n, k;
  static int[] a;
  static PriorityQueue<Integer> q;

  public static int ENGINE(int TEST_NUMBER) {
    n = bin.Int();
    k = bin.Int();
    a = new int[n];
    for (int i = 0; i < n; ++i) a[i] = bin.Int();
    q = new PriorityQueue<>();
    for (int i = 0; i < n; ++i) {
      q.add(a[i]);
      if (q.size() > k) {
        bin.print(q.poll());
        bin.print(' ');
      }
    }
    while (!q.isEmpty()) {
      bin.print(q.poll());
      bin.print(' ');
    }
    bin.println();
    return 0;
  }

  public static class Opt implements Fen_Opt<Integer> {
    public Integer op(Integer a, Integer b) { return a + b; }
    public Integer e() { return 0; }
  }

  public static void main(String[] args) {
    int t = 1;
    if (MULTI_TESTS && !SPECIAL_TESTS) t = bin.Int();
    for (int i = 1; i <= t || SPECIAL_TESTS; ++i)
      if (ENGINE(i) != 0) break;
    bin.close();
  }

  static {
    try {
      bin = new Bin();
    } catch (IOException e) { throw new RuntimeException(e); }
  }

  static final class pair<Ty1 extends Comparable<Ty1>, Ty2 extends Comparable<Ty2>>
    implements Comparable<pair<Ty1, Ty2>> {
    public Ty1 x;
    public Ty2 y;

    public pair() {}

    public pair(Ty1 a, Ty2 b) {
      x = a;
      y = b;
    }

    public int compareTo(pair<Ty1, Ty2> c) {
      if (x.compareTo(c.x) != 0) return x.compareTo(c.x);
      return y.compareTo(c.y);
    }
  }

  static final class Bin extends PrintWriter {
    private final BufferedReader in;
    private StringTokenizer token;
    public Bin() throws IOException { this(System.in, System.out); }
    public int Int() { return Integer.parseInt(next()); }
    public double Double() { return Double.parseDouble(next()); }
    public long Long() { return Long.parseLong(next()); }
    public BigInteger Big() { return new BigInteger(next()); }
    public BigDecimal BigDecimal() { return new BigDecimal(next()); }

    public Bin(InputStream input, OutputStream output) throws IOException {
      super(output);
      in = new BufferedReader(new InputStreamReader(input));
    }

    public Bin(String input, String output) throws IOException {
      super(output);
      in = new BufferedReader(new FileReader(input));
    }

    public String next() {
      try {
        while (token == null || !token.hasMoreTokens()) token = new StringTokenizer(in.readLine());
        return token.nextToken();
      } catch (Exception e) { return null; }
    }
  }

  public static class Fenwick<Ty, Opt extends Fen_Opt<Ty>> {
    private Object[] data;
    private int n;
    private Opt o;

    public Fenwick(int n, Opt op) {
      data = new Object[n];
      this.n = n;
      o = op;
      Arrays.fill(data, o.e());
    }

    void apply(int x, Ty v) {
      while (x < n) {
        data[x] = o.op((Ty)data[x], v);
        x |= x + 1;
      }
    }

    Ty prod(int x) {
      Ty e = o.e();
      ++x;
      while (x > 0) {
        e = o.op(e, (Ty)data[x - 1]);
        x &= x - 1;
      }
      return e;
    }
  }

  public interface Fen_Opt<Ty> {
    Ty op(Ty a, Ty b);
    Ty e();
  }
}

No comments

Post a comment