Обсуждение @ 1209. 1, 10, 100, 1000... @ Timus Online Judge

ElPsyCongroo Optimal solution [14] // Задача 1209. 1, 10, 100, 1000... 27 май 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.

thugwaffle Re: Optimal solution [3] // Задача 1209. 1, 10, 100, 1000... 11 май 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

MarX Re: Optimal solution [2] // Задача 1209. 1, 10, 100, 1000... 24 июн 2015 11:59

I tried hard with python but all I got was TLE, when I turn into c++ I got AC.

sergovoy Re: Optimal solution [1] // Задача 1209. 1, 10, 100, 1000... 3 авг 2018 17:27

У меня на эту задачу есть Accepted решение на Питоне, 499 мс

Rap1rka Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 9 мар 2024 14:26

скинь

Googologist Weird transformation // Задача 1209. 1, 10, 100, 1000... 3 авг 2015 16:45

How ( -b +- sqrt( b^2 - 4ac ) )/2a transforms into -1 +- sqrt( 8p-7 ) / 2 ?

dikcen Re: Optimal solution [1] // Задача 1209. 1, 10, 100, 1000... 19 сен 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!

dikcen Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 20 сен 2015 06:06

sorry， int(sqrt(2*x-2)) == int(sqrt(n*(n-1))) == int(n-1) if 'n' exists

the ant Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 8 июн 2016 11:57

How can i upgrade my ints to double ? Sorry for my ignorance.I'm a newbie...

Sharuar jahan Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 18 апр 2017 22:03

thanks

Kanon11 Re: Optimal solution [1] // Задача 1209. 1, 10, 100, 1000... 29 окт 2017 02:35

vi apnar analysis deikha chudna hoia gelam, airokom chinta kamne ashe mathai

shammya Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 20 июл 2018 22:24

Edited by author 20.07.2018 22:26

Edited by author 20.07.2018 22:26
nice

Edited by author 20.07.2018 22:26

Mewtwo Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 13 июл 2018 11:09

My initial approach was slightly different, but at the end, it gave the same result.

Here's the sequence ->
1 10 100 1000 10000 100000 ...

In that sequence, 1s are located at position ->
1, 2 ,4, 7, 11 , 16, 22 ...

Look at the 11th position in the sequence. There are total (1+2+3) zeros and (1 + 1 + 1 +1) ones before the 11th 1. So the position no 11 can be written as the sum:
(1+2+3) + 4 x 1 + 1.

Take another position as example, say 16. Before the 16th position, there are total (1+2+3+4) zeros, and (1+1+1+1+1) ones. And so 16 can be written as,
(1+ 2+3+4) + 5 x 1 + 1.

Now if you generalize this observation and formulate it, you'll get :
n(n+1)/2 + (n+1) x 1 + 1 = (position no containing 1)

After simplification, the equation stands:
n^2 + 3n + (4 - 2 x Position No) = 0

So for any INTEGER value of n, you'll get a Position No for 1 .

Now think the opposite of this . If the Position No contains 1, then n will must have an Integer value. Otherwise, the Position No will contains 0.
Solving that equation, you'll get:

n = ( -3 +- sqrt( 9 - 4 x 1 x (4 - 2 x Position No)) ) / 2

For n to be an Integer, the determinant (9 - 4x(4 - 2 x Position No)) or (8 x Position No - 7) must be a square number.

Asad5059 Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 7 окт 2020 19:27

Thanks a ton <3

Nouaili Re: Optimal solution // Задача 1209. 1, 10, 100, 1000... 10 май 2021 22:09

This an O(log n), because the sqrt function is O(log n)

Обсуждение задачи 1209. 1, 10, 100, 1000...