Equalizing Card Piles (Greedy Approach)

To distribute cards equally among $N$ piles, calculate the average number of cards per pile and subtract this value from each pile's count. This transforms the problem into finding the minimum number of moves to zero out the differences. Iterating from left to right, if a pile has a non-zero discrpeancy, "shift" that difference to the adjacent pile and increment the operation count.

#include <iostream>
#include <vector>

int main() {
   int n;
   std::cin >> n;
   std::vector<long long> piles(n);
   long long total = 0;
   for (auto &x : piles) {
       std::cin >> x;
       total += x;
   }
   long long avg = total / n;
   for (auto &x : piles) x -= avg;

   int moves = 0;
   for (int i = 0; i < n - 1; ++i) {
       if (piles[i] != 0) {
           piles[i + 1] += piles[i];
           moves++;
       }
   }
   std::cout << moves << std::endl;
   return 0;
}

Prime Selection (Backtracking)

When selecting $K$ integers from a set to reach a prime sum, a Depth First Search (DFS) approach is effective. The state tracks current index, count of selected numbers, and the runing total.

#include <iostream>
#include <vector>
#include <cmath>

bool is_prime(int n) {
   if (n < 2) return false;
   for (int i = 2; i * i <= n; ++i)
       if (n % i == 0) return false;
   return true;
}

void find_combinations(int idx, int count, int current_sum, int k, const std::vector<int>& nums, int& result) {
   if (count == k) {
       if (is_prime(current_sum)) result++;
       return;
   }
   for (int i = idx; i < nums.size(); ++i) {
       find_combinations(i + 1, count + 1, current_sum + nums[i], k, nums, result);
   }
}

0/1 Knapsack Optimization

Standard dynamic programming for the 0/1 knapsack problem uses a 1D array to reduce space complexity, iterating backwards to ensure each item is used at most once.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
   int capacity, count;
   std::cin >> capacity >> count;
   std::vector<long long> dp(capacity + 1, 0);
   for (int i = 0; i < count; ++i) {
       int weight, value;
       std::cin >> weight >> value;
       for (int j = capacity; j >= weight; --j) {
           dp[j] = std::max(dp[j], dp[j - weight] + (long long)weight * value);
       }
   }
   std::cout << dp[capacity] << std::endl;
   return 0;
}

Bitwise Swap

To swap the upper and lower 16 bits of a 32-bit integer, use bitwice shifts and masks.

#include <iostream>

int main() {
   unsigned int n;
   std::cin >> n;
   unsigned int lower = n & 0xFFFF;
   unsigned int upper = n >> 16;
   std::cout << (lower << 16) | upper << std::endl;
   return 0;
}

Frequency Counting

Utilizing a balanced binary search tree (like std::map in C++) allows for efficient frequency counting with automatic sorting of keys.

#include <iostream>
#include <map>

int main() {
   int n, val;
   std::cin >> n;
   std::map<int, int> freq;
   while (n--) {
       std::cin >> val;
       freq[val]++;
   }
   for (auto const& [key, count] : freq) {
       std::cout << key << " " << count << std::endl;
   }
   return 0;
}