Connection Status:
Competition Arena > Lasso

Lasso

SRM 847 · 2023-06-22 · by misof

SRM 847 · 2023-06-22 · by misof · Graph Theory, Greedy, Simple Math
Class Name: Lasso
Return Type: double
Method Name: lasso
Arg Types: (int, int, int, int, int, int)
Problem Statement

Problem Statement

There is a farm. The farm is an infinite horizontal chessboard. Cells of the chessboard have integer coordinates (r, c).

There is a corral for the horses. The corral is the rectangle consisting of all cells (r, c) such that 0 <= r <= R and 0 <= c <= C.

There are horses inside the corral. Currently, each cell (r, c) such that R1 <= r <= R2 and C1 <= c <= C2 contains one horse.

The horses are completely independent of each other. I.e., arbitrarily many horses may share the same cell without influencing each other.


All horses have decided to escape the corral.

There is only one cowboy around. His job is to catch all horses before any one of them gets out.

The cowboy can repeatedly use his lasso to catch and tie up a horse. This takes L seconds, regardless of where the horse is located. (L may be non-integer.) Once a horse has been tied up, it can no longer escape.


We can view the entire commotion as a turn-based process:

  • The process starts at time 0.
  • At positive integer multiples of L (i.e., at times L, 2L, 3L, ...) the cowboy gets his turn and catches one of the horses. The cowboy gets to choose which horse he catches.
  • At positive integer times (i.e., at times 1, 2, 3, ...) the horses get their turn. As you might expect, each horse moves like a chess knight (see Notes).
  • During each of the horses' turns each horse that still hasn't been caught makes exactly one move. Naturally, each horse tries to leave the corral as quickly as possible. A horse has escaped if its move ends on a cell outside the corral.
  • If the cowboy and the horses should have their turns at the exact same moment in time, the cowboy's action is evaluated first.

Find and return the largest positive real L such that the cowboy can still guarantee (by using a good strategy) that he will catch all the horses before any one of them can escape.

Notes

  • In a single move, a chess knight always jumps in such a way that one of its coordinates changes by 2 and the other changes by 1. For example, a knight at (4, 7) may jump to (6, 8), (6, 6), (3, 9), (3, 5), or four other cells.
  • Your return value may have an absolute or a relative error at most 10^(-9).

Constraints

  • 0 <= R1 <= R2 <= R <= 1000.
  • 0 <= C1 <= C2 <= C <= 1000.
Examples
0)
0
0
0
0
0
0
Returns: 1.0

The corral is a single cell with a single horse. The cowboy must act before the horse to catch it.

1)
4
4
2
2
2
2
Returns: 2.0

The corral is a 5x5 cell square with a single horse on the middle cell. The horse will escape if it gets a second turn, so the cowboy must act before that.

2)
3
2
0
0
2
1
Returns: 0.16666666666666666

The corral is a 4x3 rectangle. In the corral there are six horses forming a 3x2 rectangle. Each horse can escape the corral in a single move, so the cowboy must catch all of them before they get their first move.

3)
4
4
2
2
2
3
Returns: 1.0

Here the cowboy's strategy matters. He should catch the horse that starts at (2, 3) before the horse that starts at (2, 2). In the slowest valid solution the cowboy catches the first horse at time 1, then also at time 1 the second horse moves - e.g., to (3, 4) - and then at time 2 the cowboy catches that second horse just before it can escape the corral.

4)
4
4
2
2
2
4
Returns: 0.5

Submissions are judged against all 153 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Lasso with a public method double lasso(int R, int C, int R1, int C1, int R2, int C2) · 153 test cases · 2 s / 256 MB per case

Submitting as anonymous