A Coin Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 32M

PyPy 2 128M

PyPy 3 128M

Author:

Plasmatic

Problem type

Angie is going shopping!

She has $N$ ~N~ different types of coins in her pocket, with the $i^\text{th}$ ~i^\text{th}~ type of coin being worth $d_i$ ~d_i~ dollars, and she's going to $V$ ~V~ stores. From the $j^\text{th}$ ~j^\text{th}~ store, she wants to buy $c_j$ ~c_j~ dollars worth of stuff from store $j$ ~j~, but store $j$ ~j~ only accepts the first $l_j$ ~l_j~ types of coins in her pocket!

Can you help her figure out the minimum number of coins to pay for each transaction in exact change?

Note that for the purpose of this problem, Angie has an infinite number of each type of coin.

Constraints

$1 \le l_j \le N \le 2 \times 10^3$ ~1 \le l_j \le N \le 2 \times 10^3~

$1 \le V \le 10^5$ ~1 \le V \le 10^5~

$1 \le d_i, c_j \le 10^4$ ~1 \le d_i, c_j \le 10^4~

Input Specification

The first line of input consists of $N$ ~N~ and $V$ ~V~, separated by a space.

The next line contains $N$ ~N~ space separated integers containing the values $d_i$ ~d_i~ ( $d_1, d_2, \dots, d_N$ ~d_1, d_2, \dots, d_N~).

The next $V$ ~V~ lines of input each contain the space separated integers $c_j$ ~c_j~ and $l_j$ ~l_j~.

Output Specification

There are $V$ ~V~ lines of output, with each line containing the minimum amount of coins needed to satisfy the payment in the $j^\text{th}$ ~j^\text{th}~ transaction.

If the $j^\text{th}$ ~j^\text{th}~ transaction cannot be satisfied however, print -1.

Note for Python users: To pass this question using Python you must select the PyPy interpreter instead of the normal one.

Sample Input 1

6 3
7 10 15 2 3 24
107 3
12 4
24 2

Sample Output 1

8
2
3

Explanation for Sample Output 1

Transaction 1: $6$ ~6~ coins with $$15$ ~$15~, $1$ ~1~ coin with $$10$ ~$10~, and $1$ ~1~ coin worth $$7$ ~$7~.

Transaction 2: $1$ ~1~ coin worth $$10$ ~$10~, and $1$ ~1~ coin worth $$2$ ~$2~.

Transaction 3: $1$ ~1~ coin worth $$10$ ~$10~, and $2$ ~2~ coins worth $$7$ ~$7~.

All that needs to be noted here is that for the third transaction, even though she has a coin worth $$24$ ~$24~ the third store won't accept it.

Sample Input 2

Sample Output 2

-1
-1
3

Explanation for Sample Output 2

Transactions 1 and 2: Not possible.

Transaction 3: $2$ ~2~ coins worth $$3$ ~$3~, and $1$ ~1~ coin worth $$1$ ~$1~.

Note that the first transaction cannot be completed without the third type of coin and the second one cannot be completed without the second type of coin.

Comments

-1

goatMan commented on July 14, 2020, 12:26 a.m.

Any explanation as to why I'm getting Java Out of Memory error for my code? Source: https://dmoj.ca/src/2202142.

0

Plasmatic commented on July 14, 2020, 4:01 p.m. ← edited →

You use too much memory

Edit: see https://dmoj.ca/problem/acoinproblem#comment-11454

-1

paydayzcool commented on Feb. 5, 2020, 7:20 a.m. ← edited →

My submission got "failed initialising" on c++17, but my code runs fine in visual studio. Does anyone know what I can do about this?

2

Tzak commented on Feb. 5, 2020, 1:00 p.m.

Your int dpTable[2 * 1000][10001] uses 2000 x 10001 x sizeof(int) = ~80MB, which by itself already exceeds the 32MB memory limit.

0

AryanG commented on Aug. 3, 2019, 11:11 p.m. ← edited →

I'm getting a TLE in c after problem 2. Are there any ways to improve the algorithm.

1

4fecta commented on Aug. 4, 2019, 2:19 p.m.

There are indeed many ways to improve your algorithm. Try to work out the time complexity to see why you TLE, and how you should fix it.

1

AryanG commented on Aug. 4, 2019, 6:30 p.m. ← edited →

My current runtime is $\mathcal{O}(mV)$ ~\mathcal{O}(mV)~ where $m$ ~m~ is the number of coins used and $V$ ~V~ is the target to achieve.

2

4fecta commented on Aug. 4, 2019, 8:43 p.m. ← edit 3 →

What do you mean by "target to achieve"? If you mean the cost of an item, please note that there are multiple queries for this question. Running an $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ algorithm for each item would be insufficient.

1

AryanG commented on Aug. 5, 2019, 11:38 p.m. ← edited →

The algorithm described is for each query. Each query takes $\mathcal{O}(mV)$ ~\mathcal{O}(mV)~ time.

3

mangoqwq commented on April 10, 2019, 12:50 a.m.

why am i getting invalid return on the first case?

idk my code works for the two sample inputs for some reason aaa

5

Blazebot99 commented on Feb. 12, 2019, 5:03 p.m.

Still TLEing in PyPy3, any way to improve my algorithm? Thanks in advance!

0

czylabsonasa commented on Oct. 24, 2019, 11:08 a.m. ← edited →

tle with pypy3 but ac (in 23sec) with pypy2, with the very same code... i suppose that the time limit is not for pypy3, and/or you expected to do some magic...

0

injust commented on Oct. 24, 2019, 12:51 p.m. ← edited →

No, you just got unlucky with the judges. Resubmit a couple of times and it'll AC.

Same thing happens with PyPy 2, might I add.

-2

Plasmatic commented on Oct. 24, 2019, 12:01 p.m. ← edited →

My code gets worst case ~1.3s with PyPy3