spoj ⟿ classical ⟿ treenum2 ⟿ The art of tree numbers

you can get the problem statement from here.

nice little problem.

tree_num is the sum of distinct powers of 3 with natural exponent. we can solve this problem easily if we can realize that any natural number is sum of distinct powers of 2 with natural exponent.

one illustration that any natural number is the sum of distinct powers of 2 with natural exponent is the binary representation of natural numbers. as with natural numbers we can also represent the tree numbers in binary representation and the conversion’s also similar, instead of sum of powers of 2, it is sum of powers of 3.

https://gist.github.com/2a89c52b3bef33edb85a

PS: be careful with IO. i got tle for cin/cout with ios::sync_with_stdio(0);cin.tie(0);. so either use fast io or scanf, printf

Screenshot from 2015-05-29 19:26:37

a valuable tool for debugging c++

most of the bugs in the code can easily be removed if we can just assert our visualisation with the code that we wrote. In python it is easy to do it by just printing the data structures using the str or repr methods of those data structures. but when it comes to c++ we had to write these pretty printing routines for c++ stdlib containers(often a very small subset).

later I found some fast IO code snippet(from codechef) which automatically handles the type safety.

after that I have added some modification to it, to enable pretty printing for vector, pair, dictionary.

life has been easier ever since. but the source code got ugly as I always have to append that (wrath of C++) code for every small program, and it is UGLY!!!!!!!

so I thought to convert it into an offline header(as just for debugging)… but then I found this amazing header-only-library(cxx-prettyprint) that allows pretty-printing of any container. and it also supports C++11

you can download it from here.

http://louisdx.github.io/cxx-prettyprint/

spoj ➡ classical ➡ epalin ➡ Extend to Palindrome

you can get the problem statement from here.

we have to calculate length of longest palindromic suffix of given string and then concatenate the given string with the part other than the longest palindromic suffix.

As we already know how to generate longest Proper Prefix of string such that it is also it’s suffix (used in KMP algorithm), we have calculate the longest proper pefix of a new string NS.

NS = str(reversed(S)) + S

the longest proper prefix of NS which is also a suffix of NS is our palindromic suffix of S.

https://gist.github.com/eightnoteight/5425fe5ac09b3ce7c83c