To me, a constructive problem is one in which you are asked to find an object satisfying certain constraints (in most cases it's obvious that solutions exist, or the problem will tell you), and the main part of the challenge is actually finding any of those solutions efficiently.

A lot of people are using the term incorrectly recently, but I don't think asking to reconstruct the answer makes a problem constructive, even though the terms are similar. I would still classify your second example as greedy.

Similarly, in lots of cases an explicit construction is used to prove that an answer is valid. I would still not classify those as constructive most of the time since usually by the time you figured out what it is you need to prove you've already done 90% of the work and finding the construction itself is relatively easy.

In your example, if you have the greedy algorithm, finding an example subsequence is trivial, so it's a very small part of the problem. On the other hand, 418C - Square Table is very clearly constructive: there are lots of valid answers -- the main difficulty is finding a single example.

Of course there are edge cases in which it's not so clear, but roughly it's determined by how long you take to construct an example versus how long you take to determine what it is that you should be trying to construct.