All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Share Market
Tag(s):

Algorithms, Bitmask, Dynamic Programming, Medium-Hard

Problem
Editorial
Analytics

One fine day, Monk decided to get into the share market. Being a final year student, he doesn't have a huge amount of money to invest. However, he has N antique items each worth \(W[i]\) units, which he is ready to sell to buy any of the K shares to start his business. Cost of \(j^{th}\) share is \(C[j]\) units. Is there a way to make \(C[j]\) units using exactly \(X[j]\) items i.e. \(C[j]\) = sum of worth of exactly \(X[j]\) items.

He is really tired from all the classes and exams. Hence, he asks you to tell him if he can buy a particular share using X items where for each share each item is only considered once and for all shares each item is available.

Input
First line of input contains T denoting number of test cases.
Each test case begins with a single integer N denoting the number of antique items which he is ready to sell. Next line contains N integers separated by a space representing worth \(W[i]\) units of each item. Next line contains an integer K denoting the number of shares Next line contains an array of K integers representing X, each integer represents \(X[i]\). Last line contains an array of K integers representing cost of each share \(C[i]\).

Output
For each testcase, print K lines. Each line of the test-case represents if it possible to buy a share i having cost \(C[i]\) units using exactly \(X[i]\) items. Print "Yes" if it is possible, "No" otherwise.

Constraints

  • \(1 ≤ T ≤ 1000\)
  • \(1 ≤ N ≤ 50\)
  • \(1 ≤ W[i] ≤ 100\)
  • \(1 ≤ K ≤ 500\)
  • \(1 ≤ X[i] ≤ 50\)
  • \(1 ≤ C[i] ≤ 5000\)
SAMPLE INPUT
1
2
1 2
3
2 2 1
3 4 2
SAMPLE OUTPUT
Yes
No
Yes
Explanation

Here, we have one single testcase where worth of antique items are {1,2}. Now explanation regarding the purchase of 3 shares is as follow.

  • Cost of first share is 3 and he wishes to buy it using 2 antique items which is possible by selling both the antique items 1 + 2 = 3 hence Yes
  • Cost of second share is 4 and he wishes to buy it using 2 antique items which is not possible by selling any combination of antique items hence No
  • Cost of third share is 2 and he wishes to buy it using 1 antique items which is possible by selling second antique item hence Yes
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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?