Codeforces Round 893 (A

A - Buttons

Abridged Statement

Refer to the original statement.

Approach

It is always optimal to exhaust $c$ buttons first. If $c$ is an even number, then by the time $c$ exhausted, Anna will go first, otherwise Katie.

When $c$ is exhausted, if Anna go first, Anna can only win if $b \lt a$ . If Katie go first, Katie can only win if $a \lt b$ .

Source Code

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define fir first
#define sec second
#define sz(x) x.size()
#define pb push_back
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using pdb = pair<double,double>;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;
const double EPS = (1e-6);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void setio(string s){
    freopen((s + ".in").c_str(),"r",stdin);
    freopen((s + ".out").c_str(),"w",stdout);
}

void solve(){
    ll a, b, c;
    cin >> a >> b >> c;

    if (c % 2){
        cout << (a >= b ? "First" : "Second") << '\n';
    }else{
        cout << (b >= a ? "Second" : "First") << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

B - The Walkway

Abridged Statement

There are $n$ benches, and $m$ cookies sellers, $i$ cookie seller is at bench $m_i$ Petya starts at bench $1$ and walk to the next one every minute, Petya eats cookie under the following conditions:

Petya has never eaten any cookie before (basically when Petya is at $1$ )
Petya is at one of the $m_i$ (Petya eats cookie when there is a cookie seller)
The bench that Petya had his/her (I have no idea Petya is a boy or girl) last cookie is $d$ distance away from current bench

Determine the minimum number of cookies Petya had after removing exactly one cookie seller, and the number of different cookie sellers that we can remove which will result in the minimum cookies Petya eat.

Approach

Let's assume we're currently at bench $i$ where there is a cookie seller, and the next cookie seller is at $j$ . We will have a cookie at $i$ , and before we reach $j$ , we will have $\frac{j-i-1}{d}$ another cookies. As you can see, the number of cookies we have from $i$ to $j$ is not affected by any other cookie sellers.

With the above, we can compute, the number of cookies we will eat if we are to stop at bench $i$ from $1$ , let's call it $pf[i]$ . And then, also compute the number of cookies we will eat if we stop at bench $n$ from bench $i$ , let's call it $sf[i]$ .

Okay let's say now we want to remove cookie seller at $m_i$ . The total cookies we would have is $pf[i-1] + sf[i+1] + \frac{m_{i+1} - m_{i-1} - 1}{d}$ . Special case is for $i = 1$ and $i = n$ . But it shouldn't have any trouble.

Now we can try to remove every cookie seller (and count the cookies eaten in $O(1)$ ), and count the total of them that result in minimum cookies eaten.

(My implementation is very whacky, I made sure there is always a cookie seller ar $1$ , so that I can handle the edge case better, but that obviously did not turn out to be useful, but worse. Just use it as a reference)

Source Code

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define fir first
#define sec second
#define sz(x) x.size()
#define pb push_back
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using pdb = pair<double,double>;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;
const double EPS = (1e-6);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void setio(string s){
    freopen((s + ".in").c_str(),"r",stdin);
    freopen((s + ".out").c_str(),"w",stdout);
}

void solve(){
    ll n, m, d;
    cin >> n >> m >> d;

    vi a = {1};

    for(int i{}; i < m; i++){ 
        int x;
        cin >> x;
        if (x == 1) continue;
        a.pb(x);
    }

    bool changed = m != sz(a);
    m = sz(a);

    vll pf(m);
    vll sf(m);
    pf[0] = 1;
    sf[m-1] = 1+ (n-a[m-1])/d;

    for(int i{1}; i < m; i++){
        pf[i] = pf[i-1] + 1 + (a[i]-a[i-1]-1) / d;
    }
    
    for(int i{m-2}; i >= 0; i--){
        sf[i] = sf[i+1] + 1 + (a[i+1]-a[i]-1) / d;
    }

    int cnt = 1;
    ll res = pf[m-2] + (n - a[m-2]) / d;

    for(int i{}; i < m-2; i++){
        if (res == pf[i] + sf[i+2] + (a[i+2]-a[i]-1) / d){
            cnt++;
        }
        if (res > pf[i] + sf[i+2] + (a[i+2]-a[i]-1) / d) cnt = 1;
        res = min(res, pf[i] + sf[i+2] + (a[i+2]-a[i]-1) / d) ;
    }

    if (!changed){
        cnt += sf[0] == res;
    }
    cout << res << ' ' << cnt << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

C - Yet Another permutation

Abridged Statement

Find a permutation $p$ that consist of integers from $1$ to $n$ such that has the maximal number of distinct integers in $d$ such that $d_i = gcd(p_i, p_{(i \mod n) + 1})$ .

Approach

Let's prove that we can always have at least $\lfloor \frac{n}{2} \rfloor$ . There are $\lfloor \frac{n}{2} \rfloor$ even numbers, which can be represented as $2x$ , and $gcd(2x, x) = x$ . And that proves that we can always have at least $\lfloor \frac{n}{2} \rfloor$ distinct $d_i$ . Now let's prove that the answer will not be more than that. Let's assume there exist a number $c, 1 \leq c \leq n$ that is not included in the previous operation, that means $2 \cdot c$ definitely does not exist in the permutation, which means there is no number $x, x \gt c$ such that $gcd(c, x) = c$ .

Now we just need a way to properly arrange the numbers. We can simply start with the smallest number that is not in the array at anytime, append it to the array and keep multiplying it by 2 and append it, until the number is greater than $n$ , and repeat the entire step.

Source Code

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define fir first
#define sec second
#define sz(x) x.size()
#define pb push_back
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using pdb = pair<double,double>;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;
const double EPS = (1e-6);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void setio(string s){
    freopen((s + ".in").c_str(),"r",stdin);
    freopen((s + ".out").c_str(),"w",stdout);
}

void solve(){
    int n;
    cin >> n;

    vi used(n+1);
    for(int i{1}; i <= n; i++){
        if (used[i]) continue;
        used[i] = 1;
        for(int j{i}; j <= n; j *= 2){
            cout << j << ' ';
            used[j] = 1;
        }
    }
    cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

D - Trees and Segments

Abridged Statement

Given a binary array that is of length $n$ for $n \leq 3000$ . Denote $l_0$ as the maximal length of consecutive $0$ s, and $l_1$ as the maximal length of consecutive $1$ s in the array. The score of the array is $a \cdot l_0 + l_1$ . You have $k$ operations, in each operation you can flip a bit. Find the answer for $a = 1, 2, ..., n$ , such that you cannot use more than $k$ operations.

Approach

Let's first denote $mx[i]$ as maximal $l_1$ when $l_0 = i$ if we have used no more than $k$ operations on the array. If we have this $mx$ array, we can answer each $a$ independently by bruteforcing the answer for each possible $l_0$ , with the $mx[i]$ array. This will give us the optimal answer for each query because, when $l_0 = i$ , we have the max $l_1$ , there can be no answer better than it when $l_0 = i$ . This will take $O(N^2)$ , which will fit into the time limit.

But, how do we get $mx$ array?

Let's first discuss about finding the segment that has the maximal $l_0$ that ends before or at $i$ and used at most $j$ operations, for $1 \leq i \leq n$ and $0 \leq j \leq k$ . Notice that for each index $i$ , to maximize the segment that has $l_0$ that ends at $i$ , while having $j$ operations, is to simply toggle the first $j$ number of $1$ s (starting in reverse from $i$ ). This way we can get the maximal consecutive segment of $0$ that ends at $i$ with $j$ operations.

Let's denote $pfz[i][j]$ (prefix zero) as $l_0$ such that the segment ends at $i$ and used $j$ operations.

We can also use the similar technique to find maximal length of segment that starts at $i$ and used $j$ operations, let's call that $sfz[i][j]$ (sufsix zero).

Do the same for $1$ as well, and denote the similar array as $pfo[i][j]$ and $sfo[i][j]$ .

There are many ways to implement the above, what I did was using binary search with a prefix sum array, to compute them, time comeplexity for this is $O(N^2 \log N)$

We're not quite there yet,

$pfz[i][j]$ is currently $l_0$ such that the segment ends at $i$ and used $j$ operation. To make the process of finding $mx$ smoother, we can change $pfz[i][j]$ to the maximal $l_0$ such that the segments ends before or at $i$ and used at most $j$ operations.

This can be done easily by using the transition below,

$pfz[i][j] = max(pfz[i][j], pfz[i-1][j], pfz[i][j-1])\\$ $sfz[i][j] = max(sfz[i][j], sfz[i+1][j], sfz[i][j-1])$

(Same goes to $sfo$ and $pfo$ )

With all the above, we can start finding $mx[i]$ now.

In a setting where $l_0, l_1 \geq 1$ , the segment of $l_0$ and $l_1$ is disjoint, and either $0$ comes first or $1$ comes first.

So to find $mx$ , we can do the transition below,

For the situation when segment with $l_0$ comes before $l_1$ .

$mx[pfz[i][j]] = max(mx[pfz[i][j]], sfo[i+1][k-j])$

Otherwise,

$mx[sfz[i][j]] = max(mx[sfz[i][j]], pfo[i-1][k-j])$

Once we obtained this array, we can answer $a = 1, 2, ..., n$ independently by iterating through each $i$ , and find the max of $a * i + mx[i]$ .

Source Code

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define fir first
#define sec second
#define sz(x) x.size()
#define pb push_back
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using pdb = pair<double,double>;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;
const double EPS = (1e-6);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void setio(string s){
    freopen((s + ".in").c_str(),"r",stdin);
    freopen((s + ".out").c_str(),"w",stdout);
}

void solve(){
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    vi zeros(n);

    for(int i{}; i < n; i++){
        zeros[i] = s[i] == '0';
        if (i) zeros[i] += zeros[i-1];
    }

    vector<vi> pfz(n, vi(k+1));
    vector<vi> sfz(n, vi(k+1));
    vector<vi> pfo(n, vi(k+1));
    vector<vi> sfo(n, vi(k+1));

    // zero
    for(int i{}; i < n; i++){
        for(int j{}; j <= k; j++){
            //if number of 1s is smaller than number to change
            if (i+1 - zeros[i] <= j){
                pfz[i][j] = i+1;
            }else{
                int lo = 0, hi = i;
                while (hi > lo){
                    int mid = lo + (hi-lo+1)/2;
                    if (i-mid+1 - (zeros[i] - (!mid ? 0 : zeros[mid-1])) >= j+1){
                        lo = mid;
                    }else hi = mid - 1;
                }
                pfz[i][j] = i - lo;
            }
        }
    }
    for(int i{n-1}; i >= 0; i--){
        for(int j{}; j <= k; j++){
            //if number of 1s is smaller than number to change
            if (n - i - (zeros[n-1] - (!i ? 0 : zeros[i-1])) <= j){
                sfz[i][j] = n-i;
            }else{
                int lo = i, hi = n-1;
                while (hi > lo){
                    int mid = lo + (hi-lo)/2;
                    if ((mid-i+1) - (zeros[mid] - (!i ? 0 : zeros[i-1])) >= j+1){
                        hi = mid;
                    }else lo = mid + 1;
                }
                sfz[i][j] = lo - i;
            }
        }
    }

    for(int i{}; i < n; i++){
        for(int j{}; j <= k; j++){
            //if number of 1s is smaller than number to change
            if (zeros[i] <= j){
                pfo[i][j] = i+1;
            }else{
                int lo = 0, hi = i;
                while (hi > lo){
                    int mid = lo + (hi-lo+1)/2;
                    if ((zeros[i] - (!mid ? 0 : zeros[mid-1])) >= j+1){
                        lo = mid;
                    }else hi = mid - 1;
                }
                pfo[i][j] = i - lo;
            }
        }
    }
    for(int i{n-1}; i >= 0; i--){
        for(int j{}; j <= k; j++){
            //if number of 1s is smaller than number to change
            if ((zeros[n-1] - (!i ? 0 : zeros[i-1])) <= j){
                sfo[i][j] = n-i;
            }else{
                int lo = i, hi = n-1;
                while (hi > lo){
                    int mid = lo + (hi-lo)/2;
                    if ((zeros[mid] - (!i ? 0 : zeros[i-1])) >= j+1){
                        hi = mid;
                    }else lo = mid + 1;
                }
                sfo[i][j] = lo - i;
            }
        }
    }

    for(int i{}; i < n; i++){
        for(int j{}; j <= k; j++){
            if (i){
                pfz[i][j] = max(pfz[i][j], pfz[i-1][j]);
                pfo[i][j] = max(pfo[i][j], pfo[i-1][j]);
            }
            if (j){
                pfz[i][j] = max(pfz[i][j], pfz[i][j-1]);
                pfo[i][j] = max(pfo[i][j], pfo[i][j-1]);
            }
        }
    }

    for(int i{n-1}; i >= 0; i--){
        for(int j{}; j <= k; j++){
            if (i < n-1){
                sfz[i][j] = max(sfz[i][j], sfz[i+1][j]);
                sfo[i][j] = max(sfo[i][j], sfo[i+1][j]);
            }
            if (j){
                sfz[i][j] = max(sfz[i][j], sfz[i][j-1]);
                sfo[i][j] = max(sfo[i][j], sfo[i][j-1]);
            }
        }
    }

    vi mx(n+1, -1);

    for(int i{}; i < n; i++){
        for(int j{}; j <= k; j++){
            if (i < n-1) mx[pfz[i][j]] = max(mx[pfz[i][j]], sfo[i+1][k-j]);
            if (i) mx[sfz[i][j]] = max(mx[sfz[i][j]], pfo[i-1][k-j]);
        }
    }

    if (zeros[n-1] <= k){
        mx[0] = n;
    }
    if (n - zeros[n-1] <= k){
        mx[n] = 0;
    }

    for(int i{}; i < n; i++){
        int ans = 0;
        for(int j{}; j <= n; j++){
            if (mx[j] != -1) ans = max(ans, j * (i+1) + mx[j]);
        }
        cout << ans << ' ';
    }
    cout<< '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}