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

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

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 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

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