11516 – WiFi

Given a street (a straigt line), a set of houses (points on that line) and a number of wireless access points (not placed yet), find the minimum range required for the access points to cover all the houses.

A binary search solution:

• Given the houses’ positions and the ranges, we can find the required number of access points n'. It’s correct to calculate this using some greedy algorithm.
• If n' < n (we have extra access points), decrease the range. Otherwise, increase the range.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

const double eps = 10E-4;
vector<int> house;

int nPointReq(double d) {
	int n = 1;
	double covered = house[0] + d;
	for (size_t i = 0; i < house.size(); ++i)
		if (house[i] > covered)
			covered = house[i] + d, ++n;
	return n;
}

int main() {
	int nCase, nPoint, nHouse;
	cin >> nCase;
	cout.precision(1);
	while (nCase--) {
		// input
		cin >> nPoint >> nHouse;
		house.clear();
		for (int i = 0, d; i < nHouse; ++i)
			cin >> d, house.push_back(d);
		sort(house.begin(), house.end());
		// solve
		double lD = 0, mD, hD = house[house.size() - 1];
		do {
			mD = (hD + lD) / 2.0;
			if (nPointReq(mD) > nPoint)
				lD = mD;
			else
				hD = mD;
		} while (hD - lD > eps);
		cout << fixed << (round(mD * 10) / 20.0) << endl;
	}
	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; }
	}

}

11520 – Fill the Square

A brute-force problem.
For each empty cell in the grid, you’re trying to place a letter that doesn’t match any of its four neighbours. The solution is that for each empty space try the letters form ‘A’ to ‘Z’, and the first letter that matches the criterion is the correct one. This is a greedy –totally sufficient– solution.
C++ code with rank 341:

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

int dir[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

char grid[16][16];
int n;

int main() {
	int nCase;
	scanf("%d", &nCase);
	for (int caseI = 0; caseI < nCase; ++caseI) {
		// input
		scanf("%d", &n);
		for (int i = 0; i < n; ++i)
			scanf("%s", grid[i]);
		// solve
		for (int y = 0; y < n; ++y) {
			for (int x = 0; x < n; ++x)
				// for each cell
				if (grid[y][x] == '.') {
					char letter;
					for (letter = 'A'; letter <= 'Z'; ++letter) {
						int m;
						for (m = 0; m < 4; ++m)
							if (grid[y + dir[m][1]][x + dir[m][0]] == letter)
								break;
						if (m == 4)
							break;
					}
					grid[y][x] = letter;
				}
		}
		// output
		printf("Case %d:\n", caseI + 1);
		for (int i = 0; i < n; ++i)
			printf("%s\n", grid[i]);
	}
	return 0;
}

No array out of bounds exceptions in C++. I’ll stick with that!