You are not logged in. Please login at www.codechef.com to post your questions!

×

TRISQ - Editorial

PROBLEM LINK:

Practice
Contest

Author: Devendra Agarwal
Tester: Anudeep Nekkanti
Editorialist: Amit Pandey

DIFFICULTY:

Cakewalk.

PREREQUISITES:

Basic geometry, recursion.

PROBLEM:

Find the maximum number of squares of size $2\times2$ that can be fitted in a right angled isosceles triangle of base $B$. All sides of the square must be parallel to both base and height of the isosceles triangle.

QUICK EXPLANATION:

As $B<=1000$, we can pre-compute the output for all the test cases, and report the answer in $O(1)$ time for each of the query.

EXPLANATION:

First consider the right angle triangle $\Delta XYZ$, where $YZ$ is the base of triangle. Suppose length of the base is $B$. If we consider the position of first square with the vertex $Y$, we will have $(B/2 - 1)$ squares in the base, and we will be left with another isosceles right angle triangle having base length $(B-2)$.

Let $f(B)$ = Number of squares which can be fitted in triangle having base length $B$.

$f(B) = (\frac{B}{2} -1) + f(B-2)$

The given time limit is sufficient even if we calculate $f(B$) using the given recursion, and use memoization. Later we can answer each query in $O(1)$ time. We can do it for even and odd numbers separately with the base case $f(1) = f(2) = f(3) = 0$.

The given recursion can be solved in following manner.

$$ f(B) = \frac{B-2}{2} + F(B-2) \\\ = \frac{B-2}{2} + \frac{B-4}{2} + F(B-4) \\\ = \frac{B-2}{2}+ \frac{B-4}{2} + \frac{B-6}{2} + F(B-6) $$

With conditions, $f(1) = f(2) = 0$

$f(B) = \frac{B}{2} + (\frac{B}{2} - 1) + (\frac{B}{2} -2) + \cdots + 1$.

$f(B)$ = Sum of first $\frac{B}{2}$ natural numbers.

Lets call $M = \frac{B}{2}$
$f(B) = \frac {M \times (M-1)}{2}$

You can notice that answer for $2N$ and $ 2N+1$ will be the same.

Solution:

Setter's solution can be found here
Tester's solution can be found here

This question is marked "community wiki".

asked 09 Feb '15, 19:55

amitpandeykgp's gravatar image

4★amitpandeykgp
2591322
accept rate: 0%

edited 11 Feb '16, 19:00

admin's gravatar image

0★admin ♦♦
15.9k347484508

"we will have (B/2−1) squares in the base, and we will be left with another isosceles right angle triangle having base length (B−2)." Where does this thing come from... please help me ....

(05 Jun '15, 17:17) vishalraghavan2★

My solution

long long int t1,t2,b;
  t2=b/2;
  t1=t2*t2;
  t1=t1-t2;
  t1=t1/2;
  cout<<t1;
link

answered 21 Feb '15, 22:40

flyinglion's gravatar image

2★flyinglion
5612
accept rate: 100%

It can be solved in a more simple way. Consider you need to fill the isosceles triangle with 1x1 squares. Now, consider a square of side B. The number of 1x1 squares you can put in is clearly BxB, and also the number of 1x1 squares you can put in an isosceles triangle will be (BxB - B)/2 ie we remove the squares on the diagonal and half the remaining squares . Now you need to scale the 1x1 to 2x2, so you simply divide B by 2, and use (BxB - B)/2. My Solution I know the proof is more intuitive rather than rigorous, would be happy to know if there is some fallacy, or some rigourous way of proving it.

link

answered 16 Feb '15, 01:01

mjnovice's gravatar image

3★mjnovice
1323513
accept rate: 0%

edited 16 Feb '15, 01:02

My approach was wrong but it got AC anyway. Observing the test cases the answer for consecutive size of the base is - 0 0 0 1 1 3 3 6 6 10 10... which is nothing but the series of sum of n integers with all the sums repeating twice, except for first three 0s. After pre-computing this for 10^4 each query can be answered in O(1). Perhaps the problem could have been presented with less and randomized test cases to prevent the use of such approach.

link

answered 16 Feb '15, 01:23

skysarthak's gravatar image

3★skysarthak
453
accept rate: 0%

It can also be solved as through the following code :-->>

int N=(B/2)-1;

print((N*(N+1))/2);

link

answered 11 Jul '15, 17:05

kislaya123's gravatar image

2★kislaya123
111
accept rate: 0%

My approach:

A=(B[i]/2)*(B[i]/2);

A-=(B[i]/2);

A-=((((B[i]/2)*(B[i]/2))/2)-(B[i]/4));

cout << A << endl;

Maybe it can be simplified further.

link

answered 16 Oct '15, 18:40

vaibhav29498's gravatar image

4★vaibhav29498
1
accept rate: 0%

how u have generated a general formula for this problem??? plz help....

link

answered 17 Oct '15, 05:55

vk34's gravatar image

1★vk34
1
accept rate: 0%

Firstly, divide 'b' or 'n' by 2 so we can deal with 1x1 squares.

At the base, n-1 squares can be fit and it decreases by 1 as we go upwards. Hence the total number of squares is the sum=(n-1)+(n-2)+...+2+1.

Summation of +ve: n is added n-1 times. Therefore, sum of n's is n(n-1).

Summation of -ve: Summation of series of natural numbers is '(N)(N+1)/2'. Here N=n-1 so summation is n(n-1)/2.

Subtracting -ve from +ve, we get: n(n-1)/2 or b(b-1)/2

link

answered 19 Jun '16, 20:24

cyberneo's gravatar image

2★cyberneo
1
accept rate: 0%

Nothing Understood , Very Bad Explanation :(

link

answered 17 May, 22:26

joy59's gravatar image

0★joy59
1
accept rate: 0%

Isn't sum of the first M natural numbers M*(M+1)/2 ?

link

answered 23 Jun, 19:14

mathprogrammer's gravatar image

2★mathprogrammer
233
accept rate: 0%

For people willing to know where this statement came from:

We will have (B/2−1) squares in the base, and we will be left with another isosceles right angle triangle having base length (B−2).

You can deduce this simply by using simple trigonometry. I was also curious to find the reason behind this and then got to this approach. Please correct me if I'm wrong or if there's a better approach. If you can, try visualizing this on a notebook.

Consider in triangle XYZ, YZ is the base with Z as the right-angled vertex. Thus, YX is the hypotenuse. Let the length of base YZ = B. SInce, it's an isosceles triangle length of YX is also B. Thus, the angle XYZ is 45 degrees (tan(XYZ) = B/B = 1). If we start filling squares of side 2 units from vertex Z, we can only fill them until the distance between base and the hypotenuse becomes less than 2. Since, the corresponding angle is 45 degrees, the distance from Y to this point will also be 2. Hence, we will not be able to place 1 square of side 2 here. The total number of squares that could be filled thus B/2 - 1. B/2 since there are of side 2 units. Then we are left with another isosceles triangle above these filled squares with base B-2 that is simply the sum of the length of upper sides of all squares (2*(B/2 - 1) = B - 2).

Hope I was clear with the explanation.

link
This answer is marked "community wiki".

answered 19 Aug, 17:32

the_baahubali's gravatar image

3★the_baahubali
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,049
×365
×252
×109
×2

question asked: 09 Feb '15, 19:55

question was seen: 8,660 times

last updated: 19 Aug, 17:32