TimedPassword | Topcoder Archive

Problem Statement

It is a common issue in big companies that computer users tend to use easy and simple passwords like "abcdef", common words like "house" or "tree" or simply their usernames. For that reason, companies tend to write policies (and enforce them through automated programs) that specify certain rules that must be followed when setting a new password.

Even with those measures, there are always some vulnerabilities in software that allow crackers to get passwords without using brute force, so we decided to patent a new way to discover if a password was written by the intended user. After a user types his password many times, he will start repeating the same timing pattern when typing the password. To verify if the typed password is correct, the system takes into account the following considerations:

If the user's input is not the same as the correct password, then the password is invalid.
If the timing error exceeds maxError then the password is invalid.
In any other case the password is considered valid and access is granted.

The timing error must be calculated only if the user's input is the same as the correct password. To calculate it, the system accumulates the error for each character typed after the first. The timing error of the k-th typed character is the absolute difference between inputTime[k]-inputTime[k-1] and correctTime[k]-correctTime[k-1].

Create a method valid that given the input password, the inputTime, the correct password, the correctTime and the maxError allowed, returns the String "ACCESS GRANTED" if the password is correct and the timing error does not exceed maxError, and returns "ACCESS DENIED" in any other case (all quotes for clarity).

Definition

Class:: TimedPassword
Method:: valid
Parameters:: String, int[], String, int[], int
Returns:: String
Method signature:: String valid(String input, int[] inputTime, String correct, int[] correctTime, int maxError)
(be sure your method is public)

Constraints

input will contain between 1 and 50 characters, inclusive.
Each character of input will be a lowercase letter ('a'-'z').
inputTime will contain the same number of elements as the number of characters in input.
Each element of inputTime will be between 0 and 5000, inclusive.
All elements of inputTime will be strictly increasing.
The first element of inputTime will be 0.
correct will contain between 1 and 50 characters, inclusive.
Each character of correct will be an lowercase letter ('a'-'z').
correctTime will contain the same number of elements as the number of characters in correct.
Each element of correctTime will be between 0 and 5000, inclusive.
All elements of correctTime will be strictly increasing.
The first element of correctTime will be 0.
maxError will be between 0 and 50000, inclusive.

Examples

```
"apple"
```
```
{0, 3, 4, 7, 8}
```
```
"appel"
```
```
{0, 3, 4, 7, 8}
```
```
10
```
```
Returns: "ACCESS DENIED"
```
The password was typed using the same pattern as the correct password, but the last two characters were swapped while typing the input.
```
"apple"
```
```
{0, 3, 4, 7, 8}
```
```
"apple"
```
```
{0, 3, 4, 7, 8}
```
```
10
```
```
Returns: "ACCESS GRANTED"
```
This time the same pattern was used and the characters were typed correctly.
```
"orange"
```
```
{0, 15, 43, 74, 83, 94}
```
```
"orange"
```
```
{0, 13, 42, 70, 79, 91}
```
```
10
```
```
Returns: "ACCESS GRANTED"
```
The typed password is correct, and the timing error for each character is: 'r' --> 2 'a' --> 1 'n' --> 3 'g' --> 0 'e' --> 1 For a total error of 7. The user is granted access because it is not greater than the maximum error allowed.
```
"orange"
```
```
{0, 15, 43, 74, 83, 94}
```
```
"orange"
```
```
{0, 13, 42, 70, 79, 91}
```
```
5
```
```
Returns: "ACCESS DENIED"
```
This time, the timing error (7) is greater than the maximum error allowed (5), so the user is denied access.

"timer"

{0, 10, 21, 43, 59}

"knowledge"

{0, 13, 23, 45, 72, 102, 415, 513, 598}

Returns: "ACCESS DENIED"

The passwords are different, so access is denied.

"knowledge"

{0, 13, 23, 45, 72, 102, 415, 513, 598}

"timer"

{0, 10, 21, 43, 59}

Returns: "ACCESS DENIED"

The passwords are different, so access is denied.

```
"water"
```
```
{0, 10, 20, 30, 40}
```
```
"water"
```
```
{0, 9, 18, 27, 36}
```
```
4
```
```
Returns: "ACCESS GRANTED"
```
Remember that access is granted when the timing error is exactly equal to the maximum error allowed.

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)2024, Topcoder, Inc. All rights reserved.