TRISQ - Editorial

[the_baahubali]

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.

[bluebloodxxl]

Why did I get a WA?

Why did I get WA??

#include<bits/stdc++.h>
#include
#include<math.h>

int T, B, n, x;
using namespace std ;

int main(){

scanf("%d",&T);
while(T–)
{
scanf("%d",&B);

        if (B>3){
            if ((B%2)!=0)
                B--;
            x= (B*B)/4;
            n= ( (x) - sqrt(x) )/2;
            printf("%d",n);

        }

        else{
            n=0;
            printf("%d",n);
        }
    }

return 0;
}

[rafferz]

Another alternative way of doing it is arithmetic series:

where n = int(b/2-1) and ![alt text][2] and A1 = 1 and An = n

Example: B = 20, n =(20/2-1) = 9, 9(1+9)/2 = 45

[coder_to_hack]

Recursive function for this problem is f(x) = 1 + 2*f(x-2) - f(x-4)

[subarna_08]

F(B)=B/2+(B/2-1)+(B/2-2)+…+1
can anyone plz tell me from where the 1st B/2 term come?

[zangliu]

@subarna_08.
Correct summation is : ((B/2) - 1) + ((B/2) - 2) + … + 1 = Sum of first ((B/2) - 1) positive integers.
Hence the correct answer is: ( ((B/2) - 1)(B/2) )/2.
(Sum of first n positive integers is n(n+1)/2)

[rahulgr8888]

Can anyone tell me why the code with precompute is throwing the error NZEC, while without precompute it is working correctly in Java?

Code:

With Precompute: CodeChef: Practical coding for everyone

WithOUT precompute: CodeChef: Practical coding for everyone

[jayesh638]

Java Recursive solution:

import java.util.*;

class Solution

{

public static int derive(int n)
{
	if(n==1 ||n==2 ||n==3)
		return 0;
	return (n/2-1)+derive(n-2);
	
}
public static void main(String []args)
{
	Scanner sc=new Scanner (System.in);
	int item=sc.nextInt();
	while(item!=0)
	{
		item--;
		int n=sc.nextInt();
		int x=derive(n);
		System.out.println(x);
	}
}

}

[vishalraghavan]

“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 …

[hetp111]

correction:

TRISQ - Editorial

@subarna_08. Correct summation is : ((B/2) - 1) + ((B/2) - 2) + … + 1 = Sum of first ((B/2) - 1) positive integers. Hence the correct answer is: ( ((B/2) - 1)(B/2) )/2. (Sum of first n positive integers is n(n+1)/2)

[agarwal_mayank]

Hey!. Let the base length is B. Since the triangle is right-angled isosceles, even the perpendicular is B. The angle between base and hypotenuse is 45 degrees.(tan theta = B/B = 1). Now we need to find the position on the base beyond which a square of 2 units cannot exist. Again from tan theta, this is 2. Therefore, squares can be drawn on B-2 space. Therefore number of squares = (B-2)/2 = B/2 - 1. These squares are on the base. The part left in perpendicular is B-2, which is again a right-angled isosceles triangle. Hope this helps!

[ishaan_007]

Here is the recursive code (Python 3.6) :

def rec(b):
    if b<4:
        return 0
    else:
        return (b//2 - 1) + rec(b-2)
if __name__==‘__main__’:
    for _ in range(int(input())):
        print(rec(int(input())))

Here is the optimal code:

for _ in range(int(input())):
b = int(input())
if b<4:
    print(0)
    continue
else:
    if b%2==1:
        b-=1
    
print(((b-2)*(b))//8)

[sanchi96]

Can you please help me with this, I am getting NZEC for the code,

def recursion(n):
if(n<4):
return 0
else:
return recursion(n-2)+(n//2)-1

for t in range(int(input())):
n = int(input())
print(recursion(n))

[sanchi96]

Why am I getting NZEC for this code?

def recursion(n):
if(n<4):
return 0
else:
return recursion(n-2)+(n//2)-1

for t in range(int(input())):
n = int(input())
print(recursion(n))

[ishaan_007]

If n=10**4 (see constraints) then it will raise recursion error hence it is better to use mathematical approach than recursion one. Hope this helps. Happy coding!

[subham0312]

This solution is for a square of nxn.
Triangle base is B.

int main(){
int t, B; //no. of testcase and base of a triangle
int k, n;
cin>>t;
while (t–){
int result;
cin>>B;
k = B/n;
result = (k*(k-1))/2;
cout<<result<<endl;
}
}

[anizzz123]

please explain clearly b/2-1 came from

[anizzz123]

how total no of squares is (b-2)/2 I understood till less than b-2 length only square is possible help me …

[nagesh_reddy]

You should use recursion limit in Python, add following 2 lines top of your code :

import sys
sys.setrecursionlimit(10**7)

[nagesh_reddy]

FYI : @anizzz123