Problem Statement
Time limit is 6 seconds.
Absurdistan is a rectangular country that is divided into a grid of R rows by C columns of unit squares. These have coordinates from (0, 0) to (R-1, C-1).
We are building broadcast towers. Each broadcast tower occupies one square of the grid. Additionally, in the future each broadcast tower will have to be anchored. The anchors for a tower must occupy either both squares that are horizontally adjacent to the tower, or both vertically-adjacent squares.
Each square can only contain at most one object (i.e., either a tower, or the anchor of exactly one tower, or nothing). Anchors of a tower cannot be placed outside the grid. This limits how towers on the boundary of Absurdistan can be anchored.
Below is an example of several correctly anchored towers, using 'T' to denote towers and different numbers to denote anchors for different towers. Note that tower with anchors denoted '5' could have also been anchored vertically.
+----------+
| 0 4|
| T1 5T5 T|
| 0T3T3 4|
| 12T2 |
+----------+
You are given a sequence of 50,000 not necessarily distinct squares: (qr[0], qc[0]), ..., (qr[49999], qc[49999]). These are candidates for the places of towers in Absurdistan.
The tower building committee processes these candidates in the given order, using the following algorithm:
start with an empty set T of towers
for each i from 0 to 49999:
let S = (qr[i], qc[i]) be the current candidate square
if S is already in T:
ignore candidate number i (do nothing)
else:
let T' = T + {S}
if it is possible to build and correctly anchor all towers in T':
accept candidate number i and set T = T'
else:
reject candidate number i
You are given X. Return the number of the X-th (1-based index) rejected candidate, or -1 if there is no such candidate.
X is usually small. Please read the exact constraints for X carefully.
--------------------
In order to keep the input small, the sequence of candidate squares is generated pseudorandomly. Please use the following pseudocode to generate it:
state = seed
for i = 0 to 49999:
state = (state * 1103515245 + 12345) modulo 2^31
qr[i] = (state div 1000) mod R
state = (state * 1103515245 + 12345) modulo 2^31
qc[i] = (state div 1000) mod C
Definition
- Class:
- TowerPlacement
- Method:
- solve
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int solve(int R, int C, int seed, int X)
- (be sure your method is public)
Notes
- Candidates that are ignored do not count as rejected candidates.
- It is possible that a rejected square shares coordinates with another, previously rejected square. Each of those still counts as a separate rejection.
Constraints
- R will be between 1 and 100,000, inclusive.
- C will be between 1 and 100,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- X will be between 1 and 500, inclusive.
- Let N = min(50000, R*C). Then, X*N will not exceed 200,000.
Examples
1
1
47
5
Returns: 4
The sequence has 50,000 copies of the cell (0, 0). Each of them gets rejected because Absurdistan is too small for the tower's anchors.
3
3
47
4
Returns: 6
The sequence of candidates begins as follows: (1,1) (2,0) (0,2) (0,0) (1,1) (1,0) (2,1) (2,0) (1,1) (0,1) (1,0) (0,1) ... The following happens: Candidate 0 is accepted. We have T = { (1,1) }. Candidates 1, 2, and 3 are rejected. We cannot ever anchor a tower built in a corner of Absurdistan. Candidate 4 is ignored, we already have it in T. Candidate 5 is accepted. It is possible to build towers at (1,1) and (1,0) and anchor both of them vertically. Now T = { (1,1), (1,0) }. Candidate 6 is rejected: if we build towers at (1,1), (1,0), and (2,1) it is not possible to anchor all three while keeping everything disjoint. Candidate 6 was the fourth rejected candidate, so we return 6.
10000
14700
12345
1
Returns: -1
Plenty of room for all the towers and their anchors, nothing gets rejected. (A few candidates do get ignored.) The first few candidates: (6932,7783) (9466,8783) (9335,7850) (3799,671) (1188,9750) (2930,3413) (9546,171) (5770,4508) (9212,12084)
10
12
123456789
3
Returns: 19
The first 20 candidates: (4,2) (5,2) (7,2) (9,5) (0,4) (9,7) (0,8) (6,6) (1,4) (6,3) (6,7) (3,6) (7,10) (2,0) (9,2) (0,6) (2,0) (5,10) (3,6) (7,7) Candidates 0-4 get accepted. Candidate 5 gets rejected. Towers at (9,5) and (9,7) both need to be anchored horizontally, as they are in the last row. However, they both want to use (9,6) for one of their anchors, which isn't allowed. Candidates 6-14 all get accepted. Candidate 15, the square (0,6), gets rejected. The issue is similar to the previous one. Candidate 16 gets ignored as a duplicate of an already accepted square. Candidate 17 gets accepted. Candidate 18 gets ignored. Candidate 19 gets rejected. The situation when processing candidate 19 is shown below: candidate 19 is '#', previously accepted candidates are '*' and empty squares are '.'. ....*...*... ....*....... *........... ......*..... ..*......... ..*.......*. ...*..**.... ..*....#..*. ............ ..*..*......
25
20
1
400
Returns: 696
1
500
24255
400
Returns: 662
10
500
24252
40
Returns: 487
100000
100000
2422
4
Returns: -1
5345
1735
2
1
Returns: 29686
3534
3845
11
4
Returns: 45995
7100
1634
24
4
Returns: 44589
2304
15624
50000
4
Returns: -1
4431
8579
50000
4
Returns: -1
502
1899
50000
4
Returns: 9826
24315
3
50000
2
Returns: 227
137
26
3562
38
Returns: 491
6167
11
50000
4
Returns: 683
39986
13976
50000
4
Returns: -1
2212
53228
50000
2
Returns: -1
112
49357
50000
1
Returns: 12199
37
6
222
188
Returns: 318
3
1069
3207
62
Returns: 400
3815
43
50000
4
Returns: 1892
19
27
513
389
Returns: 691
483
1
483
414
Returns: 686
2132
277
50000
4
Returns: 5693
127
5
635
24
Returns: 133
3
8
24
28
Returns: 49
166
1130
50000
4
Returns: 2716
3288
4
13152
14
Returns: 415
1
1013
1013
197
Returns: 453
3404
61
50000
4
Returns: 2097
31474
268
50000
1
Returns: 14829
503
4656
50000
3
Returns: 17480
11548
4
46192
3
Returns: 277
9
2253
20277
9
Returns: 434
6290
363
50000
4
Returns: 16956
26198
30816
50000
4
Returns: -1
31
1
31
267
Returns: 380
24829
616
50000
4
Returns: -1
59
2042
50000
4
Returns: 1839
1071
4446
50000
4
Returns: 21053
7
2549
17843
11
Returns: 479
7
6778
47446
4
Returns: 755
1837
5
9185
21
Returns: 496
12
2169
26028
7
Returns: 766
628
693
50000
4
Returns: 5412
7979
13
50000
4
Returns: 819
174
5
870
229
Returns: 511
4
28
112
500
Returns: 741
2417
1232
50000
4
Returns: 17482
1210
1902
50000
4
Returns: 14247
105
3
315
396
Returns: 620
13
1407
18291
9
Returns: 550
178
1314
50000
1
Returns: 3136
3
432
1296
154
Returns: 444
3566
22
50000
4
Returns: 1125
818
4086
50000
4
Returns: 20250
197
4575
50000
2
Returns: 6871
3436
7
24052
8
Returns: 665
45
236
10620
18
Returns: 694
518
8
4144
48
Returns: 465
1844
3
5532
1
Returns: 17
8
561
4488
44
Returns: 453
7897
75
50000
3
Returns: 4884
830
3
2490
43
Returns: 272
6
14
84
500
Returns: 694
542
23
12466
16
Returns: 743
28
331
9268
21
Returns: 803
4
19
76
292
Returns: 410
41
158
6478
20
Returns: 583
3284
915
50000
4
Returns: 17812
30
4926
50000
4
Returns: 1180
3441
2703
50000
4
Returns: 42618
1326
387
50000
1
Returns: 1780
86
763
50000
2
Returns: 1465
10
46
460
434
Returns: 718
138
3606
50000
2
Returns: 5704
115
3
345
500
Returns: 779
304
22
6688
28
Returns: 567
12
14
168
500
Returns: 720
768
968
50000
4
Returns: 8907
21
431
9051
22
Returns: 616
724
3
2172
92
Returns: 426
7
14
98
500
Returns: 681
5
150
750
162
Returns: 393
2534
6
15204
13
Returns: 509
9
143
1287
98
Returns: 362
286
6
1716
116
Returns: 480
838
94
50000
4
Returns: 2114
107
1787
50000
4
Returns: 3039
20
20
1
500
Returns: 773
40
50
1
100
Returns: 502
50
50
12345
50
Returns: 388