I was getting TLE because it's bigget input is too small :)
It had a very nice tip:
nC2 > 3*nlogn (n>25)
&
nC2 <= 3*nlogn (n<25)

The maximum n was 18 so 18C2=153 > 3*18log18=216 and in a normal mode we often prefer nlogn solutions to n^2 solutions.
But in this problem max n was 18 and I tried many times to optimize my brute force solution (I was getting TLE for few extra ms) to get AC and I couldn't see the tip because n was so small :)
My 2^n*nC2 solution got AC but my 2^n*3*nlogn solution got TLE.

Edited by author 29.01.2015 13:48