Longest Increasing Subsequence of Rectangles

Question

Background

I was looking at some programming Olympiads the other day, and I found this ACM-ICPC Ukraine 2013 pdf.

The part I am working on is Problem D, which consist of finding out how many rectangle can you nest within another rectangle.

Assume a sequence of \$N\$ rectangles \$a_1 \times b_1,a_2\times b_2, ..., a_N \times b_N\$ where each \$ N \to a_N≤b_N \$.

Rectangle \$ a_i×b_i \$ can be put inside rectangle \$ a_k×b_k \$ if \$ (a_i<a_k)\land(b_i<b_k)\$.

We call sequence of rectangles nesting sequence, if each rectangle can be put inside following one.

The task is to write a program that finds the longest nesting subsequence, i. e. the longest nesting sequence among all subsequences of the given sequence.

Note: Rectangles is not to be rotated.

Input

First line of input is \$ N \$ with positive integer no more than 100.000.

The next subsequent inputs are\$ N \$ two integers \$ a_i b_i (1≤a_i≤b_i≤10^9) \$ as the size of the rectangle.

Output

Exactly 1 output, the length of the longest subsequence.

Sample

INPUT              | Output
-------            | _______
5                  | 3
10 10              |
3 7                |
5 5                |
4 9                |
12 12              |

Where the sequence is assumed to be \$ 3×7, 4×9, 12×12 \$

Limits

Time limit is to be less than 2 seconds, with maximum memory usage of 64 MB, based on input specifications.

Code

I figured this must be a Longest Increasing Subsequence with the twist of rectangles quiz, and I got the correct output based on the prompt.

However I am not too sure of the code, code review is appreciated!

#include <stdio.h>
#define MAX_ITEMS 100000

struct Rectangle  {  unsigned int w, h; };

unsigned int lis(struct Rectangle a[], unsigned int N)
{
    // lis_counts stores the length of the LIS
    // Mx stores maximum value
    unsigned int lis_counts[N], Mx;
    lis_counts[0] = 1;
    for (int i = 1; i < N; i++)
    {
        Mx = 0;
        // For each rectangles, check if it is a part of LIS
        for (int j = 0; j < i; j++) if (a[i].w > a[j].w && a[i].h > a[j].h)
            Mx = (Mx > lis_counts[j]) ? Mx : lis_counts[j];
        lis_counts[i] = Mx + 1; // Update the length of LIS
    }

    Mx = 0;
    for (int i = 0; i < N; i++) Mx = (Mx > lis_counts[i]) ? Mx : lis_counts[i];
    return Mx;
}

int main()
{
  unsigned int N, i;
  scanf("%d", &N);              // Read N inputs
  if (0 > N || N > MAX_ITEMS) {
    printf(0);
    return 1;
  }
  struct Rectangle rects[N];
  for (i = 0; i < N; i++){
    scanf("%d", &rects[i].w);   // Read width
    scanf("%d", &rects[i].h);   // Read height
  }
  printf("%d", lis(rects, N));  // Print LIS of rectangles
}

Answer 1

General Observations

Overall a well structure program, but it could be more readable. The program is not completely portable since it uses variable array size and older versions of C or versions of C for embedded systems may not support it. What you are calling dynamic-programming used to include calls to malloc() or calloc() and in many cases still does.

Use typedef for Struct Declarations

The code could be made shorter if typedef is used in the struct Rectangle declaration.

typedef struct rectangle
{
    unsigned int w, h;
} Rectangle;

By using the typedef keyword you are creating a new type of variable. Then the rest of the code where you use the struct is simplified:
In main() the declaration of the array

    Rectangle rects[N];

In the declaration of the function lis():

unsigned int lis(Rectangle a[], unsigned int N)

While this doesn't greatly enhance a small program like this, think of the number of lines it would simplify in a much larger program where Rectangle was used in more places.

For additional information see these Stack Overflow questions:
Why should we typedef a struct?
and
Difference between struct and typedef struct.

Readability and Maintainability

There are too many places in the code where things would be more readable and maintainable if they were on multiple lines rather than a single line. Examples:

In the code in the question the Rectangle declaration is:

struct Rectangle  {  unsigned int w, h; };

This doesn't allow easy modification if additional members of the struct are needed, it would be break this up into multiple lines like this:

struct Rectangle
{
    unsigned int w;
    unsigned int h;
};

Adding additional members then just means adding new lines to the struct definition.

These 2 lines are overly complex and it is very easy to miss the if statement in the for loop.

        // For each rectangles, check if it is a part of LIS
        for (int j = 0; j < i; j++) if (a[i].w > a[j].w && a[i].h > a[j].h)
            Mx = (Mx > lis_counts[j]) ? Mx : lis_counts[j];

The code is also very difficult to modify if it needs to be maintained. While the following code uses a lot more vertical space, it is much easier to maintain the code:

        // For each rectangles, check if it is a part of LIS
        for (int j = 0; j < i; j++)
        {
            if (a[i].w > a[j].w && a[i].h > a[j].h)
            {
                Mx = (Mx > lis_counts[j]) ? Mx : lis_counts[j];
            }
        }

The same can be said about this line of code:

    for (int i = 0; i < N; i++) Mx = (Mx > lis_counts[i]) ? Mx : lis_counts[i];

Increase the Warning Level When You Compile

When you compile with a C compiler it is generally a good idea to use the -Wall option. This will report any questionable code in the program, as an example there are 2 places in the code where there is a type mismatch between unsigned int and int, the variable N is declared as unsigned int, but the variables i and j are declared as integers, this can lead to problems when comparing the values. Variables that index arrays should generally be unsigned int since a negative index will generally index outside the bounds of the array. It is also important to note that an array index is a size variable, there is a special unsigned integer type in C for sizes called size_t. This is the variable type returned by the sizeof(OBJECT) function, and I find it very useful to use it in memory allocation and array indexing.

unsigned int lis(Rectangle a[], size_t N)
{
    // lis_counts stores the length of the LIS
    // Mx stores maximum value
    unsigned int lis_counts[MAX_ITEMS], Mx;
    lis_counts[0] = 1;
    for (size_t i = 1; i < N; i++)
    {
        Mx = 0;
        // For each rectangles, check if it is a part of LIS
        for (size_t j = 0; j < i; j++)
        {
            if (a[i].w > a[j].w && a[i].h > a[j].h)
            {
                Mx = (Mx > lis_counts[j]) ? Mx : lis_counts[j];
            }
        }
        lis_counts[i] = Mx + 1; // Update the length of LIS
    }

    Mx = 0;
    for (size_t i = 0; i < N; i++) Mx = (Mx > lis_counts[i]) ? Mx : lis_counts[i];
    return Mx;
}

2 Possible Bug in main()

The printf(0); statement in main() generates a warning in my compiler, since a string is required by the printf(STRING) statement. Depending on the implementation it isn't clear what this statement might do.

The second possible issue is that height and width can be up to 10^9. These values may be larger than an int in some implementations of C (int is only guarenteed to be 2 bytes wide, but it depends on the implementation). The sizes may turn out to be negative in this case, it can definitely cause integer overflow, you might need either long or long long depending on the implementation.

Code Simplification in main()

The pair of scanf() statements in the for loop to input the rectangles can be simplified into a single scanf() statement since the scanf() function is a variable arguments function.

    for (i = 0; i < N; i++) {
        scanf("%d %d\n", &rects[i].w, &rects[i].h);
    }

The scanf() function returns an integer value that indicates whether the read was successful or not, but this code ignores it.