### samsidx's blog

By samsidx, 6 years ago,

What is a constructive algorithm problem??

• +6

 » 6 years ago, # |   +7 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, # ^ |   0 Thanks.
 » 6 years ago, # |   +5 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 years ago, # ^ |   0 Thanks.
 » 6 months ago, # | ← Rev. 3 →   -14 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, # ^ |   -14 thx
•  » » 6 months ago, # ^ |   -9 Hey can u give the link to various training camps ..?
•  » » » 6 months ago, # ^ |   +6 Someone asked for this a while back. After some searching I found this link https://hkoi.org/en/training-materials/2019/
•  » » » » 6 months ago, # ^ |   0 Thanks for this man ..
•  » » 6 months ago, # ^ |   +15 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.
 » 4 weeks ago, # |   0 Please Someone Explain it in a simple way.Just an overview with an example would be helpful.
•  » » 4 weeks ago, # ^ |   0 In which you have to find a solution that is trivial in nature but works for all the TCs.
•  » » » 4 weeks ago, # ^ |   0 what does 'trivial in nature' means ? could you please elaborate?
•  » » » » 4 weeks ago, # ^ |   +8 Google this -> What are constructive algorithms codeforces.
•  » » » » » 4 weeks ago, # ^ |   0 Thank You . Very helpful!!
•  » » » » » 4 weeks ago, # ^ |   0 Lmao this blog appears at the top