TRICOIN - Editorial

editorial
, , , , , ,
1

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_{\substack{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.

1 Like
2

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

2 Likes
3

Complexity is O(1).

4

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

5

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

6

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

2 Likes
7

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

1 Like
8

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);

9

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

10

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.

11

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

12

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

2 Likes
13

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:

1 Like
14

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

1 Like
15

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;

}

16

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

17

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

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