LUCKY8 - Editorial

PROBLEM LINKS:

Practice
Contest

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc

QUICK EXPLANATION:

To make sure that we get a number between L and R, we need to retain all the digits starting from the most significant digit which are equal in both L and R as long as we find a difference in the digits of any corresponding position. Next we try to fill the remaining positions using only 4’s and 7’s. But before that we need to ensure that we keep the number being formed less than R and greater than L. 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, L=144239 and R=144880. For this, if we for a number X=1445??, we have already ensured that it is between L and R and hence we can fill the other ?'s using 4’s and 7’s. Suppose we form the number like X=1442??, then it’s still not ensured that L<=X<=R. Hence this has to be taken care in one of the next positions. Similarly X=1448?? 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 4’s and 7’s. We choose the combination for which the product is maximum.

DETAILED EXPLANATION:

Tip :
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 45382 consider it to be an array like the following:

index : 0 1 2 3 4
digit : 2 8 3 5 4

The problem requires you to find a number between L and R for which F4(x) * F7(x) is maximum. Let us try to find a number between L and R first.
To do that, let’s make both the numbers of equal length by appending 0’s to the smaller number(if required). For example, if you have L=238 and R=1209, append a single ‘0’ to L to make it 0238. Now, both L and R are of length 4. Next, we try to find the first position where both the numbers differ, starting from the most significant digit. Let’s call that position ‘i’. Obviously, L[i] < R[i]. As we keep checking for the difference in both the numbers, we count the number of 4’s (n4) and 7’s (n7) encountered so far. If i<0, this means both the numbers are same and our answer is n4*n7.
Now we can find a number between L and R in the following way. Suppose the number is X. And let X[y] denote the yth digit of X. Keep every digit in X from most significant position to i+1 same as that of L and R.

For example, L = 410327 and R = 410989. Here i=2 becase L[k] = R[k] for k > 2

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 ? ? ?

Let’s divide the numbers into 3 categories:

  1. The number has it’s digit at
    position i between L[i] and R[i]
    i.e. L[i] < X[i] < R[i]

  2. The number has it’s digit at
    position i equal to L[i] i.e. X[i] =
    L[i]

  3. The number has it’s digit at
    position i equal to R[i] i.e. X[i] =
    R[i]

Let’s discuss case 1 first. L[i] < X[i] < R[i] ensures that no matter what, X will always be in between L and R. So we try to maximize the product of n4 and n7 by filling the lesser significant digits(i.e. Digits at positions < i ) using only 4’s and 7’s. We already have n4 4’s and n7 7’s. So we try out filling all the remaining i positions using s4 4’s and s7 7’s such that s4 + s7 = i. Also, if X[i] is 4 or 7, add it to corresponding count (either n4 or n7). Now we try out all different combinations for which s4 + s7 = i and look for the one for which (s4+n4) * (s7+n7) is maximum. This can be done easily by looping from j=0 to i-1 and considering that there are j 4’s and (i - j) 7’s in the remaining digits of x. For example, in the above given case, we can have X[i] = 4/5/6/7. And the rest two digits i.e. X1 and X[0] can be 44,47,74 and 77 so as to maximize the products.

Next we come to case 2 i.e. X[i] = L[i]. To get a number between, L and R, we can do the following:
X[j] = L[j] for j=i to k. Then, to make X larger than L, we have L[k-1] < X[k-1]. Now we have the same case as 1 with ‘i’ modified to k-1. We apply the same method and try to maximize the product. But here, we need to do it for every possible ‘k’ i.e. from i to 0.

In the case 3, we have X[i] = R[i]. To get a number between, L and R, we can do the following:
X[j] = R[j] for j=i to k. And to have X smaller than R, we have X[k-1] < R[k-1]. Then proceed as case 1. Again, we would have to try out for all possible k i.e. from i to 0.

The maximum out of all the three cases will be our final answer.

Let’s take a look at the complexity of the solution. Let N be the length of R.
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 N*B operations as mentioned above. But these operations have to be repeated for different ‘k’ which in the worst case will be N. Thus there will be total of NNB operations.
Hence, the complexity of the solution is O(T * N * N * B).

This solution can be improved in the following manner:

In the existing solution, we can observe that given n4, n7 and i, we were calculating the maximum possible product by trying to replace every digit at index less than i with either 4 OR 7. Let’s call this value f(n4, n7, i). Instead of looping over for all values between 0 to i, the function can give the same results if modified in the following manner:

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));
}

This function does the same job in O(1) time rather than O(i) time. To understand this lets consider that there are k 4’s and (i-k) 7’s in the remaining i positions. Then the product *F4(x)F7(x) will be (n4+k) * (n7+(i-k)).
This is a quadratic equation in k. Hence the only possible points where the value can be maximum is when k=(i+n7-n4)/2 or at the end points i.e. K=0 or k=i. Hence this can be calculated in O(1) now.

A futher optimization can be to precalculate the values for given n4, n7 and i for every pair of L and R i.e. precalculating f(L,R,n4,n7,i) in the following way:

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;
}

The function is quite easy to understand.

Using the above 2 optimizations, we can get a much efficient solution.

SETTER’S SOLUTION:

Will be updated soon.

APPROACH:

The problem setter used the above approach in his solution.

TESTER’S SOLUTION:

Can be viewed here.

APPROACH:

The problem setter used the above approach in his solution.

11 Likes

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,

paste the direct link to your submission :wink:

link to my solution is http://www.codechef.com/viewsolution/1106402 .
Pls u can only provide me test cases where it is failing.

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…

Why are you using this? printf("\n%d",max_prod); read more about here - http://www.codechef.com/wiki/faq#How_does_Codechef_test_whether_my_solution_is_correct_or_not (but this is not the only problem)

I think that printf("\n%d",max_prod); is not the problem since the judge is ignore extra white spaces. 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.

Your solution getting WA for this problem every time and it annoys you so much!

Then this is exactly what you need!

The following schematic code allows you to find bug very fast:

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
         }
      }
   }
}

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.

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.

4 Likes

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).

Very nicely explained tutorial. Keep up this good work guys !!

@betlista: 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!

Very Nice Editorial. The quality of the editorials has definitely improved a lot.

http://www.codechef.com/viewsolution/1101349
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 ?

L = 410327 and R = 410989. Here i=2
becase L[k] = R[k] for k > 2

How i=2 . ‘i’ the index where both numbers differ?

At least you can put some comments in the solution. We don’t know what each variable denotes.