codeforce div 2

COFO::Cofo Educational Round 147

cofo round

COFO::Cofo Educational Round #147

Link : COFO::Cofo Edu round 147)
solved : 3
- A : 00:07
- B : 00:31
- C : 00:56
- D : tried 3 times
- rank : 2882
- score : 3 solved

Problem A : Matching

level : not yet decided
tag : combinatorics, math

point

A string s is given consisting of digits and ‘?’
Find the possible integer by chaning ‘?’ to digit
The integer should not have any leading zeroes

Design

We can count ‘?’ as 10 and multiply them
But when we find leading ‘?’, we count it as 9

Big O(time)

O(N)

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

void solve() {
    string s; cin >> s;
    int cntq = count(s.begin(), s.end(), '?');
    if (cntq == 0 || s[0] == '0') {
        if (s[0] == '0')    cout << "0\n";
        else cout << 1 << '\n';
    } else {
        int ans = 1;
        rep(i, 0, sz(s)) if (s[i] == '?'){
            if (i == 0) ans *= 9;
            else ans *= 10;
        }
        cout << ans << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}

Problem B : Sort the Subarray

level : not yet decided
tag : brute force, greedy

Point

String a and a’ are given
String a’ is the result array, after we do one operation on string a
The opertion is,
- we choose a range and sort them in non-descending order
Find the longest subarray that is choosed to do operation

Design

At first, I only used a’ and find the longest non-descending order of range and printed it
- And I got WA
I couldn’t find the reason but there can be holes on my code
So, I naively choosed a smallest section that has diffenet number between string a and a’
Then made it longest by checking the exclusive numbers in a row

Big O(time)

O(N)

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n), b(n);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];
    
    // b에서 가장 긴 non-decreasing order 찾기
    // [l:r] 사이에 포함되지 않았지만, 그냥 sort 된 것처럼 보이는 인덱스는 ? 얘도 결국 l, r 에 포함될텐데
    // 여전히 상관없음

    int le = 1e9, ri = -1;
    rep(i, 0, n) {
        if (a[i] != b[i]) {
            le = min(le, i);
            ri = max(ri, i);
        }
    }
    int prv = ri;
    rep(i, prv+1, n) {
        if (b[i-1] <= b[i]) ri++; // prv >= 1
        else break;
    }
    
    prv = le;
    r_rep(i, prv-1, -1) {
        if (b[i] <= b[i+1]) le--;
        else break;
    }
    cout << le + 1 << " " << ri + 1 << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}

Problem C : Tear it apart

level : not yet decided
tag : brute force, implementation, strings, math

Point

A string s is given, consisting of lowercase Latin letters.
In one operation, you can select several positions in it such that no two selected positions are adjacent to each other
What is the smallest number of operations required to make all the letters in s the same?

Design

Observation
- If we want make character x as the answer, we don’t see any profit deleting x
- Which means, if we set a target that we are going to make the string only have character x, we only need to delete othere characters
So, we can test above logic with every chracter with binary search
Since the total length of the string s is 2 * 1e5, we need at most 20 operations
- If we delete every odd postions for 20 operations, nothing will be left
Then we delete every other chracters except the one that we chose to leave with at most 20 operations

Big O(time)

O(20 * 26 * NlogN)

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

string ors;
bool _possible(int cnt, char dst) {
    int ops = 0;
    string s = ors, t = "";
    
    int prv = -2;
    while(sz(s) > 0 && (count(all(s), dst) != sz(s))) {
        rep(i, 0, sz(s)) {
            if (s[i] == dst) {
                t += s[i];
            } else {
                if (prv != i-1) {
                    // do nothing. erased
                    prv = i;
                } else {
                    // add to the string. can't delete it
                    t += s[i];
                }
            }
        }
        ops++;
        s = t;
        t = "";
    }
    return ops <= cnt;
}
int bs(int le, int ri, int x) {
    int ret = ri;
    char c = x + 'a';
    while(le <= ri) {
        int mid = (le + ri) / 2;
        if (_possible(mid, c)) {
            ret = min(ret, mid);
            ri = mid - 1;
        } else le = mid + 1;
    }
    return ret;
}

void solve() {
    cin >> ors;
    
    int ans = 30;
    rep(i, 0, 26) {
        if (count(all(ors), i + 'a') == 0) continue;
        int ret = bs(0, 30, i);
        ans = min(ans, ret);
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--)
        solve();
return 0;
}

Problem D : Black Cells

level : not yet decided
tag : binary search, brute force, greedy, math

Point

There is a really long strip consisting of 1e18 white cells
Initial pointer will be 0
Find the minimum number of moves you need to make in order to color at least k cells black
In one move, you can do one of three actions:
- move the pointer to the right (from cell x to cell x + 1)
- press and hold the ‘Shift’ button
- release the ‘Shift’ button : the moment you release ‘Shift’, all cells that were visited while ‘Shift’ was pressed are colored in black

Design

There are some observation
- 1. For the range of length L, if we want this range black, we need L+2 operatoins
- 1. If we go to point ‘m’, we need m moves to get there.
- 1. If s is the size of ranges that are used to make k cells black, we need s * 2 operations to press and release
- 1. If the length of a range is less than 2 ( < 1), it’s such a waste to use the cell in the range
    - But we gotta use them when we are out of cells to black
To solve the problem, we count number of ranges that’s length is greater than or equal to 2 and others
If the last selected range is (le, ri), we can get the answer as
- ans = min(ans, ri + 2 * cnt2 - (sum - k))
- ‘Move ri’ + ‘Press + Release’ for all sections - subtract unnecssarily checked ones

Big O(time)

O(N)

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

void solve() {
    int n; ll k; cin >> n >> k;
    vector<ll> le(n), ri(n);
    rep(i, 0, n) cin >> le[i];
    rep(i, 0, n) cin >> ri[i];
    
    int cnt1 = 0, cnt2 = 0;
    
    ll ans = 1e18, sum = 0;
    rep(i, 0, n) {
        ll len = ri[i] - le[i] + 1;
        if (len >= 2) {
            cnt2++;
            sum += len;
            if (sum >= k) {
                ans = min(ans, ri[i] + 2 * cnt2 - (sum - k));
            }
        }
        else {
            cnt1++;
        }
        ll hasto = max(0LL, k - sum);
        if (cnt1 >= hasto)
            ans = min(ans, ri[i] + 2 * (cnt2 + hasto));
    }
    
    
    if (ans == 1e18) ans = -1;
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}