This document details the solutions for problems from Codeforces Educational Round 166 (Rated for Div. 2).
A. Verify Password
The problem requires validating a password string based on specific criteria. The approach involves iterating through the password and checking adjacent character pairs against the rules. A password is valid if it adheres to all conditions, and invalid otherwise.
#include <cstdio>
#include <cstring>
#include <cctype> // For isdigit and islower
int T; // Number of test cases
int passwordLength; // Length of the password
char password[25]; // Password string storage
// Helper function to check if a character is a digit
bool is_digit(char ch) {
return std::isdigit(static_cast<unsigned char="">(ch));
}
// Helper function to check if a character is a lowercase letter
bool is_lowercase(char ch) {
return std::islower(static_cast<unsigned char="">(ch));
}
// Function to validate the password according to the rules
bool validatePassword() {
// Iterate through adjacent character pairs
for (int i = 0; i < passwordLength - 1; ++i) {
// Rule 1: Cannot have a lowercase letter followed by a digit
if (is_lowercase(password[i]) && is_digit(password[i + 1])) {
return false;
}
// Rule 2: If two consecutive lowercase letters, the first must not be greater than the second
if (is_lowercase(password[i]) && is_lowercase(password[i + 1]) && password[i] > password[i + 1]) {
return false;
}
// Rule 3: If two consecutive digits, the first must not be greater than the second
if (is_digit(password[i]) && is_digit(password[i + 1]) && password[i] > password[i + 1]) {
return false;
}
}
// If all checks pass, the password is valid
return true;
}
int main() {
scanf("%d", &T); // Read the number of test cases
while (T--) {
scanf("%d%s", &passwordLength, password); // Read password length and string
printf("%s\n", validatePassword() ? "YES" : "NO"); // Print result
}
return 0;
}
</unsigned></unsigned></cctype></cstring></cstdio>
B. Increase/Decrease/Copy
This problem involves transforming array 'a' into array 'b', where 'b' has one more element than 'a'. The allowed operations are increment, decrement, and copy. Since 'b' is only one element longer, the 'copy' operation will be used at most once. The solution considers two main scenarios:
- The transformation path from
a\[i\]tob\[i\]includesb\[n+1\]. In this case, only one 'copy' operation is needed in addition to increments/decrements. - The transformation path does not include
b\[n+1\]. In this scenario,b\[n+1\]must be formed by transforming one of the existing elements (a\[i\]orb\[i\]). The optimal strategy is to choose the element closest tob\[n+1\]. The initial thought might be to use global minimum/maximum values, but it's crucial to consider local minimum/maximum differences with in each pair transformation.
#include <cstdio>
#include <cmath>
#include <algorithm>
#define int long long // Use long long for potentially large sums
using namespace std;
const int MAX_SIZE = 1e6 + 5;
int T; // Number of test cases
int n; // Size of array a
int arrA[MAX_SIZE]; // Array a
int arrB[MAX_SIZE]; // Array b
signed main() {
scanf("%lld", &T); // Read the number of test cases
while (T--) {
scanf("%lld", &n); // Read the size of array a
for (int i = 1; i <= n; ++i) scanf("%lld", &arrA[i]); // Read elements of array a
for (int i = 1; i <= n + 1; ++i) scanf("%lld", &arrB[i]); // Read elements of array b
long long totalOperations = 0;
bool targetB_inRange = false; // Flag to check if b[n+1] falls within any [min(a_i, b_i), max(a_i, b_i)] range
// Calculate operations for the first n elements and check range for b[n+1]
for (int i = 1; i <= n; ++i) {
int valA = arrA[i];
int valB = arrB[i];
// Ensure valA <= valB for range checking
if (valA > valB) std::swap(valA, valB);
totalOperations += valB - valA; // Add difference (increment/decrement operations)
// Check if the target element b[n+1] is within the current transformation range
if (valA <= arrB[n + 1] && arrB[n + 1] <= valB) {
targetB_inRange = true;
}
}
totalOperations++; // Account for the mandatory copy operation
// If b[n+1] was not within any of the [min(a_i, b_i), max(a_i, b_i)] ranges
if (!targetB_inRange) {
int minExtraOps = 0x3f3f3f3f; // Initialize with a large value for minimum tracking
// Find the minimum operations to transform an existing element to b[n+1]
for (int i = 1; i <= n; ++i) {
int valA = arrA[i];
int valB = arrB[i];
// Ensure valA <= valB for range checking
if (valA > valB) std::swap(valA, valB);
// If b[n+1] is less than the minimum of the range
if (arrB[n + 1] < valA) {
minExtraOps = std::min(minExtraOps, valA - arrB[n + 1]);
}
// If b[n+1] is greater than the maximum of the range
if (arrB[n + 1] > valB) {
minExtraOps = std::min(minExtraOps, arrB[n + 1] - valB);
}
}
totalOperations += minExtraOps; // Add the minimum extra operations
}
printf("%lld\n", totalOperations); // Print the total operations
}
return 0;
}
</algorithm></cmath></cstdio>
C. Job Interview
This problem involves selecting candidates for programmer and tester roles to maximize total salary, with constraints on the number of programmers (n) and testers (m). A key challenge is handling prefix sums and efficiently querying ranges. The solution uses binary search to determine the split point where one role's requirement is met, and then calculates the total salary based on the remaining candidates and their salaries. A crucial detail is remembering to use long long for sums to prevent overflow.
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_CANDIDATES = 2e5 + 5;
int T; // Number of test cases
int numProgrammersRequired; // Required number of programmers
int numTestersRequired; // Required number of testers
int programmerSalaries[MAX_CANDIDATES]; // Salaries of candidates if assigned as programmers
int testerSalaries[MAX_CANDIDATES]; // Salaries of candidates if assigned as testers
long long prefixSumProgrammer[MAX_CANDIDATES]; // Prefix sums for programmer salaries
long long prefixSumTester[MAX_CANDIDATES]; // Prefix sums for tester salaries
long long prefixSumBestChoice[MAX_CANDIDATES]; // Prefix sums for the best salary (max(prog_salary, test_salary))
int countProgrammer[MAX_CANDIDATES]; // Cumulative count of candidates better suited as programmers
int countTester[MAX_CANDIDATES]; // Cumulative count of candidates better suited as testers
// Helper function to get sum of a range from prefix sums
long long getRangeSum(long long prefixSum[], int left, int right) {
if (left > right) return 0;
return prefixSum[right] - prefixSum[left - 1];
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &numProgrammersRequired, &numTestersRequired);
int totalCandidates = numProgrammersRequired + numTestersRequired + 1;
// Read salaries and compute prefix sums
for (int i = 1; i <= totalCandidates; ++i) {
scanf("%d", &programmerSalaries[i]);
prefixSumProgrammer[i] = prefixSumProgrammer[i - 1] + programmerSalaries[i];
}
for (int i = 1; i <= totalCandidates; ++i) {
scanf("%d", &testerSalaries[i]);
prefixSumTester[i] = prefixSumTester[i - 1] + testerSalaries[i];
}
// Calculate counts and prefix sums for the best choice salary
for (int i = 1; i <= totalCandidates; ++i) {
countProgrammer[i] = countProgrammer[i - 1];
countTester[i] = countTester[i - 1];
if (programmerSalaries[i] > testerSalaries[i]) { // Candidate is better as a programmer
countProgrammer[i]++;
prefixSumBestChoice[i] = prefixSumBestChoice[i - 1] + programmerSalaries[i];
} else if (programmerSalaries[i] < testerSalaries[i]) { // Candidate is better as a tester
countTester[i]++;
prefixSumBestChoice[i] = prefixSumBestChoice[i - 1] + testerSalaries[i];
} else { // Salaries are equal, pick one (e.g., programmer)
countProgrammer[i]++; // Arbitrarily count towards programmer for consistency
prefixSumBestChoice[i] = prefixSumBestChoice[i - 1] + programmerSalaries[i];
}
}
// Iterate through each candidate to calculate the maximum possible salary if they are excluded
for (int excludedCandidateIndex = 1; excludedCandidateIndex <= totalCandidates; ++excludedAuxiliaryIndex) {
int low = 0, high = totalCandidates + 1; // Binary search range for split point
// Binary search to find the point where programmer requirement is met
while (low + 1 < high) {
int mid = low + (high - low) / 2;
int currentProgrammers = countProgrammer[mid];
// Exclude the current candidate if they are considered within the 'mid' range and better suited as a programmer
if (programmerSalaries[excludedCandidateIndex] > testerSalaries[excludedCandidateIndex] && excludedCandidateIndex <= mid) {
currentProgrammers--;
}
if (currentProgrammers <= numProgrammersRequired) {
low = mid;
} else {
high = mid;
}
}
int programmerSplitPoint = low;
low = 0, high = totalCandidates + 1; // Reset binary search range
// Binary search to find the point where tester requirement is met
while (low + 1 < high) {
int mid = low + (high - low) / 2;
int currentTesters = countTester[mid];
// Exclude the current candidate if they are considered within the 'mid' range and better suited as a tester
if (programmerSalaries[excludedCandidateIndex] < testerSalaries[excludedCandidateIndex] && excludedCandidateIndex <= mid) {
currentTesters--;
}
if (currentTesters <= numTestersRequired) {
low = mid;
} else {
high = mid;
}
}
int testerSplitPoint = low;
long long currentTotalSalary = 0;
// Case 1: Programmers are filled first
if (programmerSplitPoint < testerSplitPoint) {
currentTotalSalary = getRangeSum(prefixSumBestChoice, 1, programmerSplitPoint) +
getRangeSum(prefixSumTester, programmerSplitPoint + 1, totalCandidates);
// Adjust if the excluded candidate was part of the initial best choices up to programmerSplitPoint
if (excludedCandidateIndex <= programmerSplitPoint) {
currentTotalSalary -= std::max(programmerSalaries[excludedCandidateIndex], testerSalaries[excludedCandidateIndex]);
} else { // Excluded candidate was forced to be a tester
currentTotalSalary -= testerSalaries[excludedCandidateIndex];
}
}
// Case 2: Testers are filled first
else if (programmerSplitPoint > testerSplitPoint) {
currentTotalSalary = getRangeSum(prefixSumBestChoice, 1, testerSplitPoint) +
getRangeSum(prefixSumProgrammer, testerSplitPoint + 1, totalCandidates);
// Adjust if the excluded candidate was part of the initial best choices up to testerSplitPoint
if (excludedCandidateIndex <= testerSplitPoint) {
currentTotalSalary -= std::max(programmerSalaries[excludedCandidateIndex], testerSalaries[excludedCandidateIndex]);
} else { // Excluded candidate was forced to be a programmer
currentTotalSalary -= programmerSalaries[excludedCandidateIndex];
}
}
// Case 3: Both roles are filled exactly by the best choices (or all candidates are needed)
else {
// This condition implies that programmerSplitPoint == testerSplitPoint
// If this point covers all candidates, sum up all best choices and subtract the excluded one
if (programmerSplitPoint == totalCandidates) {
currentTotalSalary = getRangeSum(prefixSumBestChoice, 1, totalCandidates);
currentTotalSalary -= std::max(programmerSalaries[excludedCandidateIndex], testerSalaries[excludedCandidateIndex]);
} else {
// This case should ideally not be reached under normal problem constraints
// If it does, it indicates an edge case or an issue with the logic.
// For robustness, we can assign a value indicating an error or skip.
// Setting to -1 might be problematic if valid answers can be negative.
// Let's assume valid inputs won't lead here in a way that breaks the problem.
}
}
printf("%lld ", currentTotalSalary);
}
putchar('\n');
}
return 0;
}
</algorithm></cstdio>
D. Invertible Bracket Sequences
This problem involves counting "invertible" bracket sequences. An invertible bracket sequence is one where for any prefix, the balance (number of open brackets minus closed brackets) is never negative, and the total balance is zero. The solution utilizes prefix sums to track the balance and a Segment Tree (or Sparse Table in this implementation) to efficiently query the minimum balance within ranges. The core idea is to iterate through possible start positions and use the Sparse Table to find valid end positions that satisfy the invertibility condition. The balance array is shifted by 2 \* sum\[left-1\] to align potential matches correctly.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath> // For log2
const int MAX_LEN = 2e5 + 5;
const int LOG_MAX_LEN = 18; // Sufficient for N up to 2^18
int T; // Number of test cases
int sequenceLength; // Length of the bracket sequence
char bracketSequence[MAX_LEN]; // The bracket sequence string
int balance[MAX_LEN]; // Stores the balance of brackets (open - closed)
std::vector<int> balancePositions[MAX_LEN]; // Stores indices for each balance value
long long invertibleCount = 0; // Counter for invertible sequences
// Sparse Table implementation for Range Maximum Query (RMQ)
namespace SparseTable {
int sparseTable[MAX_LEN][LOG_MAX_LEN];
int log2_floor[MAX_LEN];
// Initialize the Sparse Table
void initialize(const int arr[]) {
// Precompute log base 2 for range lengths
for (int i = 2; i < MAX_LEN; ++i) {
log2_floor[i] = log2_floor[i >> 1] + 1;
}
// Initialize the first column (k=0) with array values
for (int i = 1; i < MAX_LEN; ++i) {
sparseTable[i][0] = arr[i];
}
// Build the Sparse Table using dynamic programming
for (int k = 1; (1 << k) < MAX_LEN; ++k) {
for (int i = 1; i + (1 << k) <= MAX_LEN; ++i) {
sparseTable[i][k] = std::max(sparseTable[i][k - 1], sparseTable[i + (1 << (k - 1))][k - 1]);
}
}
}
// Query the maximum value in the range [left, right]
int queryMax(int left, int right) {
if (left > right) return -2e9; // Return a very small value if range is invalid
int k = log2_floor[right - left + 1];
return std::max(sparseTable[left][k], sparseTable[right - (1 << k) + 1][k]);
}
} // namespace SparseTable
// Clear data structures for the next test case
void clearData() {
for (int i = 0; i < MAX_LEN; ++i) {
balancePositions[i].clear();
}
invertibleCount = 0;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%s", bracketSequence + 1); // Read sequence starting from index 1
sequenceLength = strlen(bracketSequence + 1);
// Calculate prefix balances and store positions for each balance value
int currentBalance = 0;
for (int i = 1; i <= sequenceLength; ++i) {
if (bracketSequence[i] == '(') {
currentBalance++;
} else { // bracketSequence[i] == ')'
currentBalance--;
}
balance[i] = currentBalance;
balancePositions[currentBalance + sequenceLength].push_back(i); // Offset to handle negative balances
}
// Initialize Sparse Table with balance values
SparseTable::initialize(balance);
// Iterate through all possible start positions of a potential invertible sequence
for (int leftBoundary = 1; leftBoundary <= sequenceLength; ++leftBoundary) {
int prefixBalanceAtLeft = balance[leftBoundary - 1];
// Binary search for the rightmost valid end boundary 'rightBoundary'
// such that the minimum balance in [leftBoundary, rightBoundary]
// is at least 2 * prefixBalanceAtLeft. This is derived from the condition
// sum[k] - sum[left-1] >= 0 for all k in [left, right] which implies
// sum[k] >= sum[left-1], and also sum[right] = sum[left-1] for invertibility.
// The transformation `balance[k] - 2 * prefixBalanceAtLeft` is used to apply the condition correctly.
int low = leftBoundary - 1, high = sequenceLength + 1; // Binary search range
while (low + 1 < high) {
int mid = low + (high - low) / 2;
// Check if the maximum value of (balance[k] - 2 * prefixBalanceAtLeft) in [leftBoundary, mid] is <= 0
// This is equivalent to checking if balance[k] <= 2 * prefixBalanceAtLeft for all k in range
if (SparseTable::queryMax(leftBoundary, mid) <= (prefixBalanceAtLeft << 1)) {
low = mid; // Potential valid end found, try further right
} else {
high = mid; // Condition violated, need to search left
}
}
int rightBoundary = low; // The rightmost valid end boundary found
// Count valid positions within the found range [leftBoundary, rightBoundary]
// that have a balance equal to prefixBalanceAtLeft.
std::vector<int>& positionsForBalance = balancePositions[prefixBalanceAtLeft + sequenceLength];
// Find first position >= leftBoundary
auto lower = std::lower_bound(positionsForBalance.begin(), positionsForBalance.end(), leftBoundary);
// Find first position > rightBoundary
auto upper = std::upper_bound(positionsForBalance.begin(), positionsForBalance.end(), rightBoundary);
// Add the count of valid end positions to the total
invertibleCount += (upper - lower);
}
printf("%lld\n", invertibleCount);
clearData(); // Prepare for the next test case
}
return 0;
}
</int></int></cmath></algorithm></cstring></vector></cstdio>