All Tracks Algorithms String Algorithms Problem

Monk and Number Query

Easy-Medium, Hashing, Trees


Monk is playing with a Tree T rooted at node 1 consisting of N nodes. Each node has a digit written on it ranging from 0 to 9 inclusive. He has an interesting task for you as follows:

You are given a prime number K that is co-prime to \(10\) and Q queries to answer. In each query, you shall be given 2 numbers i and j. It is guaranteed that for each query, node i shall be an ancestor of node j or \(i = j\). Now, you need to report if the number formed by writing out the the digits from left to right of each node on the path from i to j inclusive, is divisible by K.

Writing out the digits from left to right implies that the digit written on node i shall be the most significant digit of the number thus formed, and the one written on node j shall be the least significant one. For more, refer to the sample explanation.

Can you do it ?

Input Format :

The first line contains 3 space separated integers denoting N, K and Q.

The next line contains N space separated integers. where the \(i^{th}\) integer is \(A[i]\) and denotes the digit written on node i.

The next line contains \(N-1\) space separated integers, where the \(i^{th}\) integer denotes the parent of node \(i+1\).

Each of the next Q lines contains 2 space separated integers, denoting the parameters of the \(i^{th}\) query.

Output Format :

For the \(i^{th}\) query, print "YES" (without quotes) if the number formed by the parameters of the \(i^{th}\) is divisible by K, else print "NO" (without quotes).

Constraints :

\( 1 \le N \le 2 \times 10^5 \)

\( 2 \le K \le 2 \times 10^7\). It is guaranteed that K is a prime number and is co-prime to \(10\)

\( 0 \le A[i] \le 9 \)

\( 1 \le Q \le 2 \times 10^5 \)

\( 1 \le parent[i] < i \)

Note :

The number thus formed may contain leading zeros.

7 7 3
3 4 4 3 4 5 9
1 2 2 1 5 5
1 3
1 4
5 7

enter image description here

In the image above, the numbers written on the nodes represent their value, and the number written just beside them represent their index.

For the queries :

  1. \(344\) that is not divisible by 7

  2. \(343\), that is divisible by 7

  3. \(49\) that is divisible by 7

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

Code Monk (Hashing)

View All Notifications