Answers to: NAME1 - Editorialhttps://discuss.codechef.com/questions/9717/name1-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/NAME1">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/NAME1">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES</h1>
<p>Ad-Hoc</p>
<h1>PROBLEM</h1>
<p>You are given two strings <b>A</b> and <b>B</b>. You are also given <b>N</b> strings <b>C<sub>1</sub></b>, <b>C<sub>2</sub></b>, ... <b>C<sub>N</sub></b>.</p>
<p>Let <b>C = C<sub>1</sub> + C<sub>2</sub> + ... C<sub>N</sub></b>
where <b>+</b> is the <b>concatenation</b> <b>operator</b> (note that it is <b>not</b> <b>commutative</b>)</p>
<p>Find whether <b>C</b> may be a substring of one of the permutations of <b>A + B</b>.</p>
<h1>QUICK EXPLANATION</h1>
<p>The length of <b>A + B</b> can be <b>80000</b>. Of course, we cannot possibly generate all the permutations of <b>A + B</b>. Let us use some insight.</p>
<p>Lemma: If <b>C</b> is a substring of a permutation of <b>A + B</b>, then there is a permutation of <b>A + B</b> in which <b>C</b> is a prefix.</p>
<p>It is easy to see that if <b>C</b> exists as a substring, we can shift all the characters on the left of the first occurance of <b>C</b>, to the end of the string without affecting the presence of <b>C</b> in the permutation of <b>A + B</b>. Also, if <b>C</b> is a prefix of some permutation of <b>A + B</b>, then it is also a permutation which is proof enough to return a positive answer.</p>
<p>Lemma: If there is no permutation of <b>A + B</b> such that <b>C</b> is a prefix, then there is no permutation of <b>A + B</b> such that <b>C</b> is a substring.</p>
<p>This is easily proven by contradiction. If we assume that there is a permutation of <b>A + B</b> in which <b>C</b> is a substring, then by the previous Lemma we should have a permutation of <b>A + B</b> in which <b>C</b> is a prefix. Thus our assumption cannot be true.</p>
<p>From the above two, we can clearly say</p>
<p><b>C</b> can be a substring of some permutation of <b>A + B</b> iff there is a permutation of <b>A + B</b> of which <b>C</b> is a prefix.</p>
<h1>EXPLANATION</h1>
<p>Since we have the liberty to assume any permutation of <b>A + B</b>, we can treat it as a bag of characters and just try to build a permutation with <b>C</b> as prefix. If we are unable to, then of course we return negative. Otherwise, we can successfully have <b>C</b> as a substring by letting the other characters occupy any position on the left or right of the constructed string <b>C</b> (from characters in <b>A + B</b>).</p>
<p>We can build a count of all the characters in <b>A + B</b> as follows
</p><pre>counts[a ... z] = { 0 }<p></p>
<p>for each character c in A
counts[c]++
for each character c in B
counts[c]++
</p></pre><p></p>
<p>We can construct <b>C</b> by concatenating the given strings. The statement assures us that the length of <b>C</b> is not more than the length of <b>A + B</b>. Then we can one by one reduce the count of the characters in <b>C</b>. If any of the counts become negative, then we know that we cannot choose that character and that <b>C</b> cannot exist as a prefix (as well as substring) of any permutation of <b>A + B</b>.</p>
<pre>for each chatacter c in C
counts[c]--
if counts[c] < 0
return false
return true
</pre>
<p>The complexity of the algorithm is <b>O(|A| + |B| + |C|)</b>.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/NAME1.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/NAME1.cpp">here</a>.</p>enSun, 24 Mar 2019 12:28:46 -0000