You are not logged in. Please login at www.codechef.com to post your questions!

×

CHINSM - Editorial

4
1

PROBLEM LINK:

Contest
Practice

Author: Vlad Mosko
Tester: Hiroto Sekido
Editorialist: Kevin Atienza

DIFFICULTY:

Medium

PREREQUISITES:

Divisor lists, intervals, combinatorics, ad hoc

PROBLEM:

Given an array of integers $[A_1, \ldots, A_N]$ and a number $K$, find the number of subarrays containing no bad pairs. A pair $(i,j)$ is a bad pair if $i < j$ and $(A_i \bmod A_j) = K$.

QUICK EXPLANATION:

  • For each position $j$, compute the largest $i_j < j$ such that $(i_j,j)$ is a bad pair. Collect all such bad pairs gotten this way, sorted by $j$. (There are at most $N$ such pairs, but may be less, because for some $j$s there could be no such $i_j$s).
  • Remove a pair $(i_j,j)$ if $j > 1$ and $i_{j-1} \ge i_j$.
  • Add the pair $(N, N+1)$ at the end of the list.
  • Assume that the list of pairs acquired is $[(i_1,j_1), (i_2,j_2), \ldots, (i_m,j_m)]$. Then the answer is: $$\frac{N(N+1)}{2} - \sum_{n=1}^{m-1} i_n (j_{n+1} - j_n)$$

To compute all pairs $(i_j,j)$, we need to store, for each value $v > K$, the maximum $i < j$ such that $A_i > K$ and $(A_i \bmod v) = K$ (there are at most $\max A_i$ such lists). We also store the maximum $l < j$ such that $A_l = K$. As we increase $j$, we need update some of these lists: When going to a new value of $j$ we only need to update at most $O(\sqrt{\max A_j})$ lists.

EXPLANATION:

Let's first assume that we have all the bad pairs, and we want to compute the number of subarrays containing no bad pairs. This is just equal to the number of subarrays (which is $N(N+1)/2$), minus the number of subarrays containing at least one bad pair. We will compute the latter instead, and we'll call a subarray bad if it contains at leaset one bad pair.

First, notice that all ${N \choose 2}$ pairs can be bad pairs (for example, if $A_i = 1$ for all $i$ and $K = 0$). Therefore we can't even compute all the bad pairs, because that is too slow. However, notice that not all bad pairs are important. For example, if the pair $p_1$ completely contains the pair $p_2$, then any subarray containing $p_1$ also contains $p_2$. Thus, the pair $p_1$ is redundant, i.e. if we remove the pair $p_1$ from our list, then the set of bad subarrays stay the same.

Thus we can remove all bad pairs completely containing other bad pairs. Note that after doing so, no two bad pairs share the same left (or right) endpoint any more (otherwise one will contain the other). Since there are at most $N$ endpoints, this reduces the number of bad pairs we have to at most $N-1$, which is more manageable :)

This also shows that for a given endpoint $j$, there is only at most one important bad pair $(i,j)$ ending in $j$, and it's the one with the maximum $i$. Therefore, the first step is to compute the maximum $i$ for each $j$ such that $(i,j)$ is bad (ignoring the $j$s for which there are no such $i$).

Bad pairs ending in every position

Assuming $A_j > K$, $(A_i \bmod A_j) = K$ is equivalent to: $$\begin{align*} (A_i \bmod A_j) &= K \\\ A_i &\equiv K \pmod{A_j} \\\ A_j &| (A_i - K) \end{align*}$$ This means that $A_j$ is a divisor of $(A_i - K)$.

For every endpoint $j$, we need to compute the maximum $i$ such that $(i,j)$ is bad. Surely, there are no bad pairs such that $A_i < K$ or $A_j \le K$, because $(A_i \bmod A_j) < K$ in those cases.

