PROBLEM LINK:
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.