The editorial of CRANIUM 2014 can be viewed here: http://bit.ly/1o4Ukkj
Cheers!
-Apoorv Jindal
The editorial of CRANIUM 2014 can be viewed here: http://bit.ly/1o4Ukkj
Cheers!
-Apoorv Jindal
I checked the editorial for the hardest problem, and it looks quite… weird. “Various methods” are mentioned, but the only presented method is what seems to be a basis of an O(N^5) bruteforce; there is never any connection to the O(log N) complexity that’s also mentioned. Besides, the problem itself looks like a specific variation on an NP-complete problem (knapsack), from which I wouldn’t expect a solution other than writing a bruteforce, finding a pattern (or mathematical formula, in this case), and more or less hardwiring it into the code.
I think the ac solutions rely on the fact that no of solutions == no of solutions to
50a + 25b + 10c + 5d + e = n
But i don’t know how to solve from here. You have any ideas?
Two of them (more just intuitive guesses):
write a bruteforce, find a pattern/formula and a way to implement it quickly
matrix exponentiation of some sort (common in combinatorial problems with long long constraints, but I don’t see how)
Yeah, counting solutions by bruteforce is a bit… wat?