ChristmasSongBroadcast
SRM 773 · 2019-12-20 · by misof
Problem Statement
"All I want for Christmas is for everyone to be forced to listen to 'All I Want For Christmas' and all other Christmas songs for the whole December!" exclaimed Santa.
You are the elf in charge of broadcasting Christmas songs to all the households in one specific village. The village contains N households, and we'll number them 0 to N-1.
You have the whole Elf Broadcasting Network at your disposal. The network consists of T directional broadcast towers, numbered 0 to T-1. Each tower can be used arbitrarily many times. When used, the tower will broadcast the whole Mariah Carey Christmas album to any one household. The cost of doing so depends both on the household and on the tower used, in a very specific way: broadcasting from tower x to household y costs ((A[y] * x + B[y]) modulo 1,000,000,007) elf dollars. Note that all the values in A are small (see Constraints).
Once a household has been "infected" by Christmas music, they are under your control and you can use them to spread the "love" to their neighbors.
Each household that has already heard the album can call any other household and play them the album.
The costs of doing so are given in the
Return the minimum total cost of spreading the Christmas joy to everyone in the village.
Notes
- It can be shown that the optimal answer will always fit into a signed 32-bit integer.
Constraints
- T will be between 1 and 10^9 + 7, inclusive.
- N will be between 1 and 50, inclusive.
- A, B and directCost will have N elements each.
- Each element of A will be between 1 and 100, inclusive.
- Each element of B will be between 0 and 10^9 + 6, inclusive.
- Each element of directCost will have N characters.
- For each i, directCost[i][i] will be '-' (and should be ignored).
- For each distinct i and j, directCost[i][j] will be one of [0-9A-Za-z] (i.e., a digit, an uppercase letter, or a lowercase letter).
- For each distinct i and j, directCost[i][j] will be equal to directCost[j][i].
1000000007
{1, 10, 100}
{7, 7, 7}
{"-AA",
"A-A",
"AA-"}
Returns: 0
There are three households in this village. The direct broadcast from any house to any other house costs 65 elf dollars (65 is the ASCII value of 'A'). However, we will not use this option because for each household there is a broadcasting tower that can broadcast the song to the house for free. The optimal solution is to broadcast from tower 1,000,000,000 to house 0, from tower 100,000,000 to house 1, and from tower 10,000,000 to house 2.
1
{1, 1, 1}
{1600, 1500, 1700}
{"-01",
"0-A",
"1A-"}
Returns: 1597
There is only a single tower. Broadcasting from the tower to household 0 costs 1600, doing so to household 1 costs 1500, and for household 2 we would pay 1700 elf dollars. The optimal solution is to use the tower to send Christmas music to household 1, then have household 1 call household 0 (cost 48) and then have the now-infected household 0 call household 2 (cost 49).
2
{100, 100, 100, 100}
{0, 35, 999999910, 123456789}
{"-01z",
"0-Az",
"1A-z",
"zzz-"}
Returns: 160
This time, one cheapest solution is to broadcast from tower 0 to household 0 (cost 0), then from tower 0 to household 1 (cost 35), then from tower 1 to household 2 (cost 3), and finally from any of those households to household 3 (cost 122, which is the ASCII value of 'z').
1
{47}
{1000000006}
{"-"}
Returns: 1000000006
Sometimes broadcasting can be pretty expensive.
123456789
{47}
{1000000006}
{"-"}
Returns: 4
Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChristmasSongBroadcast with a public method int minimizeCost(int T, vector<int> A, vector<int> B, vector<string> directCost) · 118 test cases · 2 s / 256 MB per case