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++, 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

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications