Leviosarz's blog

By Leviosarz, history, 5 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

»
5 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Your English seems pretty clear to me.

Let's consider a few things first.

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

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

  3. 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:

code

This gives a result of 48362, which might just be small enough.

To summarize my proposed solution:

  • Generate the ~50k different move type 1 sequence that might interest us.
  • Calculate the score for each sequence in length(sequence) * n time.
  • Our result is the minimum sequence score.

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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    Thank you for your wonderful approach.

    I am not clearly understand your idea, could you check it for me?

    1. After an operation 1, we will try to reduce value x[i], so the number of operation 2 in the future will be optimized. In current step, the number of operation 2 is "((x[i] * remaining multiple) — y[i]) / remaining multiple".
    2. We will try all sequence of operation 1 (called A[ ]), for each case, we calculate the result and optimize the answer. You can prove that the number of sequence will less than 50 000.
    3. We will generate all possible A[ ]. The product of all elements must be equal or smaller than 1 000. We can have them by this code.
      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?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      if (remPro % nxtVal != 0) continue;
      

      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

      int nxtVal = val;
      

      should be

      int nxtVal = 2;
      

      instead.

      Perhaps code will be simpler.

      code
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.