Competitive Programming Solutions

849A - Odds And Ends

02 Jan 2021 — Tags: implementation — URL

First of all, if $n$ is even then it is impossible to decompose it into subsegments of odd sizes.

Otherwise if $n$ is odd then there must be necessarily a subsegment containing the first element and a subsegment containing the last element, otherwise it is not possible. If true, we can take the entire array as a valid subsegment.

Time complexity: $O(1)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool solve(vi a)
{
    int n = (int)(a).size();
    if ((a[0] % 2 != 1) or (a.back() % 2 != 1))
        return false;
    return n % 2;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    for (auto &ai : a)
        cin >> ai;
    cout << (solve(a) ? "Yes" : "No") << endl;
    return 0;
}

Related posts