Help with 2123F

Revision en2, by _cerealsoup, 2025-07-02 17:00:43

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.

Tags help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English _cerealsoup 2025-07-02 17:00:43 43 Tiny change: '94692]\n\nCleane' -> '94692]\n\nI wasn't expecting an AC but it passes.\n\nCleane'
en1 English _cerealsoup 2025-07-02 16:57:26 827 Initial revision (published)