华为算法精英实战营第二期 - 转码与网络分发
举办方:华为技术有限公司
举办方:华为技术有限公司
Time limit: 2 sec
Memory limit: 256 MB
In its simplest terms, transcoding refers to the process of converting already compressed files, usually audio or video, into a different file format.
One of the most common uses for transcoding is content streaming. Transcoding is performed on special devices and the quality of related services depends highly on their effective use, including networking at minimal cost.
There is a map of some area consisting of N × N squares. Assume (0,0)enotes the top-left square and ( i, j )denotes the square at the i-th row from the top and j-th column from the left. Each square contains a positive integer number, which represents the amount of time it takes to transmit a signal from an adjacent square to that square.
All signals propagate in horizontal and vertical directions only. On the map there are many consumers (terminal nodes) and one provider (source node).
The goal is to place the minimum number of transmitters on the map so that the data stream from the provider could reach as many consumers as possible, in the expected format and with the minimum time delay each.
The consumer is a receiver of the stream — the terminal node. Consumers are scattered across the map, no more than one per square. Each consumer has a required input format.
Consumers must receive the stream in the expected format.
The transmitter is a transmitting “device” that also performs transcoding — the intermediate node. Initially, there are no transmitters on the map.
Each transmitter has one input and up to four outputs. Transmitters receive the stream in a specific format and can broadcast it in each of the four directions, as well as in two, three or four of them simultaneously, unchanged or in a new format for each direction.
Transmitters can broadcast the stream over any square: empty or non-empty, but only one end-point (another transmitter or end consumer) per each direction is allowed.
Transcoding from format i to format j takes time fij according to the transcoding table, but it is performed in parallel between all outputs of the transmitter, i.e. transcoding increases the time delay at a particular output only if the format change is required at that output.
The destination must be specified for each used output direction.Transmitters can only be installed in a free square and no more than one per square.
Each newly installed transmitter has its cost. The cost of the transmitter is calculated from a fixed part for the installation of the transmitter and an additional part for each of the outputs according to the following formula:
where P is a given parameter and 1 ≤ d ≤ 4 is the number of used output directions.
The provider is a transmitter that has no input — the source node. It is free of charge regardless of the number of outputs used. Before the broadcast, provider’s data is stored in a format with index 0. There is only one provider on the map.
At least one output of the provider must be used.
The first line of input data contains four numbers: grid side N , number of consumers M ,number of valid encoding formats F and transmitter cost parameter P.
The next line contains grid coordinates I,J of the provider.
The next N lines contain N positive integers gij defining the map grid.
The following M lines contain a description of the consumers. Each row contains 3 integers i,j,k where i and j correspond to the row and column on the grid where the consumer is located and k is the index of the desired encoding format.
The following F lines contain F non-negative integers, the time spent fij on transcoding from one format to another. Only the diagonal of this table contains 0, all other elements are strictly positive.
Constraints:
The output must contain T+2 lines,where 0≤T≤N2-M-1 (no more than the number of empty squares on the map) is the number of used transmitters.
The first line contains the number T itself.
The second line contains a description of the provider and the next T lines contain descriptions of each installed transmitter in the following format:
where i,j-row and column indices of the square with the transmitter (for provider’s description it is just I and J from the input ,1≤d≤4-number of outputs used ,and the d triples of numbers typei, idxi, fmti-type of the assigned target (another transmitter – 0 or end consumer – 1), its (target’s) 1-based index (indexing begins from 1, e. g. "0 2 0"-triplet means "broadcast to the second installed transmitter in format 0", "1 1 1"-triplet means "broadcast to the first consumer in format 1") and output stream format.
Let C be the set of satisfied consumers (those that got the stream in the required format), T be the set of installed transmitters, Time(p,c) be the total time the signal takes to reach consumer c from provider p (transcoding time included) and Cost(t)be the cost of transmitter t.
For each test case, a score is calculated using the following formula:
Because of the output format, C is always non-empty.
The submission score is the total score for each test case. If your submission produces an invalid output or exceeds the time limit for some test cases, then only those tests will be scored zero.
Input | Output |
5 3 2 10 2 3 20 15 10 10 10 10 10 10 20 10 10 15 10 90 10 10 20 10 10 10 10 10 10 10 10 0 0 0 3 1 0 1 3 0 0 10 20 0 | 2 2 3 2 1 3 0 0 1 0 2 1 2 1 2 0 0 2 0 0 1 1 1 1 0 |
Only support C++ language!
C++ compiler version: g++ 7.3.0
Optimization control options for compiling: -O3
The default C++ language dialect option is -std=gnu++14.