GRDPRTY - Editorial

encoding
grdprty
horsbug98
maths

#1

PROBLEM LINK:
Practice
Contest

Author: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

DIFFICULTY:

EASY

PREREQUISITES:

Math Triangular Number

PROBLEM:

The problem asks to find out the no. of elements in one side of the triangle formed from the total no. of unit elements. Simultaneously, the total user input number needs to check if it is a triangle number or not.

EXPLANATION:

The square root of n, one can define the (positive) triangular root of n as the number x such that Tx = n.
x can be calculated by this: x = (sqrt(8*n+1)-1)/2
which follows immediately from the quadratic formula. So an integer n is triangular if and only if 8n + 1 is a square. Equivalently, if the positive triangular root x of n is an integer, then n is the xth triangular number.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here


#2

Since the $n$th triangular number T_n = n(n+1)/2, obviously 2\cdot T_n = n(n+1) and n^2 < 2T_n <(n+1)^2.

So given a test number x we can find m, the integer part of \sqrt{2x}, and then see if T_m = x.