fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. int main() {
  6.     ll n, k;
  7.     cin >> n >> k;
  8.  
  9.     vector<ll> b(n);
  10.     vector<unordered_map<ll, ll>> g(k); // Stores frequency per group
  11.  
  12.     // Read input and store frequency in groups
  13.     for (ll i = 0; i < n; i++) {
  14.         cin >> b[i];
  15.         g[i % k][b[i]]++;
  16.     }
  17.  
  18.     // DP table: dp[i][goal_xor] -> Min cost to achieve `goal_xor` after `i` groups
  19.     vector<vector<ll>> dp(k + 1, vector<ll>(64, LLONG_MAX));
  20.  
  21.     // Base case: When all `k` groups are processed, `goal_xor == 0` must have cost `0`
  22.     dp[k][0] = 0;
  23.  
  24.     // Iterate over groups in reverse order
  25.     for (ll i = k - 1; i >= 0; i--) {
  26.         for (ll goal_xor = 0; goal_xor < 64; goal_xor++) {
  27.             ll total =1+ (n - i - 1) / k; // Total elements in this group
  28.  
  29.             for (ll last_element = 0; last_element < 64; last_element++) {
  30.                 if (dp[i + 1][goal_xor ^ last_element] == LLONG_MAX) continue; // Skip invalid states
  31.  
  32.                 // Compute the number of changes required
  33.                 ll freq = g[i].count(last_element) ? g[i][last_element] : 0;
  34.                 ll change_cost = total - freq;
  35.  
  36.                 // Transition to the next DP state
  37.                 dp[i][goal_xor] = min(dp[i][goal_xor], dp[i + 1][goal_xor ^ last_element] + change_cost);
  38.             }
  39.         }
  40.     }
  41.  
  42.     // Output the minimum number of replacements needed to get XOR = 0
  43.     cout << dp[0][0] << endl;
  44.  
  45.     return 0;
  46. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
3
1 
2
3
4
stdout
copy 
1
https://ideone.com/5ZyyX1
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!