ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1209. 1, 10, 100, 1000...

Optimal solution
Posted by ElPsyCongroo 27 May 2014 22:35
Ok, just posting this to help others understand few things here:

The sequence is 1101001000100000... If you see the locations of the digit 1, you can observe that it is at location 1,2,4,7...=> ( 1 + 0 ),( 1 + 1 ),( 1 + ( 1 + 2 )),( 1+(1+2+3 )..So, it is 1+sum_of_n_digits.

What we have now is below:

1 + n*( n+1 )/2 [ note that n*(n+1)/2 is the sum of first n natural numbers ].

Now, this value should be equal to the input value, say P.

1 + n*(n+1)/2 = p [ I/p P=7 => n should be 3, back track ].

2 + n^2 + n = 2p

n^2 + n = 2(p-1)

n^2 + n - 2 (p-1) = 0;

This is a quadratic equation in 'n'. The roots of a quadratic equation are

( -b +- sqrt( b^2 - 4ac ) )/2a

-1 +- sqrt( 8p-7 ) / 2;

But, for our example, if you do some analysis, if the value of 8p-7 is a perfect square, then the value at that position 'p' would be 1. Else the value would be 0.

So, check for 8p-7 to be a perfect square. This is the optimal solution. Got mine accepted.

BTW, if you face any difficulty at test 3, it means you have to upgrade your ints to doubles. Because 8p-7 can falll over the size of int [atleast in Java].

Thanks,
ElPsyCongroo.
Re: Optimal solution
Posted by thugwaffle 11 May 2015 23:41
Thanks for the hint. I tried a very similar algorithm but was still getting WA on Test 3 in Java. I finally switched over to Python, and got AC
Re: Optimal solution
Posted by MarX 24 Jun 2015 11:59
I tried hard with python but all I got was TLE, when I turn into c++ I got AC.
Weird transformation
Posted by Googologist 3 Aug 2015 16:45
How ( -b +- sqrt( b^2 - 4ac ) )/2a transforms into -1 +- sqrt( 8p-7 ) / 2 ?
Re: Optimal solution
Posted by dikcen 19 Sep 2015 18:43
I do it like this:

the n-th '1'should be here: n(n-1)/2+1.So, we judge whether the input number(x) == (n(n-1)/2+1).

it could be transformed to 2*x-2 == n(n-1), and int(sqrt(2*x-2)) must be the number 'n' if 'n' exists!
Re: Optimal solution
Posted by dikcen 20 Sep 2015 06:06
sorry， int(sqrt(2*x-2)) == int(sqrt(n*(n-1))) == int(n-1) if 'n' exists
Re: Optimal solution
Posted by the ant 8 Jun 2016 11:57
How can i upgrade my ints to double ? Sorry for my ignorance.I'm a newbie...
Re: Optimal solution
Posted by Sharuar jahan 18 Apr 2017 22:03
thanks
Re: Optimal solution
Posted by Kanon11 29 Oct 2017 02:35
vi apnar analysis deikha chudna hoia gelam, airokom chinta kamne ashe mathai