Answers to: LUCKY8 - Editorialhttps://discuss.codechef.com/questions/1122/lucky8-editorial<h1>PROBLEM LINKS:</h1>
<p><a href="http://www.codechef.com/problems/LUCKY8">Practice</a><br>
<a href="http://www.codechef.com/JUNE12/problems/LUCKY8">Contest</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Ad-hoc</p>
<h1>QUICK EXPLANATION:</h1>
<p>To make sure that we get a number between <strong>L</strong> and <strong>R</strong>, we need to retain all the digits starting from the most significant digit which are equal in both <strong>L</strong> and <strong>R</strong> as long as we find a difference in the digits of any corresponding position. Next we try to fill the remaining positions using only <strong>4</strong>'s and <strong>7</strong>'s. But before that we need to ensure that we keep the number being formed less than <strong>R</strong> and greater than <strong>L</strong>. Note that it can be equal to either of them. It's enough if we ensure this condition at a single digit position. For example, <strong>L=144239</strong> and <strong>R=144880</strong>. For this, if we for a number <strong>X=1445??</strong>, we have already ensured that it is between <strong>L</strong> and <strong>R</strong> and hence we can fill the other <strong>?</strong>'s using <strong>4</strong>'s and <strong>7</strong>'s. Suppose we form the number like <strong>X=1442??</strong>, then it's still not ensured that <strong>L<=X<=R</strong>. Hence this has to be taken care in one of the next positions. Similarly <strong>X=1448??</strong> is not ensured to be in between.
Once you ensure that it lies in between, we can fill all the lesser significant positions using any combination of <strong>4</strong>'s and <strong>7</strong>'s. We choose the combination for which the product is maximum. </p>
<h1> DETAILED EXPLANATION:</h1>
<p><strong>Tip :</strong>
In this example we'll treat numbers as an array of digits with the most significant digit having the highest index. For example, if the number is <strong>45382</strong> consider it to be an array like the following:</p>
<p><code>index : 0 1 2 3 4
digit : 2 8 3 5 4</code></p>
<p>The problem requires you to find a number between <strong>L</strong> and <strong>R</strong> for which <strong>F4(x)</strong> * <strong>F7(x)</strong> is maximum. Let us try to find a number between <strong>L</strong> and <strong>R</strong> first.
To do that, let's make both the numbers of equal length by appending <strong>0</strong>'s to the smaller number(if required). For example, if you have <strong>L=238</strong> and <strong>R=1209</strong>, append a single '<strong>0</strong>' to <strong>L</strong> to make it <strong>0238</strong>. Now, both <strong>L</strong> and <strong>R</strong> are of length <strong>4</strong>. Next, we try to find the first position where both the numbers differ, starting from the most significant digit. Let's call that position '<strong>i</strong>'. Obviously, <strong>L[i] < R[i]</strong>. As we keep checking for the difference in both the numbers, we count the number of <strong>4</strong>'s (<strong>n4</strong>) and <strong>7</strong>'s (<strong>n7</strong>) encountered so far. If <strong>i<0</strong>, this means both the numbers are same and our answer is <strong>n4*n7</strong>.
Now we can find a number between <strong>L</strong> and <strong>R</strong> in the following way. Suppose the number is <strong>X</strong>. And let <strong>X[y]</strong> denote the <strong>y</strong>th digit of <strong>X</strong>. Keep every digit in <strong>X</strong> from most significant position to <strong>i+1</strong> same as that of <strong>L</strong> and <strong>R</strong>. </p>
<p>For example, <strong>L = 410327</strong> and <strong>R = 410989</strong>. Here i=2 becase <strong>L[k] = R[k]</strong> for k > 2</p>
<p><code>index : 5 4 3 2 1 0
L : 4 1 0 3 2 7
R : 4 1 0 9 8 9
X : 4 1 0 ? ? ?</code></p>
<p>Let's divide the numbers into 3 categories:</p>
<ol>
<li>
<p>The number has it's digit at
position <strong>i</strong> between <strong>L[i]</strong> and <strong>R[i]</strong>
i.e. <strong>L[i] < X[i] < R[i]</strong></p>
</li>
<li>
<p>The number has it's digit at
position <strong>i</strong> equal to <strong>L[i]</strong> i.e. <strong>X[i] =
L[i]</strong></p>
</li>
<li>
<p>The number has it's digit at
position <strong>i</strong> equal to <strong>R[i]</strong> i.e. <strong>X[i] =
R[i]</strong></p>
</li>
</ol>
<p>Let's discuss case 1 first. <strong>L[i] < X[i] < R[i]</strong> ensures that no matter what, X will always be in between <strong>L</strong> and <strong>R</strong>. So we try to maximize the product of <strong>n4</strong> and <strong>n7</strong> by filling the lesser significant digits(i.e. Digits at positions < <strong>i</strong> ) using only <strong>4</strong>'s and <strong>7</strong>'s. We already have <strong>n4 4</strong>'s and <strong>n7 7</strong>'s. So we try out filling all the remaining <strong>i</strong> positions using <strong>s4 4</strong>'s and <strong>s7 7</strong>'s such that <strong>s4 + s7 = i</strong>. Also, if <strong>X[i]</strong> is <strong>4</strong> or <strong>7</strong>, add it to corresponding count (either <strong>n4</strong> or <strong>n7</strong>). Now we try out all different combinations for which <strong>s4 + s7 = i</strong> and look for the one for which <strong>(s4+n4) * (s7+n7)</strong> is maximum. This can be done easily by looping from <strong>j=0</strong> to <strong>i-1</strong> and considering that there are <strong>j 4</strong>'s and <strong>(i - j) 7</strong>'s in the remaining digits of <strong>x</strong>. For example, in the above given case, we can have <strong>X[i] = 4/5/6/7</strong>. And the rest two digits i.e. <strong>X[1]</strong> and <strong>X[0]</strong> can be <strong>44,47,74 and 77</strong> so as to maximize the products.</p>
<p>Next we come to case 2 i.e. <strong>X[i] = L[i]</strong>. To get a number between, <strong>L</strong> and <strong>R</strong>, we can do the following:
<strong>X[j] = L[j]</strong> for <strong>j=i</strong> to <strong>k</strong>. Then, to make <strong>X</strong> larger than <strong>L</strong>, we have <strong>L[k-1] < X[k-1]</strong>. Now we have the same case as 1 with '<strong>i</strong>' modified to <strong>k-1</strong>. We apply the same method and try to maximize the product. But here, we need to do it for every possible '<strong>k</strong>' i.e. from <strong>i</strong> to <strong>0</strong>. </p>
<p>In the case 3, we have <strong>X[i] = R[i]</strong>. To get a number between, <strong>L</strong> and <strong>R</strong>, we can do the following:
<strong>X[j] = R[j]</strong> for <strong>j=i</strong> to <strong>k</strong>. And to have <strong>X</strong> smaller than <strong>R</strong>, we have <strong>X[k-1] < R[k-1]</strong>. Then proceed as case 1. Again, we would have to try out for all possible <strong>k</strong> i.e. from <strong>i</strong> to <strong>0</strong>.</p>
<p>The maximum out of all the three cases will be our final answer.</p>
<p>Let's take a look at the complexity of the solution. Let <strong>N</strong> be the length of <strong>R</strong>.
Case 1 takes atmost N * B operations where B is the number of digits in base 10 i.e. 10.
Case 2 & 3 both have to do the same <strong>N*B</strong> operations as mentioned above. But these operations have to be repeated for different '<strong>k</strong>' which in the worst case will be <strong>N</strong>. Thus there will be total of <strong>N<em>N</em>B</strong> operations.
Hence, the complexity of the solution is <strong>O(T * N * N * B)</strong>.</p>
<p>This solution can be improved in the following manner:</p>
<p>In the existing solution, we can observe that given <strong>n4</strong>, <strong>n7</strong> and <strong>i</strong>, we were calculating the maximum possible product by trying to replace every digit at index less than <strong>i</strong> with either <strong>4</strong> OR <strong>7</strong>. Let's call this value <strong>f(n4, n7, i)</strong>. Instead of looping over for all values between <strong>0</strong> to <strong>i</strong>, the function can give the same results if modified in the following manner:</p>
<p><code>int f(int n4,int n7,int i) {
int k=(n7+i-n4)/2;
if(k*(i-k)>=0) return (n4+k)*(n7+i-k);
k++;
if(k*(i-k)<=0) return (n4+k)*(n7+i-k);
return max((n4+i)*n7,n4*(n7+i));
}</code></p>
<p>This function does the same job in <strong>O(1)</strong> time rather than <strong>O(i)</strong> time. To understand this lets consider that there are <strong>k 4</strong>'s and <strong>(i-k) 7</strong>'s in the remaining i positions. Then the product <strong>F4(x)*F7(x)</strong> will be <strong>(n4+k) * (n7+(i-k))</strong>.
This is a quadratic equation in <strong>k</strong>. Hence the only possible points where the value can be maximum is when <strong>k=(i+n7-n4)/2</strong> or at the end points i.e. <strong>K=0</strong> or <strong>k=i</strong>. Hence this can be calculated in <strong>O(1)</strong> now.</p>
<p>A futher optimization can be to precalculate the values for given <strong>n4</strong>, <strong>n7</strong> and <strong>i</strong> for every pair of <strong>L</strong> and <strong>R</strong> i.e. precalculating <strong>f(L,R,n4,n7,i)</strong> in the following way:</p>
<p><code>int F (int L, int R, int n4, int n7, int i) {
if(L>R) return 0;
int ans=F(n4, n7, i);
if(L<=4 && 4<=R)
MAX(ans,F(n4+1, n7, i));
if(L<=7 && 7<=R)
MAX(ans,F(n4, n7+1, i));
return ans;
}</code></p>
<p>The function is quite easy to understand.</p>
<p>Using the above 2 optimizations, we can get a much efficient solution.</p>
<h1>SETTER'S SOLUTION:</h1>
<p>Will be updated soon.</p>
<h2>APPROACH:</h2>
<p>The problem setter used the above approach in his solution.</p>
<h1>TESTER'S SOLUTION:</h1>
<p>Can be viewed <a href="http://www.codechef.com/download/Solutions/2012/June/Tester/LUCKY8.cpp">here</a>.
</p><h2>APPROACH:</h2>
The problem setter used the above approach in his solution.<p></p>enFri, 15 Jun 2012 14:11:05 +0530Answer by umangkediahttps://discuss.codechef.com/questions/1122/lucky8-editorial/1233<p>At least you can put some comments in the solution. We don't know what each variable denotes.</p>umangkediaFri, 15 Jun 2012 14:11:05 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial/1233Answer by umangkediahttps://discuss.codechef.com/questions/1122/lucky8-editorial/1232<blockquote>
<p>L = 410327 and R = 410989. Here i=2
becase L[k] = R[k] for k > 2</p>
</blockquote>
<p>How i=2 . 'i' the index where both numbers differ?</p>umangkediaFri, 15 Jun 2012 13:23:44 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial/1232Comment by malaykeshav on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1223<p><a href="http://www.codechef.com/viewsolution/1101349">http://www.codechef.com/viewsolution/1101349</a>
i have used the same procedure with the same optimization in my code, yet i got a TLE.
i have tested it on ideone with my own generated test cases. various test files with 2000 test cases each. values ranging from 10^18 to 1.
and it runs well within 0.13 secs for each test file.
may i know which test case is going wrong for my code ?</p>malaykeshavThu, 14 Jun 2012 21:02:59 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1223Answer by sourabh912https://discuss.codechef.com/questions/1122/lucky8-editorial/1222<p>Very Nice Editorial. The quality of the editorials has definitely improved a lot.<br>
</p>sourabh912Thu, 14 Jun 2012 20:00:44 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial/1222Comment by siddharth10246 on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1219<p><a href="/users/1169/betlista">@betlista</a>: anton_lunyov is correct as my previous codes have only this type of output syntax and they are accepted...but i will heed to your suggestion and will try more efficient approach...and yes the other problem!</p>siddharth10246Thu, 14 Jun 2012 16:02:06 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1219Comment by niting112 on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1209<p>Very nicely explained tutorial. Keep up this good work guys !!</p>niting112Thu, 14 Jun 2012 01:03:05 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1209Comment by betlista on anton_lunyov's answerhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1208<p>There should be some "editorial" - "how to test the code", I'm using this approach in long contests (if I know there is some brute force solution).</p>betlistaThu, 14 Jun 2012 00:14:40 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1208Answer by anton_lunyovhttps://discuss.codechef.com/questions/1122/lucky8-editorial/1207<p>Your solution getting WA for this problem every time and it annoys you so much!</p>
<p>Then this is exactly what you need!</p>
<p>The following schematic code allows you to find bug very fast:</p>
<pre>int smart(L, R) {
// your actual solution
}
int F4(L) {
// return F4(L) from the problem statement
}
int F7(L) {
// return F7(L) from the problem statement
}
int main(){
for(L=L0;L<=L1;L++) {
int maxF = 0;
for(R=L;R<=R1;R++) {
maxF = max(maxF, F4(R) * F7(R));
smartF = smart(L, R);
if (maxF != smartF) {
// Ya-hoo! bug is found
}
}
}
}
</pre>
<p>Here L0, L1, R1 are some constants that you can vary in order to cover different types of pairs (L,R). I suggest you to start with L0=1, L1=1000, R1=L+1000.</p>
<p>The advantage of this scheme is that you are not bounded by the slow speed of the brute force solution and can surf through much more pairs (L,R) in very low time.</p>anton_lunyovThu, 14 Jun 2012 00:09:38 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial/1207Comment by anton_lunyov on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1206<p>I think that <code>printf("\n%d",max_prod);</code> is not the problem since the judge is <code>ignore extra white spaces</code>. It is very easy for this problem to test yourself. Just write a brute force solution and compare its answer with the answer generated by your current solutions for various random tests. I will write more detailed scheme as an answer.</p>anton_lunyovWed, 13 Jun 2012 23:53:10 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1206Comment by betlista on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1204<p>Why are you using this? <code>printf("\n%d",max_prod);</code> read more about here - <a href="http://www.codechef.com/wiki/faq#How_does_Codechef_test_whether_my_solution_is_correct_or_not">http://www.codechef.com/wiki/faq#How_does_Codechef_test_whether_my_solution_is_correct_or_not</a> (but this is not the only problem)</p>betlistaWed, 13 Jun 2012 20:41:57 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1204Comment by siddharth10246 on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1203<p>Pls admin or any codeshef user who wants to test himself in finding tricky cases and whoever wants to help...pls refer to my above link and suggest me which case my code is failing...</p>siddharth10246Wed, 13 Jun 2012 20:35:19 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1203Comment by siddharth10246 on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1180<p>link to my solution is <a href="http://www.codechef.com/viewsolution/1106402">http://www.codechef.com/viewsolution/1106402</a> .
Pls u can only provide me test cases where it is failing.</p>siddharth10246Wed, 13 Jun 2012 00:31:44 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1180Comment by betlista on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1178<p>paste the direct link to your submission ;-)</p>betlistaTue, 12 Jun 2012 23:54:05 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1178Comment by siddharth10246 on vamsi_kavala's questionhttps://discuss.codechef.com/questions/1122/lucky8-editorial#1176<p>Pls tell me what is problem with my submitted code 1106402.
I have followed the same approach. And checked atleast 400 cases virtually all icould think of,</p>siddharth10246Tue, 12 Jun 2012 23:00:08 +0530https://discuss.codechef.com/questions/1122/lucky8-editorial#1176