Connection Status:
Competition Arena > PatternLock

PatternLock

SRM 632 - TCO14 Wildcard Sweep · 2014-08-25 · by dreamoon

SRM 632 - TCO14 Wildcard Sweep · 2014-08-25 · by dreamoon · Dynamic Programming
Class Name: PatternLock
Return Type: int
Method Name: solve
Arg Types: (int, int)
Problem Statement

Problem Statement

This problem is about a pattern lock similar to the one used on Android devices.

On the screen there is a set of nodes, placed onto vertices of a rectangular grid. (Android devices usually use a 3 times 3 grid, but we will use grids of different dimensions in this problem.) We will assign Cartesian coordinates to the nodes, starting with (0,0) in a corner.

To unlock the device, the user has to draw the correct pattern: a path that connects some of the nodes. Below we describe the properties of a valid pattern.

  • The pattern is a sequence of nodes.
  • There must be at least one node in the pattern.
  • Each node may only appear in the pattern at most once.
  • For any two consecutive nodes A and B in the pattern, each other node that lies on the straight line segment AB must occur in the pattern before A and B.

According to the last rule, (0,1)-(0,0)-(0,2) is a valid pattern: the segment (0,0)-(0,2) does contain another node (0,1) but that node was already used in the pattern. On the other hand, no valid pattern can start with the nodes (0,0) and (0,2).

You are given ints N and MOD. Alice's device has a grid of 2 times N nodes. (That is, the nodes have coordinates between (0,0) and (1,N-1), inclusive.) Alice wants to choose a pattern of length 2*N (i.e., the longest possible pattern). Let X be the number of different patterns she may choose. Return the value (X modulo MOD).

Notes

  • Two patterns are considered the same only if they contain nodes in exactly the same order.

Constraints

  • N will between 1 and 3500, inclusive.
  • MOD will between 2 and 1,000,000,007 (10^9+7), inclusive.
Examples
0)
1
12345667
Returns: 2

There are only two possible patterns: (0,0)-(1,0) and (1,0)-(0,0).

1)
2
324124124
Returns: 24

All 4! permutations of the 4 nodes give us valid patterns of length 4.

2)
3
5325352
Returns: 504

In this case some of the 6! possible permutations are illegal. For example, this is not a valid pattern: (0,0)-(0,2)-(0,1)-(1,0)-(1,2)-(1,1).

3)
500
1000000007
Returns: 286169049
4)
1
2
Returns: 0

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

Coding Area

Language: C++17 · define a public class PatternLock with a public method int solve(int N, int MOD) · 27 test cases · 2 s / 256 MB per case

Submitting as anonymous