codeforce div 2

COFO::Cofo Round 846

cofo round

COFO::Cofo Round #846

Link : COFO::Cofo round 846)
solved : 2
- A : 01:23
- B : failed
- C : solved, but the problem is deleted
- rank : 13328

Problem A : Hayato and School

level : not yet decided
tag : constructive algorithms

point

Find three numbers in the array whose sum is odd

Design

There are only two cases to make sum as odd
- odd + odd + odd
- even + even + odd

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;
const int MAXN = 2 * 1e5 + 9;

void solve() {
    int n; cin >> n;
    vector<int> odd, even;
    rep(i, 0, n) {
        int x; cin >> x;
        if (x %2 == 0) even.push_back(i + 1);
        else odd.push_back(i + 1);
    }
    // 홀 홀 홀
    if (sz(odd) >= 3) {
        cout << "YES\n";
        rep(i, 0, 3) cout << odd[i] << " ";
        cout << '\n';
    // 짝 짝 홀
    } else if (sz(odd) >= 1 && sz(even) >= 2){
        cout << "YES\n";
        cout << odd[0] << " " << even[0] << " " << even[1] << '\n';
    } else cout << "NO\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 : GCD Partition

level : not yet decided
tag : brute force, greedy, math, number theory

Point

There is an array a
We can do below operation
- select k > 1
- split the array into k subsegments
- calculate the sum in each of k subsegments and write thses sums to another array b
- the final score of such a split will be gcd(b1, b2, …, bk)
Find the maximum possible score

Design

There’s only one observation we need to notice
Let’s say s = gcd(b1, b2, b3, …, bk)
Then below equation holds
- gcd(b1, b2, …, bk) <= gcd(b1 + b2, b3, …, bk)
Then all we need to is that summing as many numbers
- How many ?
- We only need two numbers to get gcd
So, the answer will be one of gcd(prefix_sum[i], whole_sum - prefix_sum[i])

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;

ll _GCD(ll x, ll y){
    if (y == 0) return x;
    return _GCD(y, x % y);
}

void solve() {
    int n; cin >> n;
    vector<ll> a(n, 0); rep(i, 0, n) cin >> a[i];
    
    ll ans = 0;
    ll s = accumulate(a.begin(), a.end(), 0LL), cur = 0;
    rep(i, 0, n - 1) {
        cur += a[i];
        ll x = _GCD(cur, s - cur);
        ans = max(ans, x);
    }
    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;
}