PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:Easy PREREQUISITES:Strings, palindromes, ad hoc, dynamic programming PROBLEM:Given $N$, output a string consisting of lowercase letters such that there are exactly $N$ palindromic substrings. Two substrings are considered different if they have different starting / ending positions. QUICK EXPLANATION:Print a string of length $N$ of the following form: EXPLANATION:This problem admits many kinds of solutions. We'll first describe the simplest one. SimpleNotice that any string with length $K$ has at least $K$ palindromic substrings, because every singlecharacter substring is palindromic! Thus, the answer, if it exists, must have a length of $\le N$. Unfortunately, most strings of length $K$ actually has strictly more than $K$ palindromic substrings. For example, But in fact there are ways to construct a string of length $K$ having exactly $K$ palindromic substrings. One of the simplest is a string of the form: Thus, a very, very simple solution arises: Simply print a string of the form ShortThe above solution is probably the simplest you can ever get. But what if we are conserving letters, i.e., we want the string to be as short as possible? In that case, we want our string to actually have lots of palindromic substrings of length $> 1$. As mentioned above, an example of this is a string consisting of only one character like The idea in this solution is to append such singlecharacter strings together to form one large string. For example, consider the strings So our goal is to find a representation of $N$ as a sum of triangle numbers where the sum of the bases is as small as possible. We can achieve this using dynamic programming: Let $F(N)$ be the smallest sum of bases for any representation of $N$ as a sum of triangle numbers. Then a simple recurrence can be derived by enumerating all possibities for the last summand. Specifically, if $k(k+1)/2$ is the last summand in the representation, then: The following pseudocode illustrates this:
Now, to find the representation of some $N$, we simply use the
Finally, we can construct the string itself using the representation with something like this:
With this answer, it turns out that you only need a string of at most $161$ characters, and at most $5$ distinct characters! Investigating the shortest possible stringsThe algorithm above produces some really short strings. Unfortunately, they aren't the shortest possible. The smallest counterexample is $N = 26$: The algorithm produces a string of length $10$: In fact, it doesn't seem easy to figure out the shortest possible string. So unfortunately I don't have the answer for that :( If you wish to investigate it, here are the optimal answers for every $N \le 55$, along with an optimal string. Perhaps you can find a pattern and then derive a formula for the optimal string.
Time Complexity:AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 04 Jun '16, 06:20

Codechef editorials are just amazing! So much detail. answered 05 Jun '16, 22:13

I have used something different. I have simply printed $abcdef....xyzabcdef.....xyzabc...$ upto length $N$. This string has exactly $N$ palindromic substrings with length $1$. Code https://www.codechef.com/viewsolution/10325809 But I have some doubt. My first submission was WA, though I did the same thing, just with little bit changes. Can anyone figure out the fault? answered 06 Jun '16, 13:01
because of null at the last of character array you can see this on codechef code, compile and run just give n=30 and see the output
(08 Jun '16, 01:22)
I prefer ideone. WA code https://ideone.com/5tWhzH AC code https://ideone.com/RoGIe7 can you explain now? :D
(08 Jun '16, 19:13)

For Java users, this is working fine
answered 27 May '17, 13:56

The first method (abcabc....) is giving time limit exceeded error on using JAVA.. answered 06 Jun '16, 00:32

Not able to understand the formula for F(n) in second method. answered 06 Jun '16, 15:01

Hey @debjitdj cout<< a prints the characters of the string a untill the NULL character('\0') occurs in the string.
So, it is important to insert the NULL character('\0') in the end of the string. answered 06 Jun '16, 16:01
Have you tested the codes? In both the cases the output remains same (As expected). But I don't know why it is giving WA in codechef submission. WA code https://ideone.com/5tWhzH AC code https://ideone.com/RoGIe7
(06 Jun '16, 22:11)
@debjitdj In Codechef Online IDE, both are giving different outputs.
(06 Jun '16, 22:28)
2
Ooohhh!!...wow!! :P Eurekaaaaaa!!! So, ideone and codechef online ide are giving different outputs!
(07 Jun '16, 00:41)

I describe my approach on my blog too: http://passionsprimitive.blogspot.co.uk/2016/07/codechefndiffpal.html I also instinctively went in for the triangular numbers, without considering the basecase of just using the nlength string of n unique characters (and repeating after exhausting the set). Here goes: As a first observation, if we have all characters of a string identical, e.g. "aaa", we will see that there are 6 different index combo's ==> (1,1) (1,2) (1,3) (2,2) (2,3) (3,3). After some scribling around for relationship of string length and number of index combo's, this reduces easily to Triangular numbers. Now, if we think of all the input to the puzzle that are not triangular numbers, if we reduce that number to a sum of triangular numbers that have appeared before it. e.g. 13 = 6 + 6 + 1 => so, one can represent this as "aaabbbc". The largest input possible is 10000 => closest floor triangular number to this is 9870  so the 140 index triangular number. I think might as well generate all the triangular numbers till we hit the largest input and then decomposition, finally link that to printing unique strings. On second thought that it very inefficient since most of those will not be needed. What we really need is a way to find the largest triangular number smaller than a given number and then note that and reduce the running number by this triangular number. An even better hack is to hardcode the 140 triangular numbers and binary search the array. This would be superquick. Takeaways: There were much easier solutions acceptable since this is a very 'loose' problem. e.g. just repeating the character set and printing the number of character as the input would suffice as a decent base case. Figurate Number are an interesting field to explore further  this will probably reappear a lot in problem solving! Hardcoding can be king for time limits ASCII to int and viceversa Here is the solution: https://github.com/jubinchheda/codechef/raw/master/ndiffpal.py answered 17 Jul '16, 17:35
