Reducto's blog

By Reducto, history, 3 years ago, In English

Hello, Codeforces community. Can you help me in this question, i am not able to get any intuition about solving this. Here is the question

Given a directed graph of N nodes, each node has a value A[i].

There is a directed edge of length 1 from node i to node j if and only if:

  • | i — j | <= k . The absolute difference between i and j is less than or equal to k.

  • A[i] > A[j]

For each node X, find B[X] which is the length of the shortest path to a node Y such that A[Y] is a prime number. If there is no way to go to such a node Y then we say that B[X] is 0.

Print the sum of all elements in array B.

Since the answer might be large return it modulo 10^9 + 7.

Constraints

1 <= N <= 10^5 and 1 <= k <= N

1 <= A[i] <= 10^6

Input

  • 5 2

  • 2 4 8 16 32

Output

  • 6

Input

  • 3 1

  • 1 2 4

Output

  • 1
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem link?

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

if A[x] is itself a prime then also the answer is 0 and if A[x] cannot reach any prime then also the answer is 0?

»
3 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Here is my solution, first sort everything on the basis of $$$pair(A[i],i)$$$ in increasing order. Note that if you are at index i then you can reach only the indexes which are at lower indexes than it, as they are only smaller than our current $$$A[i]$$$, let $$$dp[i]$$$ store the answer for index i, initially all the $$$dp[i]$$$ are some max value. Traverse the newly created array of $$$pair(A[i],i)$$$ let it be $$$x[n]$$$. update

dp[x[i].second]=min(dp[x[i].second-k] ... dp[x[i].second+k])+1

This min finding and updating can be done using segment tree, If $$$x[i].first$$$ is itself a prime update $$$dp[x[i].second]$$$ with 0. Finally add everything in dp array to the answer.