shekabhi1208's blog

By shekabhi1208, history, 3 years ago, In English

Hello codeforces, I want to know whether there is any solution to this problem that is better than the naive O(N ^ 2) or not?

Problem:

You are given two arrays A and B. In each step, you can set A[i] = A[i] — B[i] if A[i] >= B[i]. Determine the minimum number of steps that are required to make all values of array A equal.

Print the minimum number of steps that are required to make all values of array A equal. If it is not possible, then print -1.

Constraints:

1 <= N, A[i], B[i] <= 5000

Sample Input

2

5 6

4 3

Sample Output

-1

Sample Input:

5

5 7 10 5 15

2 2 1 3 5

Sample Output:

8

Link to the Problem

  • Vote: I like it
  • +9
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it -19 Vote: I do not like it

Forgive me if I'm wrong, but I think you can save values. This is the difference (if a[i] >= b[i] store it in an array), and also store a[i] in an array. Then sort the array, and find if there is so number that is repeated N times by your preference (binary search or pointer(s)). Alternatively you can iterate over a map, and count the number of times the element occurs.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can apply the operation multiple times to the same index.

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Can be solved in $$$O(n*lg(n))$$$. Let the final value be $$$x$$$ then $$$x$$$ should satisfy $$$x \equiv a[i] \;(\bmod\; b[i]) \forall i$$$. Solution to all of the equations will be of the form $$$x \equiv r \;(\bmod\; lcm(b[1],b[2]..b[n]))$$$. $$$r$$$ can be calculated by using CRT. So no we will find $$$x$$$ s.t $$$x<=a[i] \forall i$$$ giving us the answer. Now remember lcm can get really big, so while processing equations one by one(blog) as soon as lcm gets > 5000, we know there will be only one $$$x$$$ in between [1..5000] so now you just need to check for that potential answer in O(n).

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Another $$$n*log(n)$$$ solution:
Let $$$x$$$ be the number we make all $$$a$$$ for the best solution. Let's find $$$x$$$ first, then we can calculate the number of steps to make all $$$a$$$ to $$$x$$$ in $$$O(n)$$$.

For each $$$i,j$$$ such that $$$b_{i} = b_{j}$$$;
     If $$$a_{i} \not\equiv a_{j} (mod$$$ $$$b_{i})$$$ then the answer is $$$-1$$$ since we can never make equal $$$a_{i}$$$ and $$$a_{j}$$$.
     Otherwise, (let's assume $$$a_{i} < a_{j}$$$) Whatever the $$$x$$$ is, first we must transform $$$a_{j}$$$ to $$$a_{i}$$$ before we transform it to $$$x$$$. Therefore, we can ignore $$$a_{j}$$$ while finding $$$x$$$.

So, for each unique $$$b_{i}$$$ value, only the numbers { $$$ a_{i}, a_{i}-b_{i}, a_{i}-2*b_{i} \dots $$$ } are reachable ($$$\frac{a_{i}} {b_{i}}$$$ numbers).

$$$x$$$ is the maximum number such that it's reachable for all different $$$b_{i}$$$ values. While finding all "reachables" of all different $$$b$$$, we visit $$$\frac{a_{i}}{b_{i}}$$$ numbers for each different $$$b_{i}$$$. So, in the worst case, number of operations is $$$\frac{a_{max}}{1} + \frac{a_{max}}{2} + \dots + \frac{a_{max}}{a_{max}}$$$. Which is smaller than $$$a_{max}*log(a_{max}) = O(n*log(n))$$$

Here is my code. I got AC and maximum time is 0.009748 sec.

code