FoxStones
SRM 498 · 2010-11-01 · by ir5
SRM 498 · 2010-11-01 · by ir5 · Math
Problem Statement
Problem Statement
Fox Ciel has a rectangular board separated into 1x1 cells. The board is N cells wide and M cells high. Columns are numbered 1 to N from left to right, and rows are numbered 1 to M from top to bottom. A cell in column x, row y is said to have coordinates (x, y). Each cell contains a stone, and all stones are different. Also, some cells are marked. These marked cells are given in the int[] s sx and sy, where (sx[i], sy[i]) are the coordinates of the i-th marked cell.
Ciel is interested to know how many layouts of the same stones on this board are similar to the current layout. Two layouts are considered to be similar if, for each possible pairing of a stone and a marked cell, the distance between the stone and the marked cell is the same in both layouts. The distance between cells with coordinates (xA, yA) and (xB, yB) is defined as max{|xA-xB|, |yA-yB|}, where |z| is the absolute value of z.
Return the number of layouts that are similar to the current layout, modulo 1,000,000,009. Note that according to the definition above, the current layout is similar to itself, so it should also be counted.
Ciel is interested to know how many layouts of the same stones on this board are similar to the current layout. Two layouts are considered to be similar if, for each possible pairing of a stone and a marked cell, the distance between the stone and the marked cell is the same in both layouts. The distance between cells with coordinates (xA, yA) and (xB, yB) is defined as max{|xA-xB|, |yA-yB|}, where |z| is the absolute value of z.
Return the number of layouts that are similar to the current layout, modulo 1,000,000,009. Note that according to the definition above, the current layout is similar to itself, so it should also be counted.
Constraints
- N and M will each be between 1 and 200, inclusive.
- sx and sy will each contain between 1 and 50 elements, inclusive.
- sx and sy will contain the same number of elements.
- Each element of sx will be between 1 and N, inclusive.
- Each element of sy will be between 1 and M, inclusive.
- No two cells represented by sx and sy will have the same coordinates.
Examples
0)
6
1
{3}
{1}
Returns: 4
There are 4 similar layouts:
1)
2
2
{2}
{1}
Returns: 6
2)
3
3
{1,2,3}
{1,2,3}
Returns: 8
3)
12
34
{5,6,7,8,9,10}
{11,12,13,14,15,16}
Returns: 410850247
4)
200
200
{1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,8}
{1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1}
Returns: 950203064
large test
5)
197
199
{28,52,117,57,82,8,119,77,79,180,60,65,113,110,196,126,55,153,160,56,160,24,108,91,68,84,77,80,129,64,132,130,185,19,43,158,121,117,128,154,13,134,8,157,18,123,158,56,125,114}
{180,3,139,113,176,19,40,10,123,179,11,178,143,104,26,130,23,162,186,4,3,39,186,98,115,114,8,132,164,140,148,137,137,18,148,184,28,192,175,47,85,147,30,107,194,53,152,185,120,5}
Returns: 1
large random
7)
200
200
{1}
{1}
Returns: 92677741
Largest N,M, Edge cases (K=1)
13)
200
200
{1,1}
{1,200}
Returns: 988790209
K = 2
22)
200
200
{1,200,1,200}
{1,1,200,200}
Returns: 1
K = 4 (four corner)
23)
200
200
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
Returns: 537963690
Straight Line
34)
200
200
{200,199,198,197,196,195,194,193,192,191,190,189,188,187,186,185,184,183,182,181,180,179,178,177,176,175,174,173,172,171,170,169,168,167,166,165,164,163,162,161,160,159,158,157,156,155,154,153,152,51}
{200,199,198,197,196,195,194,193,192,191,190,189,188,187,186,185,184,183,182,181,180,179,178,177,176,175,174,173,172,171,170,169,168,167,166,165,164,163,162,161,160,159,158,157,156,155,154,153,152,148}
Returns: 61992900
Straight line + 1 Noize
37)
200
200
{146,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200}
{95,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200}
Returns: 425853588
(reverse order)
39)
1
1
{1}
{1}
Returns: 1
small cases
48)
10
4
{10,6,1,5,9,6,2,8,10,1,8,8,2,1,2,4,6,8,1,7,7,4,5,7,10,5,2,3,4,3,10,5,9,3,6,9,9,3,4,7}
{2,2,2,3,4,4,1,3,4,4,4,2,3,3,2,4,1,1,1,2,4,1,4,3,1,1,4,3,2,1,3,2,3,4,3,1,2,2,3,1}
Returns: 1
small case, large K
53)
15
9
{9,10,6,11}
{2,4,1,7}
Returns: 373357996
middle cases
77)
200
196
{200}
{143}
Returns: 875661008
large N,M, small K
92)
198
194
{171,129,49,184,94,76,45,47,163,143,64,172,140,83,125,146,101,69,82,30,83,67,59,150,127,144,153,150,128,79,177,133,69,179,32,136}
{181,135,98,55,110,7,167,97,51,30,138,142,82,174,85,170,180,90,153,190,8,25,2,43,68,60,163,1,18,41,160,7,49,163,93,83}
Returns: 1
large N,M, middle-large K
Submissions are judged against all 135 archived test cases, of which 17 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxStones with a public method int getCount(int N, int M, vector<int> sx, vector<int> sy) · 135 test cases · 2 s / 256 MB per case