The idea comes from the most common one. I think most of participants(including me) got trapped when trying to fix k-2 ns in the array, but actually it's not the best.
Set n=(1010101010)2 as a sample, I got x=(1001010101)2 and y=(0011111111)2 after the initial process.
My solution tend to be obvious when it's found that swapping some 1s from ns to x while keep it less than n can provide us with space to manipulate the numbers been n early.
Let's try send the second 1 from highest of (1010101010)2 to x, and also the third. (Do them separately in two numbers)
Interestingly we got (1000101010)2 and (1010001010)2. We can operate them in pair, and they become (1000111111)2 and (1010011111)2 when we try to maximize them while follow the limitations.
Repeat the step and now we get an answer.
I can't prove the algorithm is completely right, so I published it and forwarded to a proof.
(I used log2 function, but it can be replace with two pointers or a stack)
Sorry that I may not reply in time, as I'm living in China and it's time to sleep :P
354224877 can you help me figure where did i go wrong here ?
My approach , if k is odd , i output k times n , if k is even then i output n k-2 times and the last 2 are seleceted like below :
for the n = 100100
i choose one number as 000111 and another as 100011 , is this approach correct?
n=30 k=4 Answer is 15 23 27 29
It is wrong. Let 'a' and 'b' be the 2 last numbers of your sequence. What you are currently doing is that 'a' gets the most significant bit on 'n', 'b' gets the second most significant bit of 'n', and then they complement each other such that their xor gives the remaining bits of 'n'.
That fails because 'a' can still incorporate some bits from the first (k-2) numbers (which are all 'n'), freeing up space for them to get extra pairs of bits that cancel each other out but increase the sum.
Counterexample: n = 62, k = 4
In binary, we have
n = 111110
Your algorithm computes
a = 100001
b = 011111
And the other 2 numbers (which I will call 'x' and 'y') are both equal to n:
x = 111110
y = 111110
Notice that you can move x's 4th most significant bit and y's 5th most significant bit to 'a', which would give you:
a = 100111
x = 111010
y = 111100
It still holds that a <= n, but now, you freed the last bit of both 'x' and 'y', allowing you to set them instead to
x = 111011
y = 111101
Now, everyone is <= n, but the sum was increased (this counterexample optimal sum is 190).
okay now i understand , i move the a power of 2 from one number to another number which can accomodate so that , i can have an extra 1 power of 2 in total here.
how do u come up with this kind of edge cases , any tips or does it just depend on solving more problems
I actually didn't solve it like that. My solution is similar to editorial's (iterating through the bits of 'n' and setting them on the numbers of the vector prioritizing the smallest numbers first). I think the way to get better is just solving more problems. I'm still not really good at these kind of problems, but I'm pretty sure I improved a lot recently because I started doing more problems.
orz