Number of "different" rectangles that can be created by 1<=n<=10000 squares..

[crash1989]

I found this question in some programming contest..
Given are N squares with side 1. How many "different" rectangles can one 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, you can neither deform the squares nor put any squares upon any other ones.

sample input : 6
sample output : 8
visit this link to see the 8 rectangles...
https://vn.spoj.pl/content/ae00.jpg

This is my program which works correctly until 192 squares but after 192 it ends abruptly .. Pls help me with this error ..
By the way I use DevCpp for coding C++ progs

.
#include<iostream>
using namespace std;
int main()
{
long int sq,tmp=1;
cin>>sq;     //Input number of squares
int rect=1;
for(int j=2;j<=sq;j++)
{
tmp=1;
for(int i=2;i<=j;i++)
if(j%i==0)     //finding the relevant divisors which can be rectangles 
{
if(j==2 || j/tmp>1)
{
rect++;
}
tmp=tmp*i;
}
}
cout<<rect<<endl;  //print number of rectangles possible
system("pause");
}

[kvprajapati]

Result truncated.

tmp=tmp*i;

Use, long long tmp;

[crash1989]

Now its giving an error for numbers greater than 768 ...
Is there a way of Increasing the size of tmp so that it can handle very large integers ..

[tux4life]

Could you please post using code tags?
Information about code-tags is posted all over the website :

1) in the Rules you were asked to read when you registered
2) in the text at the top of this forum
3) in the announcement at the top of this forum titled Please use BB Code and inlinecode tags
4) in the sticky post above titled Read Me: Read This Before Posting
5) any place CODE tags were used
6) Even on the background of the box you actually typed your message in

>Is there a way of Increasing the size of tmp so that it can handle very large integers ..
Yes, use a big-number library like: "GNU MP Bignum Library"

[siddhant3s]

Guess what!!
I derived a O(1) formula for the same.
If it is your homework, don't try to copy the formula. I am sure you teacher will ask you derive it if you do so.
[tex]r=floor\left (\frac{3\times n}{2} \right )-1[/tex]

where floor() is the greatest integer function
floor(3.2)=3
floor(6.1)=6
floor(6)=6

[VernonDozier]

Guess what!!
I derived a O(1) formula for the same.
If it is your homework, don't try to copy the formula. I am sure you teacher will ask you derive it if you do so.
[tex]r=floor\left (\frac{3\times n}{2} \right )-1[/tex]

where floor() is the greatest integer function
floor(3.2)=3
floor(6.1)=6
floor(6)=6

What does r stand for? If it's the number of rectangles, it's going to flunk right away. Plug in 1 for n.

[tex]r=floor\left (\frac{3\times n}{2} \right )-1[/tex]
[tex]r=floor\left (\frac{3\times 1}{2} \right )-1[/tex]
[tex]r=floor\left (\frac{3}{2} \right )-1[/tex]
[tex]r=floor\left (1.5 \right )-1[/tex]

[tex]r=1 -1 = 0[/tex]

Correct answer should be 1 since you can make one rectangle from one tile. If I'm misinterpreting what r stands for, please explain.

[siddhant3s]

I forgot to mention it, yes n=1 is a exception.
The above formula is valid for n>1
I have realized it the moment I created the formula but just forgot to mention it.

Yes r is number of rectangle

[VernonDozier]

I forgot to mention it, yes n=1 is a exception.
The above formula is valid for n>1
I have realized it the moment I created the formula but just forgot to mention it.

Yes r is number of rectangle

It's also going to break down for any non-prime odd number, like 9. Your formula assumes that there is exactly one way to create a rectangle using an odd number of squares, using all of the squares.

By your formula,

r (8) = floor ((3 times 8) / 2) - 1 = floor (24 / 2) - 1 = 11
r (9) = floor ((3 times 9) / 2) - 1 = floor (27 / 2) - 1 = 12
r (9) - r (8) = 1

r(9) - r(8) = # of rectangles created using exactly 9 squares, which in this case is 2, not 1:

*********

***
***
***

[siddhant3s]

You did not applied my formula correctly.
>>r(9) - r(8) = # of rectangles created using exactly 9 squares, which in this case is
>>2, not 1:
r(9)=# of rectangles created using 9 squares (or less) , which 12
The OP want # of square using n or less squares.
The OP wants r(9)

9 these:
#########
########
#######
######
#####
####
###
##
#

plus 3 these:
 
##
##

###
###

####
####

I think you should check the image posted by op :)
Thanks for your time though/

[VernonDozier]

You did not applied my formula correctly.
>>r(9) - r(8) = # of rectangles created using exactly 9 squares, which in this case is
>>2, not 1:
r(9)=# of rectangles created using 9 squares (or less) , which 12
The OP want # of square using n or less squares.
The OP wants r(9)

9 these:
#########
########
#######
######
#####
####
###
##
#

plus 3 these:
 
##
##

###
###

####
####

I think you should check the image posted by op :)
Thanks for your time though/

I'm familiar with the image. You list 12 combinations. Add this one:

***
***
***

