11362 – Phone List

A string prefix search problem.
Given a list of strings, determine whether any of them is a prefix of another. A brute-force O(n2) solution will get time limit exceeded.
If we sort the strings lexicographically, the problem gets easier. In the sorted string list s, if any string s[i] is a prefix of s[i+k], then s[i] is a prefix of all strings from s[i+1] to s[i+k]. So, we only need to compare each consecutive strings. Now, our algorithm has complexity O(n).
Java implementation with rank 752:

import java.util.*;

public class Main {
	public static void main(String[] args) {
		ArrayList<String> lst = new ArrayList<String>();
		int t, n, i;
		Scanner s = new Scanner(System.in);
		t = s.nextInt();
		while (t-- > 0) {
			// input
			lst.clear();
			n = s.nextInt();
			s.nextLine();
			for (i = 0; i < n; i++)
				lst.add(s.nextLine().trim());
			// solve
			Collections.sort(lst);
			for (i = 1; i < n; i++)
				if (lst.get(i).indexOf(lst.get(i - 1)) == 0)
					break;
			if (i == n)	System.out.println("YES");
			else		System.out.println("NO");
		}
	}
}

Another variant of the solution (same algorithm though) is to handle the phones as pairs of integers (the first is the phone number itself and the second is a mask that tells which digits of it are actually set). For prefix check, I utilized bit-wise operations. C++ implementation with rank 13:

#include <cstdio>
#include <algorithm>
using namespace std;

bool cmp(pair<long long, long long> i, pair<long long, long long> j) {
	return (i.first < j.first);
}

char ans[2][8] = { "NO", "YES" };
int nCase, nPhones;
pair<long long, long long> phones[10002];
char line[11];

int main() {
	int i, j;
	scanf("%d", &nCase);
	while (nCase--) {
		// input
		scanf("%d", &nPhones);
		for (i = 0; i < nPhones; ++i) {
			scanf("%s", line);
			phones[i].first = 0;
			phones[i].second = 0;
			for (j = 0; line[j]; ++j) {
				phones[i].first = (phones[i].first << 4) | (line[j] - '0' + 1);
				phones[i].second = (phones[i].second << 4) | (0xF);
			}
			while (!(phones[i].first & 0xF000000000)) {
				phones[i].first <<= 4;
				phones[i].second <<= 4;
			}
		}
		// solve
		sort(phones, phones + nPhones, cmp);
		for (i = 1; i < nPhones; ++i)
			if ((phones[i].first & phones[i - 1].second) == phones[i - 1].first)
				break;
		printf("%s\n", ans[i == nPhones]);
	}
	return 0;
}

101A – Homework

A greedy problem.
You’re given a string and allowed to remove up to m characters from it. Your goal is to choose the removed characters such that the number of distinct characters in the remaining string is minimized.
Simply, on taking input, calculate the frequency of each character and sort the frequencies. Characters with less frequency are candidate to removal more than any other ones. That’s the key point and the rest is straight-forward.
Java implementation:

import java.util.*;

public class Main {
	int m;
	static LetterAndFreq[] lst = new LetterAndFreq[26];
	static HashSet<Character> map = new HashSet<Character>();

	public static void main(String[] args) {
		// init
		for (int i = 0; i < lst.length; i++)
			lst[i] = new LetterAndFreq((char) ('a' + i), 0);
		Scanner s = new Scanner(System.in);
		// input
		String line = s.nextLine();
		int m = s.nextInt();
		for (int i = 0; i < line.length(); i++) {
			lst[line.charAt(i) - 'a'].f++;
			map.add(line.charAt(i));
		}
		// solve
		Arrays.sort(lst);
		for (int i = 0; map.size() > 0 && lst[i].f <= m; i++)
			if (lst[i].f != 0) {
				m -= lst[i].f;
				map.remove(lst[i].l);
			}
		// print
		System.out.println(map.size());
		for (int i = 0; i < line.length(); i++)
			if (map.contains(line.charAt(i)))
				System.out.print(line.charAt(i));
		System.out.println();
	}

	static class LetterAndFreq implements Comparable<LetterAndFreq> {
		char l; int f;
		public LetterAndFreq(char i, int j) { l = i; f = j; }
		public int compareTo(LetterAndFreq o) { return f - o.f; }
	}

}

195 – Anagram

A string permutation problem.
If you use STL’s next_permutation, it’ll take you no time to code. The most part will be done on the character sort conditions. Here:

#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int nCase;
string word;

