LUCKY8 - Editorial
<h1>PROBLEM LINKS:</h1>
[Practice][1]
[Contest][2]
<h1>DIFFICULTY:</h1>
Easy
<h1>PREREQUISITES:</h1>
Ad-hoc
<h1>QUICK EXPLANATION:</h1>
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.
<h1> DETAILED EXPLANATION:</h1>
**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 **y**th 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. **X[1]** 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 **N*N*B** 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.
<h1>SETTER'S SOLUTION:</h1>
Will be updated soon.
<h2>APPROACH:</h2>
The problem setter used the above approach in his solution.
<h1>TESTER'S SOLUTION:</h1>
Can be viewed [here][3].
<h2>APPROACH:</h2>
The problem setter used the above approach in his solution.
[1]: http://www.codechef.com/problems/LUCKY8
[2]: http://www.codechef.com/JUNE12/problems/LUCKY8
[3]: http://www.codechef.com/download/Solutions/2012/June/Tester/LUCKY8.cpp