Massive Cheating

• Great contest

• Good contest

• Average contest

• Bad contest

greedy strings implementation

Recall that modifying an existing character costs $$$0$$$.

Calculate the number of unique characters you need to fit in the string vs the current string length.

Let $$$n$$$ be the length of the string $$$S$$$, and $$$L$$$ be the specified upper bound character. The problem requires the final string to contain every character in the range $$$[\text{'a'}, L]$$$ exactly once.

The number of unique characters required is $$$k = (L - \text{'a'}) + 1$$$.

Observation:

Since the Modification operation is free (cost $$$0$$$), we treat the initial $$$n$$$ characters of $$$S$$$ as $$$n$$$ "free capacity" slots. We can transform these existing slots into any character we need. We do not need to preserve any original characters.

We analyze two cases:

• Case 1: Sufficient Capacity ($$$n \ge k$$$) We have enough slots to fit all required characters. We modify the first $$$k$$$ slots to match our needs. Remaining slots can be anything. Total cost is $$$0$$$.

• Case 2: Insufficient Capacity ($$$n \lt k$$$) We have fewer slots than required. We use our $$$n$$$ slots to create the first $$$n$$$ required characters. We still need $$$k - n$$$ characters, which must be added via Insertion (cost $$$1$$$).

Conclusion:

The answer is $$$\max(0, k - n)$$$.

#include <bits/stdc++.h>
using namespace std;

