_cerealsoup's blog

By _cerealsoup, history, 17 months ago, In English

I was upsolving 2123F - Minimize Fixed Points from yesterday's contest.

This is my submission: 327094692

I wasn't expecting an AC but it passes.

Cleaned up code:

constexpr int N = 2e5 + 10;
int lf[N]; // largest factor

void precompute() {
  lf[1] = 1;
  for (int i = 2; i < N; i += 1) {
    if (lf[i]) continue;
    for (int j = i; j < N; j += i) lf[j] = i;
  }
}

void solve() {
  int n;
  cin >> n;

  vector<int> ans(n + 1);
  iota(all(ans), 0);

  // maintain gcd property at all times and only check for fixed points
  for (int i = n; i > 1; i -= 1) {
    swap(ans[lf[i]], ans[i]);
  }

  for (int i = 1; i <= n; i += 1) cout << ans[i] << " ";
  cout << endl;
}

It simply swaps out each number with its largest factor.

I'm struggling to prove if (and why) this would work every time though.

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?