All Tracks Algorithms String Algorithms Problem

Monk and Number Query

Easy-Medium, 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, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

Code Monk (Hashing)

View All Notifications