void solve(){
    string s;
    cin >> s;
    char a;
    cin >> a;
    
    int n = s.size();
    int k = (a - 'a') + 1;
    int need = k - n;
    
    cout << max(0, need) << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

bitwise math constructive-algorithms

If a bit is set in the AND sum ($$$y$$$), what does that tell you about $$$a$$$ and $$$b$$$?

Can a specific bit be set in both the XOR sum ($$$x$$$) and the AND sum ($$$y$$$) simultaneously?

Let the two unknown non-negative integers be $$$a$$$ and $$$b$$$. We are given: 1. $$$x = (a \oplus b)$$$ 2. $$$y = (a \wedge b)$$$

Consider the bits at some position $$$k$$$:

• If the $$$k$$$-th bit is set in AND ($$$y$$$), then both $$$a$$$ and $$$b$$$ must have this bit set ($$$1 \wedge 1 = 1$$$).
• If the $$$k$$$-th bit is set in XOR ($$$x$$$), then exactly one of $$$a$$$ or $$$b$$$ must have this bit set ($$$1 \oplus 0 = 1$$$).

Impossibility Condition:

If both $$$a$$$ and $$$b$$$ have the $$$k$$$-th bit set (required if the bit is in $$$y$$$), their XOR at that position must be $$$0$$$. Therefore, it is impossible for the same bit position to be set in both $$$x$$$ (XOR sum) and $$$y$$$ (AND sum).

• If (x & y) != 0, no solution exists. Print -1.

Construction:

If the condition holds, we can construct the numbers by distributing the bits:

• $$$y$$$ contains bits common to both numbers.
• $$$x$$$ contains bits unique to one of the numbers.

We can simply assign:

#include <bits/stdc++.h>
using namespace std;
using long long = long long;

void solve(){
    long long x, y;
    cin >> x >> y;
    
    if((x & y) != 0){
        cout << -1 << endl;
    }
    else{
        cout << y << ' ' << (x | y) << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

number-theory math

The number of valid durations is equal to the number of common divisors of $$$a_i$$$ and $$$b_i$$$.

For a specific scenario $$$(a, b)$$$, a valid duration $$$d$$$ must divide both $$$a$$$ and $$$b$$$. Thus, $$$d$$$ must be a divisor of $$$\gcd(a, b)$$$. The "Spending Score" is simply the count of divisors of $$$\gcd(a, b)$$$.

We can solve this using two different approaches based on time complexity trade-offs.

Algorithm 1: Precomputation (Sieve-like)

Since the maximum value of $$$a_i, b_i$$$ is $$$M = 10^6$$$, we can precompute the divisor count for all numbers up to $$$M$$$.

1. Initialize an array div_count of size $$$10^6$$$.
2. Iterate $$$i$$$ from 1 to $$$M$$$. For every multiple $$$j$$$ of $$$i$$$, increment div_count[j].
3. This precomputation runs in $$$O(M \log M)$$$.
4. Each query is then answered in $$$O(1)$$$ (plus the cost of GCD) by printing div_count[gcd(a,b)].

Algorithm 2: Direct Calculation ($$$O(\sqrt{N})$$$)

If memory is tight or $$$Q$$$ is small, we can calculate the answer for each query independently.

1. Calculate $$$G = \gcd(a, b)$$$.
2. Iterate $$$i$$$ from $$$1$$$ to $$$\sqrt{G}$$$.
3. If $$$i$$$ divides $$$G$$$:
   • Increment count (for divisor $$$i$$$).
   • If $$$i \neq G/i$$$, increment count again (for divisor $$$G/i$$$).
4. Sum these counts to the total answer.

#include <bits/stdc++.h>
using namespace std;

const int MAX_VAL = 1000000;
int div_count[MAX_VAL + 1];

void precompute() {
    for (int i = 1; i <= MAX_VAL; i++) {
        for (int j = i; j <= MAX_VAL; j += i) {
            div_count[j]++;
        }
    }
}

void solve() {
    int Q;
    if (!(cin >> Q)) return;

    long long total_score = 0;
    while(Q--) {
        int a, b;
        cin >> a >> b;
        int common = gcd(a, b);
        total_score += div_count[common];
    }
    cout << total_score << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t, a, b;
    cin >> t;
    
    ll ans = 0;
    while (t--){
        cin >> a >> b;
        int x = std::gcd(a, b);
        for (int i = 1; i * i <= x; i++){
            if (x % i == 0){
                if (i * i == x) ans++;
                else ans += 2;
            }
        }
    }
    cout << ans << endl;
}

data-structures greedy

Always fuse the smallest duplicate value first.

The problem requires fusing the smallest value $$$x$$$ that appears $$$\ge 2$$$ times. This implies we should process power levels in increasing order.

When we fuse two artifacts of power $$$x$$$, we generate a new artifact of power $$$2x$$$. This new artifact might then need to be fused with existing $$$2x$$$ artifacts. To handle this efficiently, we can use a Data Structure that keeps keys sorted.

Algorithm:

1. Use a map<long long, vector<int>> to store the indices of each power level. A map automatically iterates through keys in ascending order.
2. Iterate through the map. For a power level val:
   • If there are fewer than 2 indices, we cannot fuse. Move to the next value.
   • If there are $$$\ge 2$$$ indices, sort them to find the leftmost and rightmost.
   • Pair them up: The rightmost index is destroyed (marked with -1), and the leftmost index is updated to $$$2 \cdot val$$$.
   • Crucial Step: Insert the updated leftmost index into map[2 * val].
3. Since std::map iterators remain valid when inserting new keys (larger than current), the newly formed values will be processed correctly in later iterations of the same loop.

#include <bits/stdc++.h>
using namespace std;
using long long = long long;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<long long> a(n);
    map<long long, vector<int>> pos;
    
    for (int i = 0; i < n; i++){
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    
    for (auto &it : pos){
        long long val = it.first;
        vector<int> &idxs = it.second;
        
        if (idxs.size() < 2) continue;
        
        sort(idxs.begin(), idxs.end());
        int k = idxs.size();
        
        // We can form k/2 pairs
        for (int i = 0; i < k / 2; i++){
            int left = idxs[i];
            int right = idxs[k - 1 - i];
            
            a[right] = -1;       // Destroy rightmost
            a[left] = val * 2;   // Upgrade leftmost
            
            // Add the new upgraded artifact to the map for future processing
            pos[val * 2].push_back(left);
        }
    }
    
    vector<long long> res;
    for (long long x : a) {
        if (x != -1) res.push_back(x);
    }
    
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << (i == res.size() - 1 ? "" : " ");
    }
    cout << endl;
}

dp number-theory

The maximum sum is small ($$$20,000$$$). The number of items used is also small ($$$\approx 200$$$).

We need to find the number of sequences summing to $$$X$$$ such that the length of the sequence is a Prime Number. The available numbers are $$${101, \dots, 109} \setminus {105}$$$.

This is a variation of the Coin Change problem (or Knapsack), but we must track exactly how many items are used.

Dynamic Programming State:

Let $$$dp[s][c]$$$ be the number of ways to form sum $$$s$$$ using exactly $$$c$$$ items.

• Max Sum $$$X = 20000$$$.
• Min item value $$$\approx 100$$$, so max items $$$c \approx 200$$$.
• State space: $$$20000 \times 200 = 4 \times 10^6$$$. This fits easily within memory and time limits.

Transitions:

Iterate through all current sums $$$i$$$ and counts $$$j$$$. For each valid usable number $$$w$$$:

Final Answer:

For each query $$$X$$$, calculate the sum of $$$dp[X][p]$$$ where $$$p$$$ is a prime number.

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_SUM = 20005;
const int MAX_CNT = 205;

int dp[MAX_SUM][MAX_CNT];

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;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<int> usable = {101, 102, 103, 104, 106, 107, 108, 109};
    
    dp[0][0] = 1;

    for (int i = 0; i < MAX_SUM; i++) {
        for (int j = 0; j < MAX_CNT - 1; j++) {
            if (dp[i][j] == 0) continue;
            
            for (int w : usable) {
                if (i + w < MAX_SUM) {
                    dp[i + w][j + 1] = (dp[i + w][j + 1] + dp[i][j]) % MOD;
                }
            }
        }
    }

    vector<int> primes;
    for(int i = 0; i < MAX_CNT; i++) {
        if(is_prime(i)) primes.push_back(i);
    }

    int t;
    cin >> t;
    while (t--) {
        int x;
        cin >> x;
        int ans = 0;
        for (int p : primes) {
            ans = (ans + dp[x][p]) % MOD;
        }
        cout << ans << "\n";
    }
}

ternary-search interactive

The function $$$E(x)$$$ is described as strictly decreasing until a minimum $$$x_{min}$$$ and then strictly increasing. This property is known as unimodality (specifically, convex-like).

We can use Ternary Search to find the minimum of a unimodal function. We perform the search on the range $$$[0, 10^{14}]$$$. In each step, we divide the current range $$$[L, R]$$$ into three parts using two internal points:

We query the energy at these points:

• If $$$E(m_1) \lt E(m_2)$$$, the minimum must lie in the left part $$$[L, m_2]$$$. Update $$$R = m_2$$$.
• If $$$E(m_1) \gt E(m_2)$$$, the minimum must lie in the right part $$$[m_1, R]$$$. Update $$$L = m_1$$$.

Repeating this process for roughly 100-200 iterations provides extremely high precision, well within the 300 query limit.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    double low = 0;
    double high = 1e14; 

    for(int i = 0; i < 150; i++){
        double m1 = low + (high - low) / 3;
        double m2 = high - (high - low) / 3;
        
        cout << "? " << fixed << setprecision(10) << m1 << endl;
        double ans1; cin >> ans1;
        
        cout << "? " << fixed << setprecision(10) << m2 << endl;
        double ans2; cin >> ans2;
        
        if (ans1 < ans2) high = m2;
        else low = m1;
    }
    
    cout << "! " << fixed << setprecision(10) << (low + high) / 2 << endl;
}

