Find the minimum number of MS Paint operations to fill a rectangle

Question

I found this problem somewhere in a contest and haven't been able to come up with a solution yet.

I can "select", "copy", "insert" and "move" in another place a figures on the screen. Initially I have the rectangle with size 1x1. What the least quantity of these operations I have to do for building of another rectangle, which size is AxB.

Here is my wrong code:

#include <iostream>
#include <cmath>
#define size 1002
using namespace std;

int main()
{
    int painta[size];
    int paintb[size];
    int i,j,a,b,temp;

    cin >> a >> b;
    if (a>b)
    {
        temp=a;
        a=b;
        b=temp;
    }

    painta[1]=4;
    for (i=2; i<=a; i++)
        painta[i]=painta[i-1]+2;

    for (i=2; i<=a; i++)
    {
        painta[2*i]=min(painta[i]+4,painta[2*i]);
        for (j=3*i; j<=a; j+=i)
        {
            painta[j]=min(painta[j-i]+2,painta[j]);
        }
    }

    paintb[1]=painta[a];
    paintb[2]=paintb[1]+4;

    for (i=3; i<=b; i++)
        paintb[i]=paintb[i-1]+2;

    for (i=2; i<=b; i++)
    {
        paintb[2*i] = min(paintb[i]+4,paintb[2*i]);
        for (j=3*i; j<=b; j+=i)
        {
            paintb[j]=min(paintb[j-i]+2,paintb[j]);
        }
    }
    cout << paintb[b] << endl;
    return 0;
}

Here is the link: http://www.e-olymp.com/en/problems/18

Answer 1

Your approach is okay, though you've made some implementation mistakes that you could have found by checking some small testcases.

For example, one failing testcase is 1 2, where your program gives the answer 8, although 6 is correct. This is because you should have a > b instead of b > a for your algorithm to work:

-    if (a>b)
+    if (a<b)

Now we still have problems with testcases like 1 7. The correct answer is 14, but your program answers 16. The reason is that you don't allow for overlapping inserts: Starting from a rectangle of size 1x2, we can use the sequence select, copy, insert+move, insert+move, insert+move, insert+move to get a rectangle of size 1x7. Considering this makes the program only slightly more complicated:

@@ -24,9 +24,10 @@
     for (i=2; i<=a; i++)
     {
         painta[2*i]=min(painta[i]+4,painta[2*i]);
-        for (j=3*i; j<=a; j+=i)
+        for (j=2*i+1; j<=a; j++)
         {
-            painta[j]=min(painta[j-i]+2,painta[j]);
+            int steps = (j - i - 1) / i;
+            painta[j]=min(painta[2*i]+2*steps,painta[j]);
         }
     }

@@ -39,9 +40,10 @@
     for (i=2; i<=b; i++)
     {
         paintb[2*i] = min(paintb[i]+4,paintb[2*i]);
-        for (j=3*i; j<=b; j+=i)
+        for (j=2*i+1; j<=b; j++)
         {
-            paintb[j]=min(paintb[j-i]+2,paintb[j]);
+            int steps = (j - i - 1) / i;
+            paintb[j]=min(paintb[2*i]+2*steps,paintb[j]);
         }
     }

Now there's still a small overflow here which might cause the program to crash for large inputs: You are accessing painta[2*i] and paintb[2*i] inside the loops. i can be up to 1000, but the array only has size 1002. Easy enough to fix:

@@ -5,12 +5,12 @@

 int main()
 {
-    int painta[size];
-    int paintb[size];
+    int painta[size*2];
+    int paintb[size*2];
     int i,j,a,b,temp;

Et voila, it passes all the test cases.