samsidx's blog

By samsidx, 6 years ago, In English

What is a constructive algorithm problem??

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

»
6 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.

»
6 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.

»
6 months 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://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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    thx

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

  • »
    »
    6 months 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.