constructive greedy implementation

Numbers divisible by 6 are "jokers" that can connect to anything. Numbers coprime to 6 need a multiple of 6 adjacent.

We classify the server capacities based on their divisibility:

1. S6 (The Jokers): Divisible by 6.
2. S3: Divisible by 3 (but not 2).
3. S2: Divisible by 2 (but not 3).
4. None: Not divisible by 2 or 3.

Strategy:

We construct the array by placing elements into a result vector (initialized to -1) in multiple passes to ensure validity.

1. Placement of 'None': The most restrictive elements are 'None'. They must be adjacent to 'S6'. We place all 'None' elements at even indices ($$$0, 2, 4 \dots$$$) and immediately pair them with 'S6' elements at the adjacent odd indices ($$$1, 3, 5 \dots$$$).

   • If there are more 'None' elements than 'S6' elements, it is impossible. Output NO.

2. Placement of 'Two' and 'Three': After handling 'None', we fill the remaining slots. The 'S2' and 'S3' elements must alternate to maintain validity (e.g., $$$... S2, S3, S2, S3$$$).

   • We determine which set is larger (S2 or S3) and place the larger set first into the remaining slots (continuing the pattern), followed by the smaller set.

3. Filling Gaps: Any remaining gaps (indices that are still -1) are filled with the remaining 'S6' elements.

4. Verification: Finally, we run a linear scan through the constructed array to verify all adjacent products are divisible by 6.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
 
template<typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxheap = priority_queue<T>;
template<typename T>
using vec = vector<T>;
 
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define rot(a, x) rotate(a.begin() + 1, a.begin() + 1 + x, a.end())
#define sz(x) (int)(x).size()
 
void solve() {
    ll n;
    cin >> n;
    vec<ll> one, two, three, six;
    for (ll i = 0; i < n; i++) {
        ll x;
        cin >> x;
        ll r = x % 6;
        if (!r) six.push_back(x);
        else if (r == 3) three.push_back(x);
        else if (r % 2 == 0) two.push_back(x);
        else one.push_back(x);
    }
 
    if (six.size() + one.size() == n and six.size() >= n/2) {
        cout << "Yes\n";
        for (ll i = 0; i < n; i++) {
            if (i % 2 or one.empty()) cout << six.back(), six.pop_back();
            else cout << one.back(), one.pop_back();
            cout << ' ';
        }
        return;
    }
 
    vec<ll> ans;
    while (six.size()) {
        if (ans.size() % 2) ans.push_back(six.back()), six.pop_back();
        else {
            if (one.size()) ans.push_back(one.back()), one.pop_back();
            else if (two.size() > three.size()) ans.push_back(two.back()), two.pop_back();
            else if (three.size()) ans.push_back(three.back()), three.pop_back();
            else ans.push_back(six.back()), six.pop_back();
        }
    }
 
    if (one.size() or abs(ll(two.size()) - ll(three.size())) > 1) {
        cout << "No";
        return;
    }
    if (two.size() < three.size()) swap(two, three);
    while (ans.size() < n) {
        if (two.size() > three.size()) ans.push_back(two.back()), two.pop_back();
        else ans.push_back(three.back()), three.pop_back();
    }
    cout << "Yes\n";
    for (auto x : ans) cout << x << ' ';
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll tc = 1;
    cin >> tc;
    for (ll i = 1; i <= tc; i++) {
        solve();
        cout << '\n';
    }
}