Good Numbers Codeforces Problem using Meet in the middle

Problem - https://codeforces.com/contest/1249/problem/C2

Can anyone tell how to solve this problem using meet in the middle(As they have mentioned in their tags).
Thank you :slight_smile:

I don’t know why tag is meet in the middle. I solved it with simple logic and my approach matches with editorial as well.
Let me know if you need any help in intended solution.

1 Like

Similar to C1, create two vectors one containing all bitmasks powers of 3 from 0 to say 20 and the other one from 21 to 40. Iterate on first and binary search on second

3 Likes

Yes, the greedy approach mentioned in article is intended one.

1 Like

Yes, I solved C1 using that approach.
I didn’t knew about meet in the middle before but after that I googled on it. I will try implementing it and get to you if I have any problem.

I tried doing that here.
But it got TLE .
https://codeforces.com/contest/1249/submission/63615244

:confused:

I tried changing sizes to
sz1 = 15
sz2 = 24
but it got TLE on tc 7. i don’t think meet in the middle is intended solution.
https://codeforces.com/contest/1249/submission/63615338

Okay I agree that iterating through the first vector would TLE, some observation so that you need to check only certain cases.
You can see this submission: https://codeforces.com/contest/1249/submission/63178411

1 Like

Can you explain the solution for C2. I solved C1 by precomputation and than outputting the lower bound in that precomputed vector. It worked for C1 but can you explain C2?

That’s great, but can you explain your observations for reducing time complexity.
As we cannot understand much from code.

Again thank you :slight_smile:

C2 is greedy. Convert given number into base 3 and then if there is any 2 in it’s representation then replace all digits upto 2 by 0 ( including 2) and then find a bit whose value is 0 and make it 1 and keep replacing it by 0 till then.
Examples :
101010010 => 101010010
100202012 => 101000000
101112111 => 110000000
111120000 =>1000000000
102111001 => 110000000

2 Likes