Problem Statement |
| | You are having a party. There are G guests attending it, and the food is represented by C cakes. All cakes are different, but you want to distribute them among the guests in a way which makes everybody as happy with their share of the cakes as possible. Fortunately, the guests' preferences for the cakes differ as well, so you might manage to do this...
Each cake is a square, and can be thought of as a square grid of S x S sections. You want the cakes to be cut prettily, so you don't want to ruin any of these sections, thus you're going to cut the cakes along the lines between the sections. Furthermore, you don't want to mess with multiple pieces of cakes per guest, so you want to give each guest a single piece of cake, formed by a 4-connected group of sections. You can't give a guest pieces of two different cakes, or two separate pieces of one cake.
The cakes consist of I ingredients of two types: bases and decorations. It is possible to have a cake without some of the ingredients from the list. If a base is present in a cake, it forms a layer of approximately constant height in all sections of the cake. If a decoration is present in the cake, it forms a layer of approximately constant height in some of the sections of the cake, and is absent in other sections. All sections have the same area (numerically equal to 1), so the quantity of an ingredient in a section is defined by its height in it.
You know how your guests feel about each of the ingredients; the joy received by a guest after consuming 1 unit of ingredient (the quantity contained in 1 unit of height over one section) can be measured as an integer between 1 and 10, inclusive. The joy of consuming a piece of cake is measured as a sum of joys of consuming all ingredients in it.
You are given the following information about the cakes and the guests:
-
the number of cakes C;
-
the number of guests G;
-
the number of ingredients I;
-
the size of the side of one cake (in sections) S;
-
the preferences of your guests, given as a int[] preferences: the opinion of guest i (0-based) about ingredient j (0-based) is given by preferences[i*I+j];
-
the structure of the cakes, given as a int[] cakes. The height of layer of ingredient j in section at (row, col) of cake i is given by cakes[i*I*S*S+row*I*S+col*I+j]. All indices are 0-based.
You have to return the way you'll split the cakes between the guests as a int[] of C*S*S elements. Element i*S*S+row*S+col of your return will give the 0-based index of the guest who'll get the section at (row, col) of cake i, or any number less than 0 or greater than G-1 if nobody gets the section. Note that the sections assigned to one guest must belong to only one of the cakes, and they must form a 4-connected group within that cake. It is possible to give a guest no sections at all, in this case he will get zero joy.
Your raw score for a test case will be the smallest of joys received by your guests as a result of your division. If your return was invalid (had wrong number of elements, or assigned sections to guests in an invalid way), your raw score for a test case will be 0. Your overall score will be the arithmetic average of 10000*YOUR/BEST over all test cases, where YOUR is your raw score on a test case, and BEST is the greatest score achieved by anyone on that test case.
Each test case is generated as follows:
- C is chosen between 1 and 10, inclusive (here and later "chosen" means "chosen uniformly, at random").
- G is chosen between 2*C and 10*C, inclusive.
- Each element of preferences is chosen between 1 and 10, inclusive.
- S is chosen as an even integer between 20 and 100, inclusive.
- I is chosen between 2 and 10, inclusive.
- Generation of cakes tries to simulate the procedure of making a real-world cake. The first I/2 (rounded down) ingredients are bases, the rest are decorations. Each base ingredient is placed at a constant height, but a small random error is added to this height at each specific cell. Each decoration ingredient is used for a given cake with 50% probability. If it is used, then it generates between (S*S)/400 and (S*S)/40 "roses", inclusive (integer division). Each "rose" occupies a certain center cell and its 4 neighbouring cells. Also, each "rose" is mirrored to produce 3 other "roses". This mirroring can happen in one of 3 possible ways (chosen randomly). One possible way is to place "roses" at (S-r-1, c), (r, S-c-1), (S-r-1, S-c-1) in addition to a "rose" at (r, c). Other two ways are similar. Finally, exactly one decoration ingredient (if it is used) will generate a "rim". This ingredient will be placed in cells located close enough to the cake's borders.
- The description of cakes generation procedure above is not exhaustive. You can check the offline tester's code (method generate) for details.
An offline tester is available. You can use it to test your solution locally. |
| |
Definition |
| | | Class: | Cakes | | Method: | split | | Parameters: | int, int, int, int, int[], int[] | | Returns: | int[] | | Method signature: | int[] split(int C, int G, int I, int S, int[] preferences, int[] cakes) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Two sections are neighbours if they share a side. A group G of sections is 4-connected if there exists a path P between any two sections from G such that all sections from P belong to G and any two consecutive cells from P are neighbours. |
| - | The memory limit is 1024 MB and the time limit is 10 seconds (which includes only time spent in your code). |
| - | There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. |
| - | The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
C = 2
G = 4
I = 4
S = 20
" | |
|
| 1) | |
| | | Returns: "seed = 2
C = 4
G = 32
I = 5
S = 48
" | |
|
| 2) | |
| | | Returns: "seed = 3
C = 4
G = 35
I = 10
S = 44
" | |
|
| 3) | |
| | | Returns: "seed = 4
C = 6
G = 36
I = 3
S = 50
" | |
|
| 4) | |
| | | Returns: "seed = 5
C = 7
G = 44
I = 5
S = 22
" | |
|
| 5) | |
| | | Returns: "seed = 6
C = 7
G = 62
I = 4
S = 48
" | |
|
| 6) | |
| | | Returns: "seed = 7
C = 5
G = 28
I = 8
S = 82
" | |
|
| 7) | |
| | | Returns: "seed = 8
C = 6
G = 53
I = 4
S = 50
" | |
|
| 8) | |
| | | Returns: "seed = 9
C = 3
G = 11
I = 8
S = 26
" | |
|
| 9) | |
| | | Returns: "seed = 10
C = 6
G = 57
I = 5
S = 58
" | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.