Editorial for Bubble Cup V18 A Splitting Money


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

It’s useful to notice that since we can create multiple addresses for free we never need to transfer bitcoin to an existing address. Therefore, we can solve the problem for each public address separately and sum the fees at the end.

In order to minimize the number of fees we will need to minimize the number of transactions, because the cost per transaction is constant. Therefore, we will need to make transactions as large as possible – in other words f + x. So, if number of satoshies in the address is a[i], we might think we need exactly [\frac{a[i]}{f+x}] transactions in order to make them \le x. Unfortunately, this isn’t entirely true because the remainder a[i] \bmod (f + x), can still be larger than x. If it is, then we need one extra transaction of size f + 1. This solves the problem per one public address.

Another important observation is that even though all numbers on the input are 32-bit integers, given the constraints, sum of the fees per public address can be larger than 32-bit integer allows. So we will need to use 64-bit integer for summation.


Comments

There are no comments at the moment.