C# – CodeForces – Odds and Ends

The first problem in CodeForces, division 2 is usually an implementation problem. This means that after reading it, a Joe-average algorithmic person would know how to write it in less than 5 minutes. Or so I thought, before seeing this one:


Given an integer sequence a1, a2, …, an of length n. Decide whether it is possible to divide it into an odd number of non-empty subsegments, the each of which has an odd length and begins and ends with odd numbers.

subsegment is a contiguous slice of the whole sequence. For example, {3, 4, 5} and {1} are subsegments of sequence {1, 2, 3, 4, 5, 6}, while {1, 2, 4} and {7} are not.


The first line of input contains a non-negative integer n (1 ≤ n ≤ 100) — the length of the sequence.

The second line contains n space-separated non-negative integers a1, a2, …, an (0 ≤ ai ≤ 100) — the elements of the sequence.


Output “Yes” if it’s possible to fulfill the requirements, and “No” otherwise.

This one looks like a problem, where one should evaluate m^n solutions, to make sure that the answer is correct. And knowing the zeal with which CodeForces people prepare their tests, it would be quite tough to make it a good answer within less than 5 minutes.

However, the trick here is that this is a first question. And if it does not look easy, then you should think again, probably you are missing something. The point is indeed, you are missing something, because you are reading too careful – the whole question can be translated to the following question – is 1 subsegment enough? Yes it is! Then just evaluate it for 1, seeing whether it is with uneven length, starts and ends with odd numbers. These are 3 checks and are pretty simple for a first question. But you have to understand it yourself.

Thus, this is a good working solution:

Yup! The whole magic is in 1 line! Without any complicated data structures.

Tagged with: ,