That makes 13, not 12. Your formula is incorrect.

[jephthah]

the formula posted by siddhant is fundamentally flawed. it only appeared to work, because it just happened to be valid for n=2 through n=8. as 'n' increases past 8, the result becomes more and more inaccurate.

n=9 to n=11, the result is off by 1
n=12 to n=14, the result is off by 2
n=15, the result is off by 3
n=16 to n=17, the result is off by 4
n=18 to ... the result is off by 5

etc

[jephthah]

and you don't need a "Big Number Library". you dont even need a long int . 10,000 is easily represented by a regular integer

the way to approach this problem is by summation:

\sum_{j=1}^{\left \lfloor sqrt(n) \right \rfloor} \left \lfloor \frac {n}{j} - j + 1 \right \rfloor

note, the bars represent integer floor. in code it would look like:

int answer = 0;
for (j = 1; j <= ((int)sqrt(n)); j++)
   answer += (n/j - j + 1);

.

[VernonDozier]

and you don't need a "Big Number Library". you dont even need a long int . 10,000 is easily represented by a regular integer

the way to approach this problem is by summation:

\sum_{j=1}^{\left \lfloor sqrt(n) \right \rfloor} \frac {n}{j} - j + 1

note, the bars around the sqrt represent integer floor. in code it would look like:

for (j = 1; j <= ((int)sqrt(n)); j++)
   answer += (n/j - j + 1);

.

Is there a tutorial around for how to post math terms? I see the TEX tag and the brackets, etc., and I can replicate it, but it would be nice to be able to do my own.

jephthah's formula is correct. Say n is 40. Every rectangle has a width and a length (the width being less than or equal to the length). Any rectangle having an area of 40 or less will have a width of 1, 2, 3, 4, 5, or 6, which is the floor of the square root of 40. Hence the for loop where j (the width) goes from 1 to 6:

for (j = 1; j <= ((int)sqrt(n)); j++)
   answer += (n/j - j + 1);

Take the 5th term, where the width is 5. Here are the rectangles where the area is 40 or less and one side is 5:

* ** *** **** ***** ****** ******* ********
* ** *** **** ***** ****** ******* ********
* ** *** **** ***** ****** ******* ********
* ** *** **** ***** ****** ******* ********
* ** *** **** ***** ****** ******* ********

There are 8 of them. Note the ones in red. They have a side of length 5, but 5 is the LENGTH here, not the width, so they've already been accounted for in earlier trips through the for-loop. They need to be subtracted. Thus 4 of them, or (5 -1) of them, need to be subtracted. So you have 8 - (5 - 1) = 4 left.

for (j = 1; j <= ((int)sqrt(n)); j++)
   answer += (n/j - j + 1);

Plug in 40 for n and 5 for j and get:

40 / 5 - 5 + 1 = 8 - 5 + 1 = 4

[EDIT]
My bad... Typo in the earlier math formulas. Fixed now.
[/EDIT]

[jephthah]

Is there a tutorial around for how to post math terms?

it's just LaTeX markup tags. any reference will describe the basics

http://en.wikipedia.org/wiki/Math_markup

[VernonDozier]

it's just LaTeX markup tags. any reference will describe the basics

http://en.wikipedia.org/wiki/Math_markup

Good to know. I'll check it out. Thanks. I've never used them before. They look handy.

[siddhant3s]

VernonDozier, here is a sweet link : http://www.codecogs.com/components/equationeditor/equationeditor.php

@jephthah
I got the exact formula. But I thought if I could somehow get a closed term for that summation.
This formula will surely be O(sqrt(N)).
But hey, I think that there cannot be a closed form of this. (If it was, it must have been so obvious)

[jephthah]

^ i like that link.

i don't think there's an equation without using summation. i tried to think about it for a minute, but gave up. I'm not really a math guy. :D

[VernonDozier]

^ i like that link.

i don't think there's an equation without using summation. i tried to think about it for a minute, but gave up. I'm not really a math guy. :D

I think you could give a semi-decent estimate without any summation, but the exact number? I sincerely doubt it. You have an integer division/floor component in there. That's not going to simplify well to remove the summation. I think there are some other ways of getting the exact answer, but they too are going to involve terms that don't simplify in such a way that summation drops out. I think jephthah's formula is about as simplified as this problem is going to get if you want an exact answer rather than an estimate or a range (i.e. upper and lower boundary).

[crash1989]

Hey guys I solved with using one of My friend's idea. .
find all divisors until the square root of a number .. this will give you the number of rectangles that an be formed .. this had a bit of math involved .. Math + Dumb = ME

#include<iostream>
#include<math.h>
using namespace std;
int func(int a)
{
int i,j,k,count=2,tot=1;
if(a==1)
return tot;
for(j=2;j<=a;j++)
{
count=1;
k=sqrt(j);
for(i=2;i<=k;i++)
{
if(j%i==0) 
count++;
} 
tot=tot+count;
}
return tot; 
}
int main()
{
int num;
cin>>num;
cout<<func(num)<<endl;
return 0;
}