Jump to content

Need help with making something O(logn)

Nineshadow
Go to solution Solved by fizzlesticks,

Hate when these problems only give sample answers for small input you could just do by hand for testing.

 

Assuming my program is correct. 

You don't need to do anything with the string at all. Instead just figure out what position of the original string N would get its value from and determine whether is needs to be flipped or not. 

 

Spoiler

import math

s1 = '1221'

n = int(input('n: ')) - 1
closest_power = math.log(n+1, 4)
closest_power = int(closest_power) if int(closest_power) == closest_power else int(closest_power) + 1

flip = False
pos = n
while closest_power > 1:
    length = int(math.pow(4, closest_power))
    lengthm1 = length // 4

    if lengthm1 <= pos < length - lengthm1:
        flip = not flip

    pos = pos % lengthm1
    closest_power -= 1


ans = s1[pos]
if flip:
    ans = '1' if ans == '2' else '2'

print(ans)

 

 

 

P.S. screw 1 based indexing.

I was browsing a programming book and I found this pretty interesting problem :

 

Let the function f be defined on {1,2} with values in {1,2}, such that f(1) = 2 and f(2) = 1.

The function can be extended to any sequence containing values of 1 and 2. For example , f(1211221) = 2122112 .

Let's consider the infinite series/string s, made out of digits of 1 and 2, which can be generated incrementally through the following concatenation rule :

s1 = 1221

s2 = 1221211221121221

s3 = 1221211221121221211212211221211221121221122121121221211221121221

...

Generally : sk+1 = sk + f(sk) + f(sk) + sk , where the plus operation represents concatenation.

 

Given a natural number n < 10000000 , write a program that outputs the n-th digit of the series/string s , with O(log2n).

 

For example:

  • for n = 11 the program will output 1. ( the first 11 digits of the series are : 12212112211 )
  • for n = 20 the program will output 2. ( the first 20 digits of the series are : 12212112211212212112 )

_______________________________________________________________________________________________

 

I've tried a few things myself , and most of them worked , but not in O(logn). I've been trying to find a way to use some divide et impera but without any success. Need suggestions/ideas.

 

Right now I have something like:

//vector which stores our series
vector<int> s = {1 , 2 , 2 , 1};

int n;
cin >> n;

// k represents the length of the series generated up to the current point.
int k = 4;

while(k < n)
{
vector<int> conjugate = f() // f returns the result of the function defined in the problem, executed on the s vector
vector<int> origial = s;
// push_back_vector() is a function which pushes back the values of another vector into the s vector
push_back_vector(conjugate);
push_back_vector(conjugate);
push_back_vector(original);
k*=4;            
}

cout << s[n];

 

i5 4670k @ 4.2GHz (Coolermaster Hyper 212 Evo); ASrock Z87 EXTREME4; 8GB Kingston HyperX Beast DDR3 RAM @ 2133MHz; Asus DirectCU GTX 560; Super Flower Golden King 550 Platinum PSU;1TB Seagate Barracuda;Corsair 200r case. 

Link to comment
Share on other sites

Link to post
Share on other sites

1 minute ago, prolemur said:

I could make a really efficient program to solve this problem 50% of the time :D

50% of the time?

I wonder why...

i5 4670k @ 4.2GHz (Coolermaster Hyper 212 Evo); ASrock Z87 EXTREME4; 8GB Kingston HyperX Beast DDR3 RAM @ 2133MHz; Asus DirectCU GTX 560; Super Flower Golden King 550 Platinum PSU;1TB Seagate Barracuda;Corsair 200r case. 

Link to comment
Share on other sites

Link to post
Share on other sites

39 minutes ago, Nineshadow said:

50% of the time?

I wonder why...

I think he means that because the result can only be a 1 or a 2 then you can just choose one to output every time. Basically, return 1;

 

edit: After reading the comment over again, I'm assuming you already understood what he meant so now I feel stupid for posting. Oh well, maybe it'll help someone else who doesn't get it... 

Link to comment
Share on other sites

Link to post
Share on other sites

One way to make it faster might be to try to (dis)prove the last number is a 1 or 2 instead of trying to figure it out? Just a thought since it looks like you're finding it.

Link to comment
Share on other sites

Link to post
Share on other sites

Hate when these problems only give sample answers for small input you could just do by hand for testing.

 

Assuming my program is correct. 

You don't need to do anything with the string at all. Instead just figure out what position of the original string N would get its value from and determine whether is needs to be flipped or not. 

 

Spoiler

import math

s1 = '1221'

n = int(input('n: ')) - 1
closest_power = math.log(n+1, 4)
closest_power = int(closest_power) if int(closest_power) == closest_power else int(closest_power) + 1

flip = False
pos = n
while closest_power > 1:
    length = int(math.pow(4, closest_power))
    lengthm1 = length // 4

    if lengthm1 <= pos < length - lengthm1:
        flip = not flip

    pos = pos % lengthm1
    closest_power -= 1


ans = s1[pos]
if flip:
    ans = '1' if ans == '2' else '2'

print(ans)

 

 

 

P.S. screw 1 based indexing.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

47 minutes ago, fizzlesticks said:

Hate when these problems only give sample answers for small input you could just do by hand for testing.

 

Assuming my program is correct. 

You don't need to do anything with the string at all. Instead just figure out what position of the original string N would get its value from and determine whether is needs to be flipped or not. 

 

Hidden Content

 

P.S. screw 1 based indexing.

That's exactly what I was thinking to achieve , but I didn't really manage to implement it properly.

Also , if you need a few more test cases :

  • n = 1024 => 1
  • n = 1.000.000 => 1
  • n = 123.456 => 2

 

i5 4670k @ 4.2GHz (Coolermaster Hyper 212 Evo); ASrock Z87 EXTREME4; 8GB Kingston HyperX Beast DDR3 RAM @ 2133MHz; Asus DirectCU GTX 560; Super Flower Golden King 550 Platinum PSU;1TB Seagate Barracuda;Corsair 200r case. 

Link to comment
Share on other sites

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×