CODEWITHSUNDEEP
algorithmdynamic-programming
Santanu
Santanu

Reputation: 893

Where is the mistake in my dp approach here? https://www.spoj.com/problems/AE00/

Problem:

Byteman has a collection of N squares with side 1. How many different rectangles can he form using these squares?

Two rectangles are considered different if none of them can be rotated and moved to obtain the second one. During rectangle construction, Byteman can neither deform the squares nor put any squares upon any other ones.

Input The first and only line of the standard input contains one integer N (1 <= N <= 10000).

Output The first and only line of the standard output should contain a single integer equal to the number of different rectangles that Byteman can form using his squares.

Example For the input data: 6

the correct result is: 8

My Solution:

public class Rectangles {
    public void solve(int testNumber, Reader in, OutputWriter out) {
        try {
            while(true) {
                int N = in.ni();
                out.printLine(result(N));
            }
        } catch (Exception ee) { }
    }

    private long result(int n) {
        long[] res = new long[n+2];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        for(int i=3;i<=n;i++) {
            if(i%2 == 0) {
                res[i] = 3 + res[i-2];
            } else {
                res[i] = 1 + res[i-1];
            }
        }
        return res[n];
    }
}

My DP Approach:

For 0 squares: Result is 0
For 1 square: Result is 1: f(1) = 1
For 2 squares: Result is 2 : f(2) = 2
Now for f(3) = f(2) + 1 more square
With 1 more square we can only place it horizontally and hence 
f(3) = f(2)+1, generalizing, when n is ODD : f(n) = f(n-1) + 1
when n is EVEN: we use two squares which can make up to 3 rectangles, two horizontally([SQ] & [SQ][SQ]) plus one on top of the other, so total 3 possibilities, and hence f(n) when n is EVEN: f(n) = f(n-2) + 3.

Upvotes: 1

Views: 335

Answers (3)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

For a given N all possible different rectangles are:

  1x1 1x2 1x3 1x4 ... 1x[N/1]
      2x2 2x3 2x4 ... 2x[N/2] // 2x1 is equals to 1x2 
          3x3 3x4 ... 3x[N/3] // 3x1 and 3x2 are equal to 1x3 and 2x3
                  ... 
                      Mx[N/M]

Where [...] means integer part (floor) or, in other words, [N/M] is integer division. Since N is not very large, we can just loop

C# Code:

private static int Solution(int value) {
  int result = 0;

  for (int i = 1; ; ++i) {
    int upTo = value / i;

    if (i > upTo)
      return result;

    result += (upTo - i + 1);
  }
}

Demo:

  int[] tests = new int[] {
    0,
    1,
    6,
    9,
    10000,
  };

  string report = string.Join(Environment.NewLine, tests
    .Select(test => $"{test,5} -> {Solution(test),5}"));

  Console.Write(report);

Outcome:

    0 ->     0
    1 ->     1
    6 ->     8
    9 ->    13
10000 -> 46884

Upvotes: 1

Alfe
Alfe

Reputation: 59416

I propose to consider how many rectangles with the smaller(!) side being length x can exist. Then loop through all possible values for x and sum them up. Pseudo-code:

result = 0
for x in 1 .. floor(sqrt(n)):
  result += number_of_rectangles_with_smaller_side(x)

And I think number_of_rectangles_with_smaller_side(x) is floor(n / x) - x + 1 but you should double check that ;-)

Upvotes: 0

anatolyg
anatolyg

Reputation: 28241

Not all rectangles are obtained from adding one square to an existing rectangle.

For example, if N = 9, one of the rectangles is 3x3. Your DP approach will not find it. Or, in other words, f(9) > f(8) + 1.

Upvotes: 1

Related Questions