bool mySort(char x, char y) {
	if (tolower(x) - tolower(y))
		return tolower(x) < tolower(y);
	else
		return x < y;
}

int main() {
	cin >> nCase;
	while (nCase--) {
		cin >> word;
		sort(word.begin(), word.end(), mySort);
		do
			cout << word << endl;
		while (next_permutation(word.begin(), word.end(), mySort));
	}
}

10150 – Doublets

A graph problem.
You have a start word (start) and you’re required to reach a target word (end). You can move between two words (vertices) if they’re doublets (edge). We need:

• An array (w) containing the words (vertices) in the dictionary. It can have a fixed size of 25143.
• A hash-map (wordToInt) that maps each of these words to its position in the array. Now, we can represent each word as an integer and all our paths and queues will consist of integers.
• An adjacency list (adjList) that represents our graph. Given a word (a word’s position) the list returns its doublets (which are all integers now). However, we won’t build the graph before the search. If you do so, you’ll get TLE because this has complexity O(l*n2). The graph should initially be disconnected. Only as we reach a vertex, do we connect its edges.
• The previous point requires that we keep track of vertices that have been fully connected already. So, we’ll have a boolean array (adjListGood). And wordToInt comes in handy, again.
• To do our BFS we need an array (parent) that tells each vertex’s parent as we traverse the graph.

Et voilà! C++ implementation with rank 354:

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;

#define L (17)
#define N (25143 + 1)

int nW = -1;
char w[N][L];
bool adjListGood[N];
vector<int> adjList[N];
int parent[N];
map<string, int> wordToInt;

bool areDoublets(int i, int j) {
	int d = 0;
	for (unsigned int k = 0; k < strlen(w[i]); ++k)
		d += (w[i][k] == w[j][k] ? 0 : 1);
	return d == 1;
}

int bfs(int s, int e) {
	int p, newP;
	queue<int> q;
	q.push(s);
	parent[s] = -9;
	while (q.size()) {
		p = q.front();
		q.pop();
		// end
		if (p == e) {
			return e;
		}
		// adjList good
		else if (adjListGood[p]) {
			// push
			for (unsigned int i = 0; i < adjList[p].size(); ++i)
				if (parent[newP = adjList[p][i]] == -1) {
					parent[newP] = p;
					q.push(newP);
				}
		}
		// need to build adjList
		else {
			// build
			for (int i = 0; i < nW; ++i)
				if (strlen(w[p]) == strlen(w[i]) && areDoublets(p, i))
					adjList[p].insert(adjList[p].end(), i);
			adjListGood[p] = true;
			// push
			for (unsigned int i = 0; i < adjList[p].size(); ++i)
				if (parent[newP = adjList[p][i]] == -1) {
					parent[newP] = p;
					q.push(newP);
				}
		}
	}
	return -1;
}

int main() {
	int i;
	char line[L << 3], w1[L], w2[L];
	// dictionary
	while (gets(line) && sscanf(line, "%s", w[++nW]) == 1)
		wordToInt[w[nW]] = nW;
	// test cases
	bool caseOne = true;
	while (gets(line) && sscanf(line, "%s %s", w1, w2) == 2) {
		if (!caseOne)
			printf("\n");
		caseOne &= false;
		memset(parent, -1, sizeof(parent));
		if (strlen(w1) == strlen(w2)
				&& wordToInt.find(w1) != wordToInt.end() && wordToInt.find(w2) != wordToInt.end()
				&& (i = bfs(wordToInt[w2], wordToInt[w1])) != -1)
			do
				printf("%s\n", w[i]);
			while ((i = parent[i]) != -9);
		else
			printf("No solution.\n");
	}
	return 0;
}

10867 – Decode the tape

A simple ad-hoc string manipulation problem. You just need a little observation.
…
Each row of input is the ASCII representation of a character — ignoring ‘|’ and ‘.’ –. Simple enough!
My C++ code:

#include <iostream>
#include <map>
using namespace std;

#define N 1 << 16

int main() {
	string lineIn;
	while (getline(cin, lineIn)) {
		if (lineIn[0] == '_')
			continue;
		int i = 1;
		char out = 0;
		for (; lineIn[i] != '.'; ++i)
			out = (out << 1) | (lineIn[i] == 'o' ? 1 : 0);
		for (++i; lineIn[i] != '|'; ++i)
			out = (out << 1) | (lineIn[i] == 'o' ? 1 : 0);
		cout << out;
	}
	return 0;
}

Rank 2179.