This document provides solutions for problems from the SMU Summer 2023 Contest, Round 6.
A. Burger Optimization
This problem involves maximizing profit from selling two types of burgers with different ingredients and prices, given a limited number of buns. The strategy is to iterate through all possible counts of the first burger type, up to the maximum that can be made with the available buns and the quantity of its key ingredient. For each count of the first burger, we calculate the maximum number of the second burger that can be made with the remaining buns and ingredients, and then determine the total profit. The overall maximum profit found is the answer.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long buns, burger1_count, burger2_count, burger1_price, burger2_price;
cin >> buns >> burger1_count >> burger2_count >> burger1_price >> burger2_price;
long long max_profit = 0;
// Iterate through possible counts of the first burger type
// The number of first burgers cannot exceed half the available buns
// and cannot exceed the available count of its key ingredient.
for (long long i = 0; i <= min(buns / 2, burger1_count); ++i) {
long long remaining_buns = buns - (i * 2);
// Calculate the maximum count of the second burger with remaining buns
long long current_profit = i * burger1_price + min(remaining_buns / 2, burger2_count) * burger2_price;
max_profit = max(max_profit, current_profit);
}
cout << max_profit << endl;
}
return 0;
}
</vector></algorithm></iostream>
B. Grid Filling with 2x2 Squares
The problem requires determining if a target grid A can be formed by filling a grid B (initially all zeros) using 2x2 squares of ones. If possible, we need to output the number of 2x2 squares used and their top-left corner coordinates. The approach is to scan the target grid A to identify all valid 2x2 squares of ones. Whenever a 2x2 square of ones is found in A, we mark the corresponding 2x2 area in B with ones and record the coordinates of the top-left corner of this square. After identifying all such squares, we compare the modified grid B with the original grid A. If they are identical, the solution is valid; otherwise, it's impossible to form A using the given operation.
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int int=""> Coordinates;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector>> target_grid(n, vector<int>(m, 0));
vector<vector>> constructed_grid(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> target_grid[i][j];
}
}
// If the target grid is already all zeros, no operations are needed.
bool all_zeros = true;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if (target_grid[i][j] == 1) {
all_zeros = false;
break;
}
}
if (!all_zeros) break;
}
if (all_zeros) {
cout << 0 << endl;
return 0;
}
vector<coordinates> square_positions;
// Iterate through the grid to find 2x2 squares of ones.
// Start from index 1 to allow checking previous elements.
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
// Check if a 2x2 square of ones exists starting from (i-1, j-1) in target_grid
if (target_grid[i][j] == 1 &&
target_grid[i - 1][j] == 1 &&
target_grid[i][j - 1] == 1 &&
target_grid[i - 1][j - 1] == 1)
{
// Mark the corresponding 2x2 area in constructed_grid
constructed_grid[i - 1][j - 1] = 1;
constructed_grid[i - 1][j] = 1;
constructed_grid[i][j - 1] = 1;
constructed_grid[i][j] = 1;
// Record the top-left corner of the square (0-indexed adjusted)
square_positions.push_back({i - 1, j - 1});
}
}
}
// Check if the constructed grid matches the target grid.
if (target_grid != constructed_grid) {
cout << -1 << endl;
} else {
cout << square_positions.size() << endl;
for (const auto& pos : square_positions) {
// Output coordinates are 1-indexed as per common contest problem statements.
cout << pos.first + 1 << ' ' << pos.second + 1 << endl;
}
}
return 0;
}
</coordinates></int></vector></int></vector></int></utility></vector></iostream>
C. Gas Pipeline Dynamics
This problem can be solved using dynamic programming. Let dp\[i\]\[0\] represent the minimum cost to build a pipeline up to segment i where the pipe at segment i is at ground level (low). Let dp\[i\]\[1\] represent the minimum cost when the pipe at segment i is elevated (high). The transition depends on the type of terrain at segment i ('0' for normal, '1' for an intersection, which implies an elevated pipe). When the terrain is '1' (intersection), the pipe must be elevated. The cost to reach dp\[i\]\[1\] from dp\[i-1\]\[1\] involves moving to the next segment (cost a), building the elevated pipe (cost 2\*b), and passing through the intersection (cost b). When the terrain is '0' (normal), the pipe can be either low or high. To reach dp\[i\]\[0\] (low pipe at segment i): - From dp\[i-1\]\[0\] (low pipe at i-1): Cost is a (move) + b (low pipe). - From dp\[i-1\]\[1\] (high pipe at i-1): Cost is a (move) + a (descend) + b (low pipe). To reach dp\[i\]\[1\] (high pipe at segment i): - From dp\[i-1\]\[0\] (low pipe at i-1): Cost is a (move) + b (ascend) + 2\*b (high pipe). - From dp\[i-1\]\[1\] (high pipe at i-1): Cost is a (move) + 2\*b (high pipe). The base case is dp\[0\]\[0\] = b, representing the initial cost to have a ground-level segment before the first segment, assuming the pipeline starts at ground level. The final answer is dp\[n\]\[0\] since the problem requires the pipeline to end at ground level.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, cost_move, cost_low, cost_high;
string terrain_str;
cin >> n >> cost_move >> cost_low >> cost_high;
cin >> terrain_str;
// Add a dummy character at the beginning for 1-based indexing convenience
terrain_str = " " + terrain_str;
// dp[i][0]: min cost to reach segment i with a low pipe
// dp[i][1]: min cost to reach segment i with a high pipe
vector<vector long="">> dp(n + 1, vector<long long="">(2, INF));
// Base case: Before the first segment, assume a low pipe with initial cost.
// The cost 'b' is for passing through the initial segment.
dp[0][0] = cost_high; // Initial cost to be at ground level before starting.
for (int i = 1; i <= n; ++i) {
if (terrain_str[i] == '1') { // Intersection: must be high
// Transition from previous high pipe to current high pipe
// Cost: move (a) + maintain high (2*b)
dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost_move + 2 * cost_high);
} else { // Normal terrain: can be low or high
// Transition to current low pipe (dp[i][0]):
// From previous low pipe: move (a) + build low (b)
dp[i][0] = min(dp[i][0], dp[i - 1][0] + cost_move + cost_low);
// From previous high pipe: move (a) + descend (a) + build low (b)
dp[i][0] = min(dp[i][0], dp[i - 1][1] + 2 * cost_move + cost_low);
// Transition to current high pipe (dp[i][1]):
// From previous low pipe: move (a) + ascend (b) + build high (2*b)
dp[i][1] = min(dp[i][1], dp[i - 1][0] + cost_move + cost_low + 2 * cost_high);
// From previous high pipe: move (a) + maintain high (2*b)
dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost_move + 2 * cost_high);
}
}
// The final answer is the minimum cost to reach the last segment at ground level.
cout << dp[n][0] << endl;
}
return 0;
}
</long></vector></algorithm></string></vector></iostream>
D. Permutation Counting with Constraints
This problem asks for the number of permutations of length n such that there are no two adjacent elements (x\_i, y\_i) and (x\_{i+1}, y\_{i+1}) where both x\_i <= x\_{i+1} and y\_i <= y\_{i+1}. Directly counting this is difficult. Instead, we use the principle of inclusion-exclusion. The total number of permutations is n!. We subtract permutations where the first condition (x\_i <= x\_{i+1}) holds for at least one pair, and permutations where the second condition (y\_i <= y\_{i+1}) holds for at least one pair. We then add back permutations where both conditions hold simultaneously for at least one pair to correct for double-counting. The number of permutations where the first components are in non-decreasing order can be calculated. Similarly, for the second components. If a permutation satisfies both non-decreasing conditions for the first and second components simultaneously, it means the pairs (x\_i, y\_i) are also non-decreasing in both components. This happens when the sequence of pairs, when sorted by the first component, is also sorted by the second component. We calculate these counts using factorials of the frequencies of identical elements.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int int=""> Pair;
const int MOD = 998244353;
// Precompute factorials
vector<long long=""> factorials;
void precompute_factorials(int max_n) {
factorials.resize(max_n + 1);
factorials[0] = 1;
for (int i = 1; i <= max_n; ++i) {
factorials[i] = (factorials[i - 1] * i) % MOD;
}
}
// Function to calculate modular exponentiation (for modular inverse if needed, though not directly here)
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
// Function to calculate combinations (nCr) if needed
// long long modInverse(long long n) {
// return power(n, MOD - 2);
// }
//
// long long nCr_mod_p(int n, int r) {
// if (r < 0 || r > n) return 0;
// if (r == 0 || r == n) return 1;
// if (factorials[r] == 0 || factorials[n - r] == 0) return 0; // Avoid division by zero if precomputation failed
// return (((factorials[n] * modInverse(factorials[r])) % MOD) * modInverse(factorials[n - r])) % MOD;
// }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
precompute_factorials(n);
vector<pair> pairs(n);
map<int int=""> freq1, freq2;
bool possible = true;
for (int i = 0; i < n; ++i) {
cin >> pairs[i].first >> pairs[i].second;
freq1[pairs[i].first]++;
freq2[pairs[i].second]++;
}
// Check if any element appears n times in either dimension, making it impossible
for (int i = 1; i <= n; ++i) { // Assuming values are within 1 to n range, adjust if not.
if (freq1.count(i) && freq1[i] == n) { possible = false; break; }
if (freq2.count(i) && freq2[i] == n) { possible = false; break; }
}
// A more robust check if values are not restricted to 1..n
for(auto const& [val, count] : freq1) {
if (count == n) { possible = false; break; }
}
if (possible) {
for(auto const& [val, count] : freq2) {
if (count == n) { possible = false; break; }
}
}
if (!possible) {
cout << 0 << endl;
return 0;
}
// Calculate permutations where first components are non-decreasing
long long non_decreasing_x = 1;
for (auto const& [val, count] : freq1) {
non_decreasing_x = (non_decreasing_x * factorials[count]) % MOD;
}
// Calculate permutations where second components are non-decreasing
long long non_decreasing_y = 1;
for (auto const& [val, count] : freq2) {
non_decreasing_y = (non_decreasing_y * factorials[count]) % MOD;
}
// Total permutations - (non-decreasing x + non-decreasing y) + (both non-decreasing)
long long total_permutations = factorials[n];
long long base_subtraction = (non_decreasing_x + non_decreasing_y) % MOD;
// Check for permutations where both x and y are non-decreasing simultaneously
sort(pairs.begin(), pairs.end());
bool both_non_decreasing_possible = true;
for (int i = 1; i < n; ++i) {
// If the pairs sorted by x are also sorted by y, then this case is possible.
if (pairs[i].second < pairs[i - 1].second) {
both_non_decreasing_possible = false;
break;
}
}
if (both_non_decreasing_possible) {
// Calculate permutations where both x and y are non-decreasing
map<pair int=""> freq_both;
for (const auto& p : pairs) {
freq_both[p]++;
}
long long both_non_decreasing_count = 1;
for (auto const& [p, count] : freq_both) {
both_non_decreasing_count = (both_non_decreasing_count * factorials[count]) % MOD;
}
// Result = Total - (count_x + count_y) + count_both
long long final_ans = (total_permutations - base_subtraction + MOD) % MOD;
final_ans = (final_ans + both_non_decreasing_count) % MOD;
cout << final_ans << endl;
} else {
// Result = Total - (count_x + count_y)
long long final_ans = (total_permutations - base_subtraction + MOD) % MOD;
cout << final_ans << endl;
}
return 0;
}
</pair></int></pair></long></int></map></algorithm></vector></iostream>
E. XOR Guessing (Interactive)
This is an interactive problem. We need to guess a hidden integer x within the range [0, 214 - 1]. The strategy involves two queries. In the first query, we send numbers from 1 to 100. The returned value res1 will be the XOR sum of x with each of these numbers. Since x is less than 214, its first 7 bits are independent of the higher bits if we consider numbers up to 100 (which are less then 27). Thus, res1 will essentially reveal the higher 7 bits of x. In the second query, we send numbers from 1 to 100, each left-shifted by 7 bits (i.e., i << 7). The returned value res2 will be the XOR sum of x with these shifted numbers. This res2 will reveal the lower 7 bits of x. By combining the higher 7 bits from res1 and the lower 7 bits from res2, we can reconstruct the value of x.
#include <iostream>
#include <vector>
#include <numeric> // For std::iota if needed, but manual loop is fine
using namespace std;
int main() {
// No need for fast I/O for interactive problems usually
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
int response1, response2;
// First query: XOR with numbers 1 to 100
cout << "?";
for (int i = 1; i <= 100; ++i) {
cout << " " << i;
}
cout << endl;
cin >> response1;
// Second query: XOR with numbers (1 << 7) to (100 << 7)
cout << "?";
for (int i = 1; i <= 100; ++i) {
cout << " " << (i << 7); // Left shift by 7 bits
}
cout << endl;
cin >> response2;
int guessed_x = 0;
// Extract the lower 7 bits of x from response2
// response2 = x ^ (1<<7) ^ (2<<7) ^ ... ^ (100<<7)
// response2 = x ^ ((1^2^...^100) << 7)
// The lower 7 bits of response2 are essentially the lower 7 bits of x
// because the lower 7 bits of (k << 7) are always 0.
int lower_7_bits_mask = (1 << 7) - 1; // Mask for 7 bits (0b1111111)
guessed_x |= (response2 & lower_7_bits_mask);
// Extract the higher 7 bits of x from response1
// response1 = x ^ 1 ^ 2 ^ ... ^ 100
// The higher 7 bits of response1 are essentially the higher 7 bits of x
// because the numbers 1 to 100 have their higher 7 bits as 0.
int higher_7_bits_mask = ((1 << 7) - 1) << 7; // Mask for bits 7 through 13
guessed_x |= (response1 & higher_7_bits_mask);
// Output the final guessed value
cout << "! " << guessed_x << endl;
return 0;
}
</numeric></vector></iostream>
F. Remainder Problem with Square Root Decomposition
This problem involves two types of operations on an array a. Operation 1 updates an element a\[x\] by adding y. Operation 2 queries the sum of elements in a that have a remainder y when divided by x. To optimize this, we use square root decomposition. We choose a threshold N (around sqrt(max\_array\_size)). For Operation 1 (update a\[x\] by y): - If x < N, we update a\[x\] and also update precomputed sums for all remainders i from 1 to N-1: sum\[i\]\[x % i\] += y. - If x >= N, we only update a\[x\]. The precomputed sum are not affected as they only cover small moduli. For Operation 2 (query sum with remainder y modulo x): - If x < N, we can directly retrieve the precomputed sum: sum\[x\]\[y\]. This is fast. - If x >= N, the modulus x is large. We cannot rely on precomputed sums for all possible large x. Instead, we iterate through the array a starting from index y with a step of x (y, y+x, y+2x, ...) and sum the values directly. This is a brute-force approach for large moduli. The time complexity for each operation is approximately O(max(N, max\_array\_size / N)). By setting N = sqrt(max\_array\_size), the complexity becomes O(sqrt(max\_array\_size)) per operation. The total time complexity for q queries is O(q \* sqrt(max\_array\_size)). The chosen N is 750, which is close to sqrt(500000).
#include <iostream>
#include <vector>
#include <cmath> // For sqrt
using namespace std;
// Define the block size for square root decomposition
// Typically chosen as sqrt of the maximum possible array index or problem constraints.
// sqrt(500000) is approx 707. Using 750 is a common choice.
const int BLOCK_SIZE = 750;
const int MAX_VAL = 500000; // Maximum possible value in the array
// Array to store the actual values. Its size should cover the maximum possible index.
// The problem statement doesn't specify the max index, assuming it's related to MAX_VAL.
// If indices can be larger, this needs adjustment.
int data_array[MAX_VAL + 1]; // Use 1-based indexing implicitly or adjust size
// Precomputed sums: sum[block_modulus][remainder]
// block_modulus ranges from 1 to BLOCK_SIZE - 1
// remainder ranges from 0 to block_modulus - 1
int prefix_sums[BLOCK_SIZE][BLOCK_SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int operation_type, x_val, y_val;
cin >> operation_type >> x_val >> y_val;
if (operation_type == 1) { // Update operation
// Update the actual value in the array
data_array[x_val] += y_val;
// Update precomputed sums for all moduli smaller than BLOCK_SIZE
// The remainder changes for each modulus i
for (int i = 1; i < BLOCK_SIZE; ++i) {
prefix_sums[i][x_val % i] += y_val;
}
} else { // Query operation
if (x_val < BLOCK_SIZE) {
// If the modulus x is small, use the precomputed sum
// The remainder is y_val
cout << prefix_sums[x_val][y_val] << '\n';
} else {
// If the modulus x is large, iterate and sum directly
int current_sum = 0;
// Start from y_val and step by x_val
for (int i = y_val; i <= MAX_VAL; i += x_val) {
current_sum += data_array[i];
}
cout << current_sum << '\n';
}
}
}
return 0;
}
</cmath></vector></iostream>
dynamic programming,greedy,combinatorics,inclusion-exclusion,square root decomposition,interactive problems,number theory