Suppose that, for every value $v$, $K < v \le \max A_i$, we store the value $i_v$, which we define as the maximum $i_v < j$ such that $(A_{i_v} \bmod v) = K$. Note that $i_v$ is also dependent on $j$, so as we increase $j$, we will need to update some of the $i_v$s, but for now, assume we can do those updates. If so, the $i$ we are looking for is simply $i_{A_j}$ :)

Now for the updates. As we leave a particular value of $j$ and go to the next one ($j+1$), we need to update some of the $i_v$s, specifically for those $v$s having $(A_j \bmod v) = K$. As shown above, this is equivalent to $v$ being a divisor of $A_j - K$, so we only update for those $v$s that are divisors of the number $A_j - K$. This is good, because it has only at most $2\sqrt{A_j - K}$ such divisors :)

Unfortunately, the last statement is incorrect for the case $A_j = K$. If $A_j = K$, then $A_j - K = 0$. But every $v$ is a divisor of zero! In this case, updating all the lists may be too slow, so we need to do something else. This is simple; we can simply maintain a separate value $l$, which is the maximum $l < j$ such that $A_l = K$. $i_v$ is now modified to exclude those $i$s such that $A_i = K$, and for an endpoint $j$, the $i$ we are looking for is now $\max(i_{A_j}, l)$ :) Thus, we maintain the fast running time!

The total running time of this step is $O(N \sqrt{\max A_i})$.

After getting the bad pairs $(i_j,j)$ for every such $j$, we can simply remove those pairs for which $i_{j-1} \ge i_j$, because those pairs are not important. Now we have a list of bad pairs $[(i_1,j_1), (i_2,j_2), \ldots, (i_m,j_m)]$ satisfying the following: $$i_1 < i_2 < \cdots < i_m$$ $$j_1 < j_2 < \cdots < j_m$$

Subarrays containing bad pairs

We now want to compute the number of subarrays containing at least one bad pair.

Each such subarray contains a unique "rightmost" bad pair, so we can compute, for each $1 \le k \le m$, the number of subarrays whose rightmost bad pair is $(i_k,j_k)$. Let's denote this by $f(k)$. Then the number of subarrays containing at least one bad pair is: $$\sum_{k=1}^m f(k)$$

Let's first compute $f(m)$ (the last one). For a subarray $[i\ldots j]$ to contain $(i_m,j_m)$, it must be true that $1 \le i \le i_m$ and $j_m \le j \le N$. There are $i_m(N+1-j_m)$ such choices for such subarrays, therefore $f(m) = i_m(N+1-j_m)$.

Now, let's compute $f(k)$ for $1 \le k < m$. The subarray $[i\ldots j]$ should contain $(i_k,j_k)$, but we need to ensure that this is the rightmost bad pair, i.e. the subarray doesn't contain $(i_{k+1},j_{k+1})$. This means that $1 \le i \le i_k$ and $j_k \le j$. However, $j < j_{k+1}$ should be true, otherwise it will contain the pair $(i_{k+1},j_{k+1})$. Therefore, there are $i_k (j_{k+1} - j_k)$ choices for such subarrays, and thus we have $f(k) = i_k(j_{k+1} - j_k)$ :)

This step runs in $O(N)$ time :)

Here's an implementation in C++:

#include <stdio.h>
#include <algorithm>
using namespace std;
#define ll long long
#define LIM 100111

int I[LIM];

int main() {
    for (int j = 0; j < LIM; j++) I[j] = -1;

    int n, k;
    scanf("%d%d", &n, &k);

    ll total = n*(n+1LL) >> 1;
    int pi = 0, pj = 1;
    #define add_pair(ci,cj) do {\
        total += pi * (pj - (cj));\
        pi = ci;\
        pj = (cj);\
    } while (0)

    int l = 0;
    for (int j = 1; j <= n; j++) {
        int a;
        scanf("%d", &a);
        if (a == k) {
            l = j;
        } else if (a > k) {
            int i = max(I[a], l);
            if (pi < i) {
                add_pair(i, j);
            }

            a -= k;
            for (int v = 1; v * v <= a; v++) {
                if (a % v == 0) I[v] = I[a / v] = j;
            }
        }
    }

    add_pair(n, n+1);

    printf("%lld\n", total);
}

