Bank Business Strategy Optimization

This is an interesting and challenging problem inspired by real life. (but not all)

Story

Banking plays a critical role in our economy! Richard, a wealthy and seasoned financier, decided to start his own bank. To ensure its success, he invited his friend Bomb, a talented competitive programmer, as a technical advisor. Together, they aim to maximize the bank's profit by carefully deciding which businesses to accept.

Richard's bank handles two types of financial activities: Loaning (1) and Saving (2). With limited resources and a finite timeline, Bomb modeled a predictive dataset to help Richard make optimal decisions.

Can you help Bomb and Richard optimize their strategy and grow their bank's wealth?

Problem Description

At the start, the bank has 100,000 USD. You are given data for N predicted financial transactions, and your task is to decide whether to accept or reject each transaction to maximize the bank's profit.

Transaction Types:

Loaning (1):

• The bank lends out money (Amount) on a given date (From) and receives it back with interest on another date (To).
• For simplicity, the profit is 10% of the loan amount per year (pro-rated for partial years).

Saving (2):

• The bank deposits money (Amount) on a given date (From) and receives it back with interest on another date (To).
• The profit is 5% of the saving amount per year (pro-rated for partial years).

Input Format

The first line contains a single integer N — the number of predicted financial transactions.
Each of the next N lines describes a transaction in the format:
Type Amount From To

-Type: 1 (Loaning) or 2 (Saving).
-Amount: The transaction amount in USD (an integer).
-From: The start date in the format YYYY-MM-DD.
-To: The end date in the format YYYY-MM-DD.

Output Format

Output N lines, each containing either true (accept the transaction) or false (reject the transaction).

Constraints:

· 1 ≤ N ≤ 10^5
· 1 ≤ Amount ≤ 10^6
· 2023−01−01 ≤ From < To ≤ 2026−01−01
· The bank cannot handle negative balances at any point.

Example Input:

10  
1 50000 2023-06-01 2024-06-01  
2 20000 2023-01-01 2023-12-31  
1 30000 2023-07-01 2024-07-01  
2 40000 2023-12-01 2024-11-30  
2 15000 2023-02-01 2023-11-01  
1 60000 2023-08-01 2024-08-01  
2 35000 2023-03-01 2023-12-01  
1 25000 2023-04-01 2024-04-01  
2 10000 2023-05-01 2023-10-01  
1 45000 2023-09-01 2024-09-01 

Example Output:

true  
true  
false  
true  
true  
true  
false  
true  
true  
false  

Explanation:

• Transaction 1 (Loaning): The bank lends 50,000 USD for 1 year with a 10% annual profit. The return from this loan after 1 year will be:

50,000+(50,000×10%×1)=50,000+5,000=55,000 USD
Accepted.

• Transaction 2 (Saving): The bank saves 20,000 USD for 1 year with a 5% annual profit. The return from this saving after 1 year will be:

20,000+20,000×5%×1)=20,000+1,000=21,000 USD
Accepted.

• Transaction 3 (Loaning): The bank doesn't have enough money to accept this loan after the previous transactions. After lending 50,000 and saving 20,000, the available balance is only 50,000 USD, which is insufficient to cover this loan of 30,000 USD.

Rejected.

• Transaction 4 (Saving): The bank saves 40,000 USD for 1 year, with a 5% annual profit. The return from this saving will be:

40,000+(40,000×5%×1)=40,000+2,000=42,000 USD
Accepted.

• Transaction 5 (Saving): The bank saves 15,000 USD for about 9 months. The return after 9 months will be:

15,000+(15,000×5%×912)=15,000+562.5=15,562.5 USD
Accepted.

• Transaction 6 (Loaning): The bank lends 60,000 USD for 1 year with 10% annual profit. After accepting previous transactions, the bank now has a balance of 105,562.5 USD (after previous loans and savings). Since 60,000 USD is available, the loan is accepted. The return from this loan after 1 year is:

60,000+(60,000×10%×1)=60,000+6,000=66,000 USD
Accepted.

• Transaction 7 (Saving): The bank does not have enough funds to accept this saving request after previous transactions.

Rejected.

• Transaction 8 (Loaning): The bank lends 25,000 USD for 1 year with 10% annual profit. The return from this loan after 1 year is:

25,000+(25,000×10%×1)=25,000+2,500=27,500 USD
Accepted.

• Transaction 9 (Saving): The bank saves 10,000 USD for about 5 months. The return after 5 months will be:

10,000+(10,000×5%×512)=10,000+208.33=10,208.33 USD
Accepted.

• Transaction 10 (Loaning): After previous transactions, the bank does not have sufficient funds to accept this loan request.

Rejected.

Total Amount of Money After 3 Years:

After accepting transactions 1,2,4,5,6,8 and 9 the bank will have:
1.Starting balance: 100,000 USD.
2.After Transaction 1 (Loaning): 100,000−50,000+55,000=105,000 USD
3.After Transaction 2 (Saving): 105,000−20,000+21,000=106,000 USD
4.Transaction 3 (Loaning) is rejected, so the balance remains 106,000 USD.
5.After Transaction 4 (Saving): 106,000−40,000+42,000=108,000 USD
6.After Transaction 5 (Saving): 108,000−15,000+15,562.5=108,562.5 USD
7.After Transaction 6 (Loaning): 108,562.5−60,000+66,000=114,562.5 USD
8.Transaction 7 (Saving) is rejected, so the balance remains 114,562.5 USD.
9.After Transaction 8 (Loaning): 114,562.5−25,000+27,500=117,062.5 USD
10.After Transaction 9 (Saving): 117,062.5−10,000+10,208.33=117,270.83 USD
11.Transaction 10 (Loaning) is rejected, so the balance remains 117,270.83 USD.

Thus, the total amount of money in the bank after 3 years is 117,270.83 USD.

Notes:

1. Prioritize transactions based on profitability while avoiding negative balances.
2. Time management is crucial to ensure cash flow aligns with transaction deadlines.

Comments

[Richard Roberts]

Two years ago, a friend who is a businessman asked me to create the above challenge problem as a developer and demonstrate the model. It is an optimization problem using a greedy algorithm. If you are interested, try solving it.