patternjavaMinor

Equivalent passwords ACPC 2014

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

2014passwordsacpcequivalent

Problem

I am preparing for ACM-TCPC (Tunisia). So I started solving problems from past ACM-ACPC versions. But I got stuck in the Problem I from 2014.

The problem consists of finding the number of non-equivalent passwords in list of passwords. Two passwords, A and B, are equivalent if len(A) == len(B) and |A[i] -B[i]| is the same for i in [0..len(A)] (len is the length of the password and |x| is the absolute value of x).

Examples:

Input:

000
111
222

Output:

Input:

Output:

Input

43434
54545
45454

Output:

My code works fine and it solves the Judges I/O, However it takes a plentiful amount of time!

The code I wrote:

```
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Password {
public static void main(String[] args){
String[] str_tab ;
HashMap hm = null;
List l = null;
try {
int[] tab = null;
BufferedReader br = new BufferedReader(new FileReader(new File("./password.in")));
PrintWriter wr = new PrintWriter("./passwrd.out");
int T = Integer.parseInt(br.readLine().toString());
for (int i = 0; i ();
int N = Integer.parseInt(br.readLine().toString());
for (int j = 0; j l){
List ls = new ArrayList();
ls.add(l.get(0));
int j= 0;
for (int i = 1; i < l.size(); i++) {
j = 0;
while(j<ls.size() && !isEq(l.get(i),ls.get(j))) j++;
if(j == ls.size()) ls.add(l.get(i));
}

return ls.size();
}
public static boolean isEq(String p1, String p2){
if(p1.length() != p2.length()) return false;
int diff = Math.abs(p1.charAt(0) - p2.charAt(0));
for (int i = 1; i <p1.length(); i++) {

if(Math.abs(p1.charAt(i) - p2.charAt(i)) != diff){
return false;
}
}

Solution

Lint

str_tab, hm, and tab are all unused variables.

In br.readLine().toString(), the .toString() is superfluous, as br.readLine() already returns a string.

In main(), the

for (int i = 0; i

Use try-with-resources for AutoCloseable resources.

Using Scanner instead of BufferedReader would let you not have to deal with IOException.

Passing a Scanner instead of a List lets each test case work on the fly as the input streams in.

solve() doesn't really "solve". I'd pick a more descriptive name. Here, I've instantiated an object to represent each test case. (I think that a good solution requires more state than I would like to pack into a single function.) If the challenge had not required the program to be named Password, I would have just used DistinctPasswordCounter as the name of the class, and eliminated the inner class.




Strategy

Your

solve()

 compares each password with every previously seen password, which makes it O(N2).  It's not surprising that the solution is slow, considering that N is large (up to 105).

Consider a different strategy: when you encounter a password, also note all possible variants of it.  For example, if the password

31415 appears, then also register the variants 20304, 20306, 20324, 20326

, etc.

How many variants would we be talking about?  Given an original password, such as

31415

, there would be…

31415 itself




the ±1 variants:


$${2 \choose 4}{0 \choose 2}{3 \choose 5}{0 \choose 2}{4 \choose 6}$$
… of which there are 25:

20304, 20306, 20324, 20326, 20504, 20506, 20524, 20526, 22304, 22306, 22324, 22326, 22504, 22506, 22524, 22526, 40304, 40306, 40324, 40326, 40504, 40506, 40524, 40526, 42304, 42306, 42324, 42326, 42504, 42506, 42524, 42526

.

the ±2 variants:


$${1 \choose 5}\left(3\right){2 \choose 6}\left(3\right){3 \choose 7}$$
… of which there are 23:

13233, 13237, 13633, 13637, 53233, 53237, 53633, 53637

.

the ±3 variants:


$${0 \choose 6}\left(4\right){1 \choose 7}\left(4\right){2 \choose 8}$$
… of which there are 23:

04142, 04148, 04742, 04748, 64142, 64148, 64742, 64748

.

the ±4 variants:


$$\left(7\right)\left(5\right){0 \choose 8}\left(5\right){1 \choose 9}$$
… of which there are 22:

75051, 75059, 75851, 75859

.

the ±5 variants:


$$\left(8\right)\left(6\right)\left(9\right)\left(6\right)\left(0\right)$$
… of which there is 1:

86960

.

In the worst case, a password like

44444 or 55555 would generate 1+32+32+32+32+1 = 130 entries. If you stick them all in a HashSet

 with O(1) insertion and lookup time, then the solution would be O(130 N), which is much better than O(N2) for N ≫ 130.

In practice, there will probably be much fewer than 130 variants.  For example,

31415

 has just 54 variants.  Passwords that are shorter or that have a wide distribution of digits would have fewer variants.  Passwords that are equivalent to another password would generate no variants at all.  (For large N, the proportion of passwords that are equivalent to an existing password should rise dramatically due to the Birthday Paradox.)

Suggested solution

``
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.HashSet;
import java.util.NoSuchElementException;

public class Password {

public static class DistinctPasswordCounter {
private final Scanner in;
private final HashSet seenPasswords;
private int n, distinctCount;

public DistinctPasswordCounter(Scanner in) {
this.in = in;
this.n = Integer.parseInt(in.nextLine());

// 100 is a rough estimate of the number of variants
// per password, based on (5 * Math.pow(2, maxLength)).
// For very large n, it could probably be tuned lower
// due to the Birthday Paradox.
this.seenPasswords = new HashSet<>(100 * this.n);
}

public int count() {
while (this.n --> 0) {
String password = this.in.nextLine();
if (this.seenPasswords.add(password)) {
// No variant of this password has been seen before
this.distinctCount++;
int variants = this.addVariants(password);
// System.err.printf("%3d variants of %s\n", variants + 1, password);
}
}
return this.distinctCount;
}

private int addVariants(String password) {
int diff = 0, variants = 0, v;
while (0 = password.length()) {
this.seenPasswords.add(password);
return 1;
}
char c1 = (char)(password.charAt(pos) - diff),
c2 = (char)(password.charAt(pos) + diff);
String head = password.substring(0, pos),
tail = password.substri

Code Snippets

public class Password {

    public static class DistinctPasswordCounter {
        public DistinctPasswordCounter(Scanner in) {
            this.in = in;
            this.n = Integer.parseInt(in.nextLine());
            …
        }

        public int count() {
            while (this.n --> 0) {
                …
            }
            return …;
        }
    }

    public static void main(String[] args)
            throws FileNotFoundException, NoSuchElementException {
        try (Scanner in = new Scanner(new File("password.in"));
             PrintWriter out = new PrintWriter("password.out")) {
            int t = Integer.parseInt(in.nextLine());
            for (int i = 1; i <= t; i++) {
                DistinctPasswordCounter counter = new DistinctPasswordCounter(in);
                out.printf("Case %d: %d\n", i, counter.count());
            }
        }
    }
}

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.HashSet;
import java.util.NoSuchElementException;

public class Password {

    public static class DistinctPasswordCounter {
        private final Scanner in;
        private final HashSet<String> seenPasswords;
        private int n, distinctCount;

        public DistinctPasswordCounter(Scanner in) {
            this.in = in;
            this.n = Integer.parseInt(in.nextLine());

            // 100 is a rough estimate of the number of variants
            // per password, based on (5 * Math.pow(2, maxLength)).
            // For very large n, it could probably be tuned lower
            // due to the Birthday Paradox.
            this.seenPasswords = new HashSet<>(100 * this.n);
        }

        public int count() {
            while (this.n --> 0) {
                String password = this.in.nextLine();
                if (this.seenPasswords.add(password)) {
                    // No variant of this password has been seen before
                    this.distinctCount++;
                    int variants = this.addVariants(password);
                    // System.err.printf("%3d variants of %s\n", variants + 1, password);
                }
            }
            return this.distinctCount;
        }

        private int addVariants(String password) {
            int diff = 0, variants = 0, v;
            while (0 < (v = this.addVariants(password, ++diff, 0))) {
                variants += v;
            }
            return variants;
        }

        private int addVariants(String password, int diff, int pos) {
            if (pos >= password.length()) {
                this.seenPasswords.add(password);
                return 1;
            }
            char c1 = (char)(password.charAt(pos) - diff),
                 c2 = (char)(password.charAt(pos) + diff);
            String head = password.substring(0, pos),
                   tail = password.substring(pos + 1);
            return (c1 < '0' ? 0 : this.addVariants(head + c1 + tail, diff, pos + 1)) +
                   (c2 > '9' ? 0 : this.addVariants(head + c2 + tail, diff, pos + 1));
        }
    }

    public static void main(String[] args)
            throws FileNotFoundException, NoSuchElementException {
        try (Scanner in = new Scanner(new File("password.in"));
             PrintWriter out = new PrintWriter("password.out")) {
            int t = Integer.parseInt(in.nextLine());
            for (int i = 1; i <= t; i++) {
                DistinctPasswordCounter counter = new DistinctPasswordCounter(in);
                out.printf("Case %d: %d\n", i, counter.count());
            }
        }
    }
}

Context

StackExchange Code Review Q#123462, answer score: 3

Revisions (0)

No revisions yet.