Simple question:How to write easy-to-implement brute force solutions? Which techniques do you use (like using next_permutation)?

Thank you for all answers:-)

Before contest

Codeforces Round #680 (Div. 1, based on Moscow Team Olympiad)

09:23:25

Register now »

Codeforces Round #680 (Div. 1, based on Moscow Team Olympiad)

09:23:25

Register now »

*has extra registration

Before contest

Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)

09:23:24

Register now »

Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad)

09:23:24

Register now »

*has extra registration

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

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

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

1 | Errichto | 207 |

2 | Monogon | 196 |

2 | SecondThread | 196 |

4 | vovuh | 188 |

5 | pikmike | 186 |

6 | antontrygubO_o | 185 |

6 | Um_nik | 185 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

Simple question:How to write easy-to-implement brute force solutions? Which techniques do you use (like using next_permutation)?

Thank you for all answers:-)

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/01/2020 04:41:37 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

In this case : B r u t e f o r c e

Thank do not need ((:

Read the problem,stick a smile on your face and start to type.By the time you finish i can truly say you will have a brute force solution on your screen :)

For brute-force I use recursion 90% of the time. If you are brute-forcing something which state can be described by a permutation, then sure — go with next_permutation.

But in general brute-force is not algorithm but an approach so it's hard to give you any real advice that will always work. In general I use backtracking with recursion and that's the most standard approach.

Hi, let's understand brute force using this simple example. Given 2 numbers A and B , find the Greatest Common Divisor(Highest Common factor).

So, lets say you decide to iterate through every possible number < =

min(A,B) and check if the number divides both A and B. Then you keep the maximum number to do so as your answer. In an increasing for loop, that would be the latest number to follow the above condition.This solution is called the brute force solution. Why ? Because you are basically iterating through every possible number to check the answer. Most of the numbers won't divide both A and B, which is a waste of precious computation time. Due to this they have the worst time complexity of all the solution present for a problem.

An optimal method to find GCD is to use Elucid's algorithm, the details of which can be found here

The brute force solution is

O(n) while Elucid's GCD isO(logn)This will definitely help to clear the doubts about bruteforce approach.