Hello everyone, could you give me any idea about this problem? Thanks a lot.
We have 2 arrays x[ ], y[ ] size n and an integer m. We can do 2 operations:
1- Multiply all x[ ] by a (a <= m). (x[i] = x[i] * a, i = 1-> n, 2 <= a <= m)
2- Decrease arbitrary x[i] by 1. (x[i] = x[i] — 1, only one value i per operation)
Find the minimum number of operations to transform x[ ] to y[ ].
Constrain: n <= 5000, m <= 1000. 0 <= x[ ], y[ ] <= 1000.
Example:
Input:
n = 2, m = 5.
x[ ] = (3, 5)
y[ ] = (8, 15)
Output:
2
Note:
(3, 5) -> (9, 15) (1st operation, a = 3) -> (8, 15) (2nd operation, i = 1).
Sorry for my bad English :(
Your English seems pretty clear to me.
Let's consider a few things first.
Say we have x[i] >= y[i] for all i. Do we ever want to make a type 1 move at this point? If we do we make at least one more move, but we can never decrease the number of type 2 moves we make. Therefore once we have x[i] >= y[i] for all i, we only make type 2 moves.
Say we have x[0] = 1, x[1] = 1, y[0] = 4, y[1] = 1, and m = 2. Because we have one transition 1->4 we know that we must make at least two type 1 moves. What's the best way to make 1->1 with two type 1 moves? we can either go 1,1,2,2,2 or 1,2,1,2. Clearly the second is better. Generalizing this, whenever we have some sequence of type 1 moves we want to make we can calculate how many type 2 moves to make for each index at each step based on the multiple we have left to apply; we want to make our (x[i] * remaining multiple) >= y[i] and minimize it. We can calculate this directly with integer division. Number to remove = ((x[i] * remaining multiple) — y[i]) / remaining multiple. Therefore for a type 1 move sequence we can calculate the number of type 2 moves we need for each spot in time proportional to the sequence length.
How many type 1 move sequences must we consider? Since each type 1 move must at least double all our x[i] and the maximum transition we can have between x[i] and y[i] is 1->1000, we know that the maximum length of a move sequence is log(1000) = 10. This gives an awful upper bound of 1000^10 sequences. Can we improve it? There may be a more involved mathematical explanation, but I'm not seeing it at the moment, so I wrote some quick code:
This gives a result of 48362, which might just be small enough.
To summarize my proposed solution:
This should take significantly less than 50k * 5k * log(1000) = 2.5b operations. With some shortcuts and optimizations I'm confident that this can pass.
Thank you for your wonderful approach.
I am not clearly understand your idea, could you check it for me?
Pseudo code : https://pastebin.ubuntu.com/p/b4bqtXS5mK/
C++ code: https://pastebin.ubuntu.com/p/Mrqzsbk3yR/
Btw: How do you highlight your C++ code in spoiler?
To post code as I did, use spoiler tags. They look like <spoiler summary="name"> ... code ... <\spoiler>. You should also wrap it in tilde blocks to allow hashtags. Five tildes on their own line at the start and end of the code block, inside the spoiler tags.
Your understanding of 1 and 2 seem correct. There's two small issues with your code in part 3.
First is that we don't have a guarantee that we exactly multiply to 1000 or m or any number; we only know that we exceed it first by our last multiplier. That means that the line
is unneeded.
Second is that I did not guarantee that we want our A[] sequences in sorted order. It may be that the sequences 2,2,3 and 2,3,2 give different results. Therefore we should generate them both. That means that in your for loop
should be
instead.
Perhaps code will be simpler.
Well, I just realize my mistake in counting all case, I just fixed the variable Count, but I forget to fix the array :(
Now, I understand your idea, it is very amazing and magic. Thank you for every thing.
Happy to help :)