CO92SUBW - EDITORIAL

editorial
, , , ,
1

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes ## Problem Link
Practice

Contest

Difficulty

Easy

PREREQUISITES:

Implementation

Problem

There are some stations on the X-axis. The distance between the i-th and i+1-th station is i+1. It takes one second to move one unit of distance, also it takes one second to move from one station to the next. We want to go from point 0 to point X in the minimum time.

Explanation

Let di denote the position of the i-th station. The distance between station i and i-1 is equal to i. Therefore di = di-1 + i.

If we apply the recurrence recursively we get that di is equal to the sum of integers from 1 to i. In closed form: di = (i*(i+1))/2.

Numbers of the sequence 1 3 6 10 15 are called triangular numbers.

Note that triangular numbers increases quadratically. There are not many of them below 109, actually there are only 44720.

Chef wants to go to position X. So he can walk to station 1, then go by trains to the nearest station to X, and finally go walking the remaining distance.

Now the problem is to find the leftmost and rightmost station to the cinema, and check which one is more convenient. Is possible to binary search the answer, but since constraints are small, we can just iterate over all possible triangular numbers.

Implementation

Author’s Solution

Tester’s and Editorialist’s Solution

1 Like
2

int t = nextInt();
while(t–>0){
int n = nextInt();
int min = Integer.MAX_VALUE;
for(int i=1;i<45000;i++){
int sum = i+ Math.abs(i*(i+1)/2 -n);
min = Math.min(min,sum);
}
p.println(min);
}

3

My approach
Alternative Soln
This question can be done with O(time taken to find sqrt(x)) per test case.

Overall efficinecy O(T*time taken to find sqrt(x))
Finding sqrt() depends on algorithm implemented in systems/fn.

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

i is no of jumps to reach triangular no.

First is solved inequality i(i+i)/2<=x;

Which lead me to i<=(sqrt(8*x+1)-1)/2;
Then I found which is optimal sol i or i+1;

If i is ans then steps = i + (x-i*(i+1)/2)
And if i+1 is ans then steps = (i+1)*(i+2)/2-x+1+i;

And took minimum of these.

1 Like
4

Just FYI sqrt() is not computed in constant time. But still nice solution

5

@nilesh3105 Thanks, updated ans.

6

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,j=0,x,n,f,d1,d2,g;
cin>>t;
while(j<t)
{
cin>>x;
n=(-1+sqrt(1+(8*x)))/2;

	f=((n+1)*(n+2))/2;
	
	g=(n*(n+1))/2;
	
	d1=abs(g-x);
	
	d2=abs(f-x);
	
	if(d1>d2)
	cout<<(d2+n+1)<<"\n";
	else if(d2>=d1)
	cout<<(d1+n)<<"\n";
	j++;
}
return 0;

}strong text
please check my code even though my out puts are correct its still not accepting my solution
can you pls provide me the test case where it is failing