search

Spookiel / British-Informatics-Olympiad-Solutions

Contains python solutions for the British Informatics olympiad
24 stars 9 forks source link

B.I.O. 2021 Q1c cannot be realistically computed. #1

Closed NobleOMD closed 2 years ago

NobleOMD commented 2 years ago

Hi, been working on this question for a while now, have gotten to the point at which I'm looking for solutions. Your code for B.I.O. 2021 Q1c will get to the solution but my computer probably won't calculate it until the heat death of the universe. Is there something I am missing or just more power?

teymour-aldridge commented 2 years ago

It's definitely infeasible (the algorithm generates all 25! possibilities, which is something in the range of 10^25 possible permutations, and checks each one in turn).

In #2 I've suggested an alternative approach.

NobleOMD commented 2 years ago

Ty, your explanation was really helpful I think I need to learn binary trees properly and also dynamic programming a bit better. I am going to look through the lecture PowerPoint you referenced but what would you suggest to learn binary trees better?