samsidx's blog

What is a constructive algorithm??
By samsidx, 10 years ago, In English

What is a constructive algorithm problem??

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

It's an algorithm which builds something. A graph, an array, a matrix etc. It's what test generators use to build test cases.

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It's just like some proofs in math: there are non-constructive ones which show that some property holds (or some object exists) without constructing the actual object, satisfying this property. Usually such proofs are proofs by contradiction or ones using the axiom of choice (I can't remember any usage of the axiom of choice in discrete math proofs though).

The same applies to computational problems: if you are asked to return an object, satisfying some property, you might be able to prove such an object exists. By proving I mean you could in principle be able to check this somehow in runtime (probably, in polynomial time), however, you might be unable to guess a clever way of getting the object other than brute force.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -14 Vote: I do not like it

In case some of you are still confused, I am adding what helped me understand these, in addition to the other answers. Basically, it is related to problems which is asking you to find any answer(of possibly many) that satisfies the constraints of the question. A nice example is a recent question https://mirror.codeforces.com/contest/1348/problem/D. Also you should go through this training camp pdf for more examples https://assets.hkoi.org/training2019/cast.pdf and how to approach problems of these types.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Hey can u give the link to various training camps ..?

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I wrote this comment, after I was trying to figure out what constructive algorithms are, since I also found this link when I was searching. Rather than just downvoting, let me know the reason here in the comments. I wouldn't repeat if there is anything I am doing wrong, that I don't know of.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Someone Explain it in a simple way.Just an overview with an example would be helpful.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In which you have to find a solution that is trivial in nature but works for all the TCs.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what does 'trivial in nature' means ? could you please elaborate?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Google this -> What are constructive algorithms codeforces.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

so I can consider it as ad-hoc ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Not really.

    Constructive = the problem asks for an object satisfying some conditions and you need to provide an example of said object.

    Ad-hoc = the solution does not only require algorithms/data structures, but also a non-trivial idea.

    The former often implies the latter, but not always.

    → Reply