SHOPPING - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Challenge

PREREQUISITES:

Ad-hoc

PROBLEM:

We are given a dynamic market in which new ATM and currency denomination are introduced. The task is to handle several cashier and atm transactions in such a way that the notes received from cashiers are minimum. The transactions are provided in an online fashion, i.e., next transaction is known only when the previous transaction is finished.

EXPLANATION:

The problem is a challenge problem so there is no perfect solution. The queries are given in an online manner, which means we have no knowledge about future transactions, and hence, we should use a strategy which should be able to handle a random future transaction fairly well (although it is quite common among top contestants to figure out the test data using multiple submissions, and hence future transactions in this problem).

Since we want to avoid getting more number of notes from cashiers, we should try to give her/him the money which is as close to requested amount as possible, This can be achieved if we have a balanced set of notes. Hence, while choosing an ATM to withdraw money, we should pick the one, which makes the resulting set of notes “well balanced” (i.e., provides notes of various denominations). For example, if currently we have n_i notes of c_i currency, and after withdrawing money from an ATM, we have m_i notes of c_i currency, then we should pick the ATM for which the following is maximum.

\sum (m_i + 4)/(n_i + 4).

The constant 4 is added to avoid division by zero, in case n_i = 0. This is just one optimization, and probably can be fine tuned more to have a better balanced set. It would be nice if top contestants could reveal their strategies.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

1 Like

You can build a “streak” of your available money, that is, calculate the maximum ‘r’ that satisfies the values in [1…r] are all possible to be built without ever changing.

For example, with notes 1x1, 1x2, 2x4, 1x20, the streak value is 11.

Thus, we can add notes from big to small for paying and apply a RMQ to see by adding which amount the number of changes we receive is lowest.

(For more implementation details, take a look at my ‘well-commented’ code)

The best editorial for shopping so far! You are well confident that your shopping editorial will inspire people and yes this is so right! I am impressed by it. Thanks for sharing. red vest

weaknesses, and somehow, a click here
click here
click here
click here
click here
click here
click here
click here
click here
click here
click here
click here
click here
click here it

//