codeforce div 3

COFO::Cofo Round 801

cofo round

COFO::Cofo Round #863

Link : COFO::Cofo round 863)
solved : 2
- A : 00:17
- B : 00:35
- C : tried
- rank : 2 solved

Problem A : Insert Digit

level : not yet decided
tag : greedy, math, strings

point

Positive number of length n and one additional digit are given
Find the maximal number when you can put the digit where you want to inside the number

Design

When there is a number that’s less digit than d,
- We can put d here
Otherwise, print d first and print left number because d is the greatest number

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, d; cin >> n >> d;
    string s; cin >> s;
    bool f = false;
    rep(i, 0, n) if (s[i] - '0' < d) f = true;
    if (!f) {
        cout << s << d << '\n';
        return;
    }
    
    rep(i, 0, n) {
        if (d != -1 && s[i] - '0' < d) {
            cout << d;
            d = -1;
        }
        cout << s[i];
    }
    if (d != -1) cout << d;
    cout << '\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 : Conveyor Belts

level : not yet decided
tag : implementation, math

Point

Conveyor matrix is given
Start poistion (x1, y1) and end position (x2, y2) are given
Each conveyor belt is moving clockwise.
Find the minimum amount of energy that will have to be spent to get to the end position

Design

Since, the moving belt is free to walk we only need to find how many layers are between start and end position
We can get what layer we are by checking the length from the current position to the end layer of the matrix

Big O(time)

O(1)

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() {
    ll n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    ll  X1 = min(x1, n - x1 + 1),
        Y1 = min(y1, n - y1 + 1),
        X2 = min(x2, n - x2 + 1),
        Y2 = min(y2, n - y2 + 1);
    ll st = min(X1, Y1), en = min(X2, Y2);
    cout << abs(en - st) << '\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 : Restore the Array

level : not yet decided
tag : constructive algorithms, greedy

Point

There is a hidden array a
Array b is given created by a,
- b[i] = max(a[i], a[i+1])
Find the array a

Design

I was struggling to solve this problem during the test
I knew that putting same number or 0 will solve the problem, but couldn’t make it through
Here’s the simple solution to this problem
We can get a[i] = min(b[i-1], b[i]) (i >= 2)
- a[1] = b[1]
- a[n] = b[n-1]
Let’s say we are proving if it works by creating B using a and b
- B[1] = max(a[1], a[2]) = max(b[1], min(b[1], b[2]))
- if b[1] > b2, then max(b[1], b[2]) = b[1]
- if b[2] >= b[1], then max(b[1], b[1]) = b[1]
- So, B[1] = b[1]
And we can use this logic up to n
But you know what?
- This is just proving something that we know already
- I mean, if we can not come up with the solution we don’t get the chance to prove it.
- So this greedy can be captured by intuition

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 - 1) cin >> b[i];
    
    a[0] = b[0];
    rep(i, 1, n - 1) a[i] = min(b[i-1], b[i]);
    a[n-1] = b[n-2];
    
    for(auto x : a) cout << x << " ";
    cout << '\n';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}