Answers to: NDIFFPAL - Editorialhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/SNCKPA16/problems/NDIFFPAL">Contest</a><br>
<a href="http://www.codechef.com/problems/NDIFFPAL">Practice</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a><br>
<strong>Testers:</strong> <a href="http://www.codechef.com/users/antoniuk1">Vasya Antoniuk</a> and <a href="http://www.codechef.com/users/kevinsogo">Kevin Atienza</a><br>
<strong>Translators:</strong> <a href="http://www.codechef.com/users/antoniuk1">Vasya Antoniuk</a> (Russian), <a href="http://www.codechef.com/users/vnoi">Team VNOI</a> (Vietnamese) and <a href="http://www.codechef.com/users/huzecong">Hu Zecong</a> (Mandarin)<br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/kevinsogo">Kevin Atienza</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Strings, palindromes, ad hoc, dynamic programming</p>
<h1>PROBLEM:</h1>
<p>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. </p>
<h1>QUICK EXPLANATION:</h1>
<p>Print a string of length $N$ of the following form: <code>abcabcabcabcabcabc...</code>. This string has exactly $N$ palindromic substrings. </p>
<h1>EXPLANATION:</h1>
<p>This problem admits many kinds of solutions. We'll first describe the simplest one. </p>
<h1>Simple</h1>
<p>Notice that any string with length $K$ has at least $K$ palindromic substrings, because every single-character substring is palindromic! Thus, the answer, if it exists, must have a length of $\le N$. Unfortunately, most strings of length $K$ actually has <em>strictly more than $K$ palindromic substrings</em>. For example, <code>abababab</code> contains $8$ one-character palindromic substrings, but it also has the substrings <code>aba</code>, <code>bab</code>, <code>ababa</code>, etc., appearing multiple times. In fact, if there is a character appearing twice consecutively, then you automatically have more than $K$ palindromic substrings. In the extreme case, in a string consisting of only one letter like <code>aaaaa...</code>, all substrings are palindromic. </p>
<p>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: <code>abcabcabcabcabcabc...</code>. It's easy to see why it doesn't have any palindromic substring of length $> 1$: any substring of length $> 1$ has at least one of the following substrings: <code>ab</code>, <code>bc</code>, and <code>ca</code>. But the reversals of these substrings don't appear anywhere in the string! </p>
<p>Thus, a very, very simple solution arises: Simply print a string of the form <code>abcabcabcabcabcabc...</code> of length $N$! </p>
<h1>Short</h1>
<p>The 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? </p>
<p>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 <code>aaaaa...</code>. If the length is $K$, then there are $1 + 2 + 3 + \ldots + K = K(K+1)/2$ palindromic substrings. Thus, to form a string with $N$ palindromic substrings, we simply find a $K$ such that $K(K+1)/2 = N$. Unfortunately, not all $N$s can be represented as $K(K+1)/2$. In fact, such numbers are rare! Below $x$, there are only approximately $\sqrt{2x}$ such values. </p>
<p>The idea in this solution is to append such single-character strings together to form one large string. For example, consider the strings <code>aaa...aaabbb...bbb</code>. Suppose there are $A$ <code>a</code>s and $B$ <code>b</code>s. It's easy to see that no palindromic substrings containing an <code>a</code> and a <code>b</code> because if so, the substring <code>ab</code> would appear, but the reversal, <code>ba</code>, doesn't appear anywhere in the string! Thus, there are $A(A+1)/2 + B(B+1)/2$ palindromic substrings. Similarly, <code>aaa...aaabbb...bbbccc...ccc</code> has $A(A+1)/2 + B(B+1)/2 + C(C+1)/2$ substrings, etc..</p>
<p>So our goal is to find a representation of $N$ as a sum of <a href="https://en.wikipedia.org/wiki/Triangular_number"><em>triangle numbers</em></a> 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 <em>last summand</em>. Specifically, if $k(k+1)/2$ is the last summand in the representation, then:<br>
$$F(N) = \min_{\frac{k(k+1)}{2} \le N} \left(k + F\left(N - \frac{k(k+1)}{2}\right)\right)$$
Our base case here is simply $F(0)$. Along with $F(N)$, we also store the $k$ that minimizes the above, so that we can reconstruct the representation! </p>
<p>The following pseudocode illustrates this:</p>
<pre><code>BOUND = 10011
F[0..BOUND]
K[0..BOUND]
for N = 1..BOUND:
F[N] = INFINITY
for k=0 increasing where k*(k+1)/2 <= N:
cost = k + F[N - k*(k+1)/2]
if F[N] > cost:
F[N] = cost
K[N] = k // store the k that minimizes
</code></pre>
<p>Now, to find the representation of some $N$, we simply use the <code>K</code> array:</p>
<pre><code>def find_representation(N):
rep = []
while N > 0:
k = K[N]
rep.append(k)
N -= k*(k+1)/2
return rep
</code></pre>
<p>Finally, we can construct the string itself using the representation with something like this:</p>
<pre><code>alphabet = 'abcdefghijklmnopqrstuvwxyz'
def construct(N):
rep = find_representation(N)
s = ''
for i=0..rep.length-1:
append alphabet[i] to s rep[i] times
return s
</code></pre>
<p>With this answer, it turns out that you only need a string of at most $161$ characters, and at most $5$ distinct characters! </p>
<h1>Investigating the shortest possible strings</h1>
<p>The 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$: <code>aaaaaabbcd</code>. But in fact a shorter string is possible: <code>aaaaaabaa</code>. </p>
<p>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. </p>
<pre><code> N opt string
1 1 a
2 2 ab
3 2 aa
4 3 aab
5 4 aabc
6 3 aaa
7 4 aaab
8 5 aaabc
9 5 aaaba
10 4 aaaa
11 5 aaaab
12 6 aaaabc
13 6 aaaaba
14 7 aaaabac
15 5 aaaaa
16 6 aaaaab
17 7 aaaaabc
18 7 aaaaaba
19 8 aaaaabac
20 8 aaaaabab
21 6 aaaaaa
22 7 aaaaaab
23 8 aaaaaabc
24 8 aaaaaaba
25 9 aaaaaabac
26 9 aaaaaabab
27 9 aaaaaabaa
28 7 aaaaaaa
29 8 aaaaaaab
30 9 aaaaaaabc
31 9 aaaaaaaba
32 10 aaaaaaabac
33 10 aaaaaaabab
34 10 aaaaaaabaa
35 11 aaaaaaabaac
36 8 aaaaaaaa
37 9 aaaaaaaab
38 10 aaaaaaaabc
39 10 aaaaaaaaba
40 11 aaaaaaaabac
41 11 aaaaaaaabab
42 11 aaaaaaaabaa
43 12 aaaaaaaabaac
44 12 aaaaaaaabaab
45 9 aaaaaaaaa
46 10 aaaaaaaaab
47 11 aaaaaaaaabc
48 11 aaaaaaaaaba
49 12 aaaaaaaaabac
50 12 aaaaaaaaabab
51 12 aaaaaaaaabaa
52 13 aaaaaaaaabaac
53 13 aaaaaaaaabaab
54 14 aaaaaaaaabaabc
55 10 aaaaaaaaaa
</code></pre>
<h1>Time Complexity:</h1>
<p><a href="https://en.wikipedia.org/wiki/Output-sensitive_algorithm">$O(N)$</a></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKPA16/Setter/NDIFFPAL.cpp">Setter</a> <br>
<a href="http://www.codechef.com/download/Solutions/SNCKPA16/Tester/NDIFFPAL.py">Tester</a> </p>enSat, 27 May 2017 13:56:39 +0530Answer by akashbhalotiahttps://discuss.codechef.com/questions/81930/ndiffpal-editorial/99201<p>For Java users, this is working fine- </p>
<pre><code>import <a href="http://java.io">java.io</a>.*;
class NDIFFPAL
{
public static void main(String args[]) throws IOException
{
BufferedReader br=new BufferedReader
(new InputStreamReader(<a href="http://System.in">System.in</a>));
int T,N,c,i,j;
String word,s="abcdefghijklmnopqrstuvwxyz";
System.out.println();
T=Integer.parseInt(br.readLine());
for(i=0;i<T;i++)
{
N=Integer.parseInt(br.readLine());
word="";
c=N/26;
for(j=0;j<c;j++)
{
word+=s;
}
c=N%26;
word+=s.substring(0,c);
System.out.println(word);
}
}
}
</code></pre>akashbhalotiaSat, 27 May 2017 13:56:39 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/99201Answer by mohit_97https://discuss.codechef.com/questions/81930/ndiffpal-editorial/83309<p><a href="/users/126197/arch_abs">@arch_abs</a> this method is working fine in c++.I got an AC on first go.</p>mohit_97Sun, 17 Jul 2016 20:19:31 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/83309Answer by jackpotmanhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial/83303<p>I describe my approach on my blog too: <a href="http://passionsprimitive.blogspot.co.uk/2016/07/codechef-ndiffpal.html">http://passionsprimitive.blogspot.co.uk/2016/07/codechef-ndiffpal.html</a></p>
<p>I also instinctively went in for the triangular numbers, without considering the base-case of just using the n-length string of n unique characters (and repeating after exhausting the set).</p>
<p>Here goes:</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>An even better hack is to hard-code the 140 triangular numbers and binary search the array. This would be super-quick.</p>
<p>Take-aways:</p>
<p>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 re-appear a lot in problem solving!
Hard-coding can be king for time limits
ASCII to int and vice-versa</p>
<p>Here is the solution: <a href="https://github.com/jubinchheda/codechef/raw/master/ndiffpal.py">https://github.com/jubinchheda/codechef/raw/master/ndiffpal.py</a></p>jackpotmanSun, 17 Jul 2016 17:35:36 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/83303Comment by debjitdj on debjitdj's answerhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial#82048<p>I prefer ideone.</p>
<p>WA code- <a href="https://ideone.com/5tWhzH">https://ideone.com/5tWhzH</a></p>
<p>AC code- <a href="https://ideone.com/RoGIe7">https://ideone.com/RoGIe7</a></p>
<p>can you explain now? :D</p>debjitdjWed, 08 Jun 2016 19:13:42 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial#82048Comment by admin123 on debjitdj's answerhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial#82032<p>because of null at the last of character array you can see this on codechef code, compile and run </p>
<p>just give n=30 and see the output</p>admin123Wed, 08 Jun 2016 01:22:36 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial#82032Comment by debjitdj on pankaj_chopra's answerhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial#82010<p>Ooohhh!!...wow!! :P Eurekaaaaaa!!! So, ideone and codechef online ide are giving different outputs!</p>debjitdjTue, 07 Jun 2016 00:41:24 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial#82010Comment by pankaj_chopra on pankaj_chopra's answerhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial#82006<p><a href="/users/93909/debjitdj">@debjitdj</a> In Codechef Online IDE, both are giving different outputs.</p>pankaj_chopraMon, 06 Jun 2016 22:28:06 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial#82006Comment by debjitdj on pankaj_chopra's answerhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial#82005<p>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.</p>
<p>WA code- <a href="https://ideone.com/5tWhzH">https://ideone.com/5tWhzH</a></p>
<p>AC code- <a href="https://ideone.com/RoGIe7">https://ideone.com/RoGIe7</a></p>debjitdjMon, 06 Jun 2016 22:11:46 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial#82005Answer by pankaj_choprahttps://discuss.codechef.com/questions/81930/ndiffpal-editorial/81995<p>Hey <a href="/users/93909/debjitdj"><a href="/users/93909/debjitdj">@debjitdj</a></a> <strong>cout<< a</strong> prints the characters of the <strong>string a</strong> untill the <strong>NULL character('\0')</strong> occurs in the string.
So, it is important to insert the <strong>NULL character('\0')</strong> in the end of the string.<br>So, you have to replace only<br><strong>char a[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};</strong><br>statement by<br><strong>char a[27]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','\0'};</strong><br><strong>OR</strong><br><strong>char a[]="abcdefghijklmnopqrstuvwxyz";</strong><br>statement to correct your code.<br>Note that,in the latter statement , <strong>'\0'</strong> is not necessary, it is inserted automatically.</p>pankaj_chopraMon, 06 Jun 2016 16:01:19 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/81995Answer by rc1c2https://discuss.codechef.com/questions/81930/ndiffpal-editorial/81994<p>Not able to understand the formula for F(n) in second method. </p>rc1c2Mon, 06 Jun 2016 15:01:02 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/81994Answer by debjitdjhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial/81991<p>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$.</p>
<p>Code- <a href="https://www.codechef.com/viewsolution/10325809">https://www.codechef.com/viewsolution/10325809</a></p>
<p>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?</p>
<p>WA- <a href="https://www.codechef.com/viewsolution/10325602">https://www.codechef.com/viewsolution/10325602</a></p>
<p>AC- <a href="https://www.codechef.com/viewsolution/10325809">https://www.codechef.com/viewsolution/10325809</a></p>debjitdjMon, 06 Jun 2016 13:01:11 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/81991Answer by arch_abshttps://discuss.codechef.com/questions/81930/ndiffpal-editorial/81974<p>The first method (abcabc....) is giving time limit exceeded error on using JAVA..</p>arch_absMon, 06 Jun 2016 00:32:38 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/81974Answer by bhambyahttps://discuss.codechef.com/questions/81930/ndiffpal-editorial/81957<p>Codechef editorials are just amazing! So much detail.</p>bhambyaSun, 05 Jun 2016 22:13:04 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial/81957Comment by bhambya on bhishma's answerhttps://discuss.codechef.com/questions/81930/ndiffpal-editorial#81956<p>It's essentially the same, just that they are using 3 as mod instead of 26.</p>bhambyaSun, 05 Jun 2016 22:12:35 +0530https://discuss.codechef.com/questions/81930/ndiffpal-editorial#81956