All Tracks Algorithms String Algorithms Problem

Monk and Number Query
Tag(s):

Easy-Medium, Easy-Medium, Hashing, Trees

Problem
Editorial
Analytics

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.

SAMPLE INPUT
7 7 3
3 4 4 3 4 5 9
1 2 2 1 5 5
1 3
1 4
5 7
SAMPLE OUTPUT
NO
YES
YES
Explanation

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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Code Monk (Hashing)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications