EDITORIAL- CRANIUM 2014

general
,
1

The editorial of CRANIUM 2014 can be viewed here: http://bit.ly/1o4Ukkj

Cheers!
-Apoorv Jindal

1 Like
2

and problems here: http://www.codechef.com/CRNM2014/

3

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.

1 Like
4

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?

5

Two of them (more just intuitive guesses):

  1. write a bruteforce, find a pattern/formula and a way to implement it quickly

  2. 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?