Yesterday Div3 round(Make a Power of Two)

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Make a Power of Two In this problem, I wrote the code and it gives me TLE on test case-3 without any reason because my code runs in worst-case (269*11) = 2959 and the time limit for this problem is "one second" but still it gives me TLE why? I don't have any Idea anyone help me

My code

// This function is working in O(max(s1.length(), s2.length())
int recur(string s1, string s2, int x, int y)
{
    if (x >= s1.length() || y >= s2.length())
        return 0;
    int t1 = 0, t2 = 0;

    if (s1[x] == s2[y])
        t1 = 1 + recur(s1, s2, x + 1, y + 1);
    else
        t2 = recur(s1, s2, x, y + 1);

    return max(t1, t2);
}

// storing the power to 2 from 0-40
vector<string> make_power_of_2()
{
    vector<string> vs;
    vs.pb("1");
    int ans = 1;
    for (int i = 1; i <= 40; i++)
    {
        ans = ans * 2;
        vs.pb(to_string(ans));
    }
    return vs;
}

void solve()
{
    vector<string> vs = make_power_of_2();
    int n;
    cin >> n;

    string str = to_string(n);
    int ans = INT_MAX;
    int flag = 0;
    for (int i = 0; i < vs.size(); i++)
    {
        int z = recur(vs[i], str, 0, 0);
        ans = min(ans, (vs[i].length() + str.length() - 2 * z));
    }
    cout << min(ans, (int)(str.length() + 1)) << endl;
}

Comments (7)

Show archived | Write comment?

waltz47

3 years ago, # |

← Rev. 2 →

make_power_of_2() should be preprocessed. You're calling it per testcase without clearing it (looking at Your submission). 40 push_backs per case making its size 40 * 10 ^ 4.

Call it once, or clear the vs vector after each testcase.

→ Reply

gnudgnaoh

use 2**62 or larger

jeal0uspengu1n

3 years ago, # ^ |

No reason for using it as it is cleary mentioned in the question that the value of n<=10⁹ , so even if we add a digit to the right of n it cannot exceed 2^36

theviz

u would get a wa generating all powers till 36. you have to generate atleast till 56 because 2^56 > 1e18

And why is it , that we've to generate till 1e18 , the upper limit in the question is 1e9 and the max number of moves to get a power of 2 is (number of digits+1) , that gives us 1e10 in worst scenario

← Rev. 3 →

From the editorial of this round:

Suppose n consists of more than 9 digits. Then n=10^9 because n≤10^9 according to the input format. The answer for the number doesn't exceed 9 — we can get this answer if we erase all 0 from the number to turn it into 1. Suppose there's a number x such that ans(n,x)≤8. This number can consist of no more than 18 digits (10 digits of n plus 8 digits), hence x<10^18.

Therefore, it's enough to consider all powers of two that are less than 10^18

Gotcha ;)

Ankit_12's blog