TRICOIN - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunny Aggarwal
Tester: Sergey Kulik
Editorialist: Sunny Aggarwal

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementaion, Mathematics, Brute Force.

PROBLEM STATEMENT:

You are given a number N that represents the number of coins you have and you have to print the maximum possible height H of triangle which can be made from these coins in such a way that i^{th} row of the triangle contains i coins.

QUICK EXPLANATION:

Maximum possible height of the triangle is the maximum possible value of H such that \frac{H\times(H+1)}{2} \le N.

EXPLANATION:

It should be noted that i^{th} row of triangle contains i coins. Therefore, a traingle with H height will contain 1 coin in 1^{st} row, 2 coins in 2^{nd} row, … , H coins in H^{th} row and total number of coins required to build a triangle of height H will be equal to

\sum_{{1 \le i \le H}}{i} \quad = \quad \frac{H \times (H+1)}{2}

As we are asked to find the maximum possible height of the triangle, we have to find the maximum value of H such that \frac{H \times (H+1)}{2} \le N. Note that the value of N ~= 10^9 in worst case and therefore the maximum possible value of H will be order of \sqrt{N}.

We can use following simple procedure to solve this problem.

int sum(int h) {
	return (h * (h+1) / 2);
}

void solve() {
	int n;
	cin >> n;
	int h = 1;
	while(sum(h) <= n) {
		h ++;
	}
	cout << h - 1 << "\n";
}

TIME COMPLEXITY:

O(\sqrt{N})

BONUS:

Try solving same problem with 1 \le N \le 10^{15}.

AUTHOR’S AND TESTER’S SOLUTION:

Author’s solution can be found here.
Tester’s solution can be found here.

3 Likes

Solution for 1 <= N <= {10}^{15} . One of the shortest code ever written. :stuck_out_tongue:

2 Likes

There is another answer possible for O(1).
Just use quadratic Formula.

x = ( -b+sqrt(b - 4ac ) ) * 2

where b = 1 , a = 1 & c = n (input)

equation to be solved : x2 + x - 2n

3 Likes

binary search will be best here
https://www.codechef.com/viewsolution/9987437

1 Like

I even tried avoid looping by the following code. But, subtask 2 got failed. I don’t know why.

int noofgoldcoins = Integer.parseInt(br.readLine());
int rootA = (int) ((-1 + Math.sqrt(1+8*noofgoldcoins))/2);
System.out.println(rootA);

simple solution by using Babylonian square root algorithm :https://www.codechef.com/viewsolution/9983926

2 Likes

The O(1) Solution Can Be Explained Like This :
You Can See That For Height = 1 , Number of Coins Needed =1
For Height=2,total Coins Needed=3;
for height=3,total coins needed=6
for height 4,total coins needed =10
for height 5,total coins needed=15
if u observe the pattern : (1,3,6,10,15…)
its = (1,1+2,1+2+3,1+2+3+4,1+2+3+4+5,…)
whhich has a simple formula : summation of first n natural numbers = n*(n+1)/2
therefore , height(height+1)/2 <= no of gold coins;
solving this , we get the ans as : (-1+sqrt(1+8*goldcoins))/2

Hope It Helps. :slight_smile:

6 Likes

whats wrong in this:

#include
#include <math.h>
using namespace std;

int main() {
// your code goes here
int ctr=0,sum=0,i=0,j=1,t,N;
cin>>t;
if(t>100) goto ends;
for(i=0;i<t;i++)
{
ctr=0;
sum=0;
cin>>N;
for(j=1;j<=N;j++)
{
sum=sum+j;
if(sum<=N) ctr++;

    }
    cout<<ctr<<"\n";
}
ends:
return 0;

}

No need for 8N stuff. We can divide by 2 earlier. The answer would be floor( sqrt(2N+0.25) - 0.5)

A Two Liner in Python with Time Complexity of O(1)

https://www.codechef.com/viewsolution/22575685

1 Like

Complexity is O(1).

for n>=10^9, just take input in long long.

1 Like

@likecs , what’s the logic behind the line
printf("%d\n",(((int)sqrt(1+8.0*n))-1)/2)… ??

Just solve the above quadratic inequality. (H*(H+1)/2) <= N

Reason is 8*noofgoldcoins will overflow for integer. Hence give a negative number or some random value inside square root. That is why, I used 8.0 to convert value to double whose range is more than int and it passes both subtask.

1 Like

@likecs Complexity is NOT O(1) (it is O(log n)).

@alexvaleanu complexity is O(1) for the given program(above link) not O(log n).

1 Like

How did you get (-1+sqrt(1+8*goldcoins))/2 this value?
I mean what was the approach you followed?
I am facing difficulties in finding patterns.

By using the formula for roots
If the equation is ax^2 + bx + c = 0
it implies
x = ( -b + sqrt( b^2 - 4ac ) ) / 2 or ( -b - sqrt( b^2 - 4ac ) ) / 2
And since the height can’t be negative we ditch the second one.

first of all you have to change the data type of the variables.
when you change your data type to the following your code will get partially correct.

long int ctr=0,j,N;
long long int sum=0;

but you will not get the complete AC from this code , bcz for higher values of N it will get TLE as we are using for loop which is increasing the time complexity.