Some implementation details:

  • We added a sentinel leftmost bad pair $(0,1)$ to make the add_pair macro simpler.
  • There is also a sentinel rightmost bad pair $(N,N+1)$ so that $f(m)$ (the last pair) is not special :)
  • There is no array $A$ allocated; instead the individual values of $A$ are inputted and processed on the fly.

Time Complexity:

$O(N\sqrt{\max A_i})$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 16 Aug '15, 13:07

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 15 Jan '16, 19:32

admin's gravatar image

0★admin ♦♦
19.8k350498541


Setter's solution giving WA for test case :- 6 3 64 1 4 8 6 3 Sry, If I done Mistake, this is my first comment :0

link

answered 16 Jun '16, 05:24

nikil_agar's gravatar image

4★nikil_agar
29
accept rate: 0%

1st time I solved question number 6 at long challenge. The best part it was AC in 0.00 sec with 2.7M memory.

https://www.codechef.com/viewsolution/7826337

link

answered 17 Aug '15, 18:18

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

I got 18 correct sub tasks out of 20.

One of them showed TLE and the other WA.

I can very well understand the reason for TLE because my code used higher time (different approach). But I can't understand why I got that 1 WA.

Can any one explain me?

Here's my code link text

link

answered 18 Aug '15, 10:23

prrateekk's gravatar image

3★prrateekk
534216
accept rate: 12%

I did not go through your code thoroughly(I am sorry for that :)), but one thing came into my mind -- are you sure that the int variable 'one' is not getting overflowed in any test case?

(19 Aug '15, 01:04) snk9674★

What's the difficulty level of this problem?

link

answered 20 Aug '15, 09:39

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

Just if you want an explanation for my above solution mentioned (https://www.codechef.com/viewsolution/7826337), you can have a look at https://discuss.codechef.com/questions/73958/august-challenge-2015-chef-and-insomnia.

link

answered 21 Aug '15, 20:54

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

Statement 1 : "For example, if the pair p1 completely contains the pair p2, then any subarray containing p1 also contains p2. Thus, the pair p1 is redundant, i.e. if we remove the pair p1 from our list, then the set of bad subarrays stay the same"

Statement 2 : "Thus we can remove all bad pairs completely contained in other bad pairs"

Aren't these two lines from the above editorial contradicting each other? First one says remove 'p1' and second one says remove all ' p2's ' ...!!

link

answered 23 Aug '15, 19:20

sharad07's gravatar image

4★sharad07
20711
accept rate: 3%

It's a simple typo and has been fixed.

(23 Aug '15, 23:47) kevinsogo7★

Sorry but I have been trying to understand the editorial since 3 hours now and I couldn't get it. Can u please take an example and describe the flow of algorithm. I think it would also help others looking for better explanation as well

Thanks in advance

link

answered 29 Aug '15, 01:35

ironman8888's gravatar image

2★ironman8888
31
accept rate: 16%

Just if you want an explanation for my above solution mentioned (https://www.codechef.com/viewsolution/7826337), you can have a look at https://discuss.codechef.com/questions/73958/august-challenge-2015-chef-and-insomnia.

(29 Aug '15, 02:25) likecs6★

Hey , can u give explanation for your code or the above code by taking a small example. I am not able to understand the explanation you gave in that link . Thanks in advance

link

answered 31 Aug '15, 16:15

ironman8888's gravatar image

2★ironman8888
31
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,851
×2,655
×968
×899
×186
×57
×18

question asked: 16 Aug '15, 13:07

question was seen: 6,527 times

last updated: 16 Jun '16, 05:24