What is a constructive algorithm problem??

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 186 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

What is a constructive algorithm problem??

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/24/2021 08:46:05 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Thanks.

It's just like some proofs in math: there are non-constructive ones which show that some property holds (or some object exists) without

constructingthe 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.

Thanks.

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.

thx

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

Someone asked for this a while back. After some searching I found this link https://hkoi.org/en/training-materials/2019/

Thanks for this man ..

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.

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

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

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

Google this ->

`What are constructive algorithms codeforces`

.Thank You . Very helpful!!

Lmao this blog appears at the top

Now have to google "What are constructive algorithms codeforces jalotra" to find it on top.