BARRAY Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Pratik Kumar
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

2671

PREREQUISITES:

None

PROBLEM:

You’re given an array A of N integers. You need to find the minimum cost of creating another array B of N integers with the following properties

  • B_i \ge 0 for each 1 \leq i \leq N
  • The GCD of adjacent elements of B is equal to 1, i.e, \gcd(B_i, B_{i+1}) = 1 for each 1 \leq i \lt N

The cost of creating B is defined as follows:

\sum_{i=1}^{N} 2^{|A_i - B_i |}

Find the minimum possible cost to create the array B. Since the answer can be huge print it modulo 10^9+7

Note: You need to minimize the value of total cost of creating the array B, and then print this minimum value modulo 10^9 + 7. For example, suppose there is a way to create the required B with a cost of 500, and another way to do it with a cost of 10^9 + 7 (which is 0 \pmod {10^9 + 7}). The output in this case would be 500 and not 0.

EXPLANATION:

Observation 1: Let us take k as the max(|A_i - B_i|), \; 1 \leq i \leq N. We would note that k is small(less than 20).

Now using the above observation let us solve this problem using DP.
Let us define our dp dp[i][j], where 1 \leq i \leq n and -k \leq j \leq k.
Here dp[i][j] stores the minimum cost and denotes that we have processed till i_{th} index and the element at the i_{th} index is modified to (A[i] + j). Now let us compute dp[i][j].
Clearly dp[i][j] depends on dp[i-1][j'], \;where \; -k \leq j' \leq k. As we are computing dp[i][j], we know that the value of i_{th} index is A[i] + j, so dp[i][j] depends on dp[i-1][j'] if and only if gcd(A[i] + j,A[i-1] + j') is 1. In that case:

dp[i][j] = min(dp[i][j], dp[i-1][j'] + 2^{|j|})

So we compute this dp and our answer would be min(dp[n][j]), where\; -k \leq j \leq k

TIME COMPLEXITY:

O(Nk^2), for each test case.

SOLUTION:

Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

Is there any proof to show that k is always small?

7 Likes
3

I just thought the max value of k would be 2

4

Please prove your observations. I would understand that we should prove it ourselves, but this is an editorial after all. I think it should be included…

14 Likes
5

does an observation need a proof? I would certainly enjoy having one, but I have no clue how hard that proof is. Since the constraints are small (N <= 10⁴), you can find out the maxK pretty fast with a few lines of code.

public static void getMaxK()  {
    int maxK = 0;
    for (int i = 1; i <= 1e4; i++) {
        int curMaxK = 0;
        int curK = 0;
        for (int j = 1; j <= 1e4; j++) {
            if(gcd (i, j) == 1) curK = 0;
            else curK++;
            curMaxK = max(curMaxK, curK);
        }
        maxK = max(maxK, curMaxK);
    }
    out.println(maxK);
}

Output: 13
Runtime: 3819ms (for those wondering)

1 Like
6

i think you should loop till 1e6 as the editorialist is taking about |Ai-Bi| and Ai range from 1 to 1e6

4 Likes
7

my bad yes. Well then it would probably not be a trivial observation anymore.

1 Like
8

It turns out that k = 2 works lol (submission) and its quite far away from 20, so are you not sure about the proof either?

I did the same dp in contest but I didn’t submit it because I expected k to be around 30-40 and that would overflow and mess up the mod

2 Likes
9

my solution is giving tle for k=20 but wa for 16
CodeChef: Practical coding for everyone wa
CodeChef: Practical coding for everyone tle

10

Proof k=20 works (actually works for k\geq 3 as well), we will prove that there are no x,y\leq 10^6 such that we can’t make their gcd 1 with such moves:

Lemma

Firstly notice that \gcd(X,Y) > 1 \implies \exists p\in\text{Primes}:\, p|X \text{ and } p|Y.
We define those p as representative.

Some Definitions

Now for i,j\in[-k,k] and for some x,y\leq 10^6\, there are, not necessarily distinct,
C = (2k+1)^2 values \gcd(x+i,\, y + j).
We suppose that all of them are >1, so each of them has a representative prime, let P be the multiset holding such primes and c_x the be number of times x appears in P.
Notice that c_p \leq \left \lceil \frac{2k+1}{p}\right \rceil^2.

Proof for k = 20

We can compute the maximum values of c_x
(c_2,c_3,c_5,c_7,c_{11},c_{13},c_{17}, c_{19},c_{23}, c_{29}, c_{31}, c_{37}, c_{41}, \dots) = (441, 196, 81, 36, 16, 16, 9, 9, 4, 4, 4, 4, 1,\dots)

So there are at least 12 + C - (441 + 196+\cdots+4) = 873 distinct primes each of which divides one of [x-k,x+k]. So by the pigeonhole \exist x'\in[x-k,x+k]: \lceil\frac{873}{2k+1}\rceil=22 distinct primes divide it , let them be q_1\dots q_{22} so now x+k\geq x' \geq q_1\cdots q_{22}\geq 2^{22} > 10^6+k \implies x>10^6 which is a contradiction, we are now done.

5 Likes
11

in 3rd sample test case
if array b=[9 16 7 19 10 7 1]
then cost would 7 but how 8?

12

I got ac just by initializing my ans with LLONG_MAX rather than 1e18 .somebody please explain this behaviour .

13

Hi! Great job! I solved this problem during the contest, but I didn’t come up with a proof. I am amazed at the negligence of the authors who did not bother to provide proof in the analysis. Thanks a lot for the explanation!

2 Likes
14

Hi! i think your proof just proves that we can make 2 numbers have gcd = 1 with k = 2 but how do we arrive at the conclusion that abs(Ai-Bi) <= k.
let’s say that there are 3 numbers A1, A2, A3. now your proof said that we can make gcd(A1, A2) =1 for k = 2 but let’s say there is only one pair of numbers (A1, A2) which have gcd = 1 with changes <= k now for pair (A2, A3) we again apply the theorem but how do we guarantee that there will be a pair of (A2, A3) with gcd=1 and changes <= k with same A2 as the (A1, A2) pair.

1 Like
15

I think there is a mistake in your explanation: why you divide 17 by 2? In proof for k = 20 you divided 873 by 41 (41 = 2 * k + 1). And in proof for k = 2 you divide 17 by 2 but 2 != 2 * k + 1. So why do you divide by 2, not 5?

16

Submission
So i did this, with k=2 and without even taking modulo and i get AC for this. Taking modulo is not even needed as max will be 4e4. No proof by editorialist though, so disappointed with this contest.

1 Like
17

Because it was, in fact, wrong. k=3 barely worked and for a second I thought k=2 also works. I deleted that part of the proof so I don’t confuse anybody

1 Like
18

Editorial doesn’t contain proof. Didn’t expect this from codechef.

19

What is the proof that k would be less than 20, what if it becomes of the order 10^3 or more?

20

I think the complexity is (n * k * k * log(max(a[i] + k))