118D – Caesar’s Legions

A Dynamic Programming problem.
You’re trying to find the number of permutations of footmen/horsemen that match the given criterion. While you’re permuting, some problems are revisited. That’s when DP comes in handy:

• State S(n1, n2, k1, k2) – You’ve placed n1 footmen and n2 horsemen. The previous soldier is either a part of k1 consecutive footmen or k2 consecutive horsemen.
• Transition S(n1, n2, k1, k2) = S(n1 + 1, n2, k1 + 1, 0) + S(n1, n2 + 1, 0, k2 + 1) – You can either place a footman — which increases the number of consecutive footmen by one and resets the number of consecutive horsemen k2 — or a horseman.

Caution!

• Don’t forget the modulo 10⁸.

C++ implementation but with values decreasing instead of increasing:

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

#define N 128
#define K 16
#define M 100000000

int nWays[N][N][K][K];
int N1, N2, K1, K2;

long long getNWays(int n1, int n2, int k1, int k2) {
	if (n1 < 0 || n2 < 0 || k1 < 0 || k2 < 0)
		return 0;
	if(n1 == 0 && n2 == 0)
		return 1;
	if (nWays[n1][n2][k1][k2] != -1)
		return nWays[n1][n2][k1][k2];
	return nWays[n1][n2][k1][k2] =
			(getNWays(n1 - 1, n2, k1 - 1, K2) + getNWays(n1, n2 - 1, K1, k2 - 1)) % M;
}

int main() {
	memset(nWays, -1, sizeof nWays);
	cin >> N1 >> N2 >> K1 >> K2;
	cout << getNWays(N1, N2, K1, K2) << 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; }
	}

}

114B – PFAST Inc.

A brute-force problem with some bit-wise tricks.
You have a list of names. Some of them don’t get along. Find the largest sought team. Make sure your output is sorted!
The basic idea is that you generate all possible teams and exclude the ones that have “bad combinations”. All of this is done bit-wise. As you see, the maximum team has 16 members so each combination can be represented by an integer. Each set bit of that integer indicates that a certain member is a part of that team. An example:

	n = 3;
	names = {"x", "y", "z"}
	team = 5	// 510 = 1012 which means "x", "z" are in the team

So, we need:

• An array (names) that holds all the names. This array must be sorted for the output to be easy.
• A hash map (nameToInt) that maps each name to an integer for simplicity’s sake. Bit-wise tweaks are now easier.
• An integer array (forbidden) that holds forbidden combinations.
• A method (nSetBits(i)) that counts the number of set bits in an integer / the number of members in a team.
• Read the names, sort them, give each one a representative integer, read forbidden combinations and store them, generate all possible combinations, exclude the bad ones and maximize the number of members.

C++ implementation:

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

#define N (16 + 1)
#define L (10 + 1)

map<string, int> nameToInt;
string names[N];
int n, m, forbidden[N * N], bestTeam;
string name;

int nSetBits(int i) {
	i = i - ((i >> 1) & 0x55555555);
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
	int i, j;
	cin >> n >> m;
	// names sort & map
	for (i = 0; i < n; names[i] = name, ++i)
		cin >> name;
	sort(names, names + n);
	for (i = 0; i < n; ++i)
		nameToInt[names[i]] = i;
	// forbidden teams
	for (i = 0; i < m; ++i) {
		forbidden[i] = 0;
		cin >> name;
		forbidden[i] |= 1 << nameToInt[name];
		cin >> name;
		forbidden[i] |= 1 << nameToInt[name];
	}
	// genearate all possible and maximize
	for (int i = (1 << n) - 1; i > 0; --i) {
		for (j = 0; j < m; ++j)
			if ((forbidden[j] & i) == forbidden[j])
				break;
		if (j == m && nSetBits(bestTeam) < nSetBits(i))
			bestTeam = i;
	}
	// print
	cout << nSetBits(bestTeam) << endl;
	for (i = 0; i < n; ++i)
		if (bestTeam & (1 << i))
			cout << names[i] << endl;
	return 0;
}

199C – About Bacteria

Let’s follow the straight-forward approach:

• Start with one bacteria. Calculate the growth after n seconds.
• Start with t bacteria. Keep growing until you reach the amount in the first step.
• The time you waited for in the previous step is the solution.

The amount of bacteria for the next second givencurrent bacteria goes as follows:

So, ifis the amount afterseconds starting withbacteria:







So, starting with 1 bacteria and after n seconds:

And starting with t bacteria after m seconds:

As we see, the computations are exponential and won’t fit into integer arithmetic. So, we can’t calculate which is the first step of the solution. The straight-forward solution won’t work. We have to find another way around.
Let’s continue with the math. For bothto be equal, m has to be the solution:


Subtract b then divide by k

Subtract b then divide by k

Keep going but remember that n > m:




So, for to be equal:

• We need to start with 1 bacteria. Wait until it grows to t bacteria ().
• The time we waited is n – m. So the solution m is n – (n – m).

The computations aren’t that large this time. C++ implementation:

#include <iostream>
using namespace std;

typedef unsigned long long int64;

int main(void) {
	int64 k, b, n, t, m, zm = 1;
	cin >> k >> b >> n >> t;
	for (m = 0; m < n && zm < t; ++m)
		zm = k * zm + b;
	if (zm > t)
		m--;
	cout << n - m << endl;
	return 0;
}

199A – Hexadecimal’s theorem

The basic approach is:


Hence, if we generate the list of all Fibonacci numbers up to (input bound) the answer is just a binary-search-away.
C++ implementation:

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

typedef unsigned long long int64;
#define N 48

int64 fib[N];
int nFib;

int64 generate() {
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i < N; ++i)
		fib[i] = fib[i - 1] + fib[i - 2];
	return fib[N - 1];
}

int main(void) {
	generate();
	int64 n;
	cin >> n;
	int64 * p = upper_bound(fib, fib + N, n) - 1;
	if (p - 4 >= fib)
		cout << *(p - 4) << " " << *(p - 3) << " " << *(p - 1) << endl;
	else
		cout << "0 0 " << *p << endl;
	return EXIT_SUCCESS;
}

There’s an other naive (totally valid) solution. You noticed that 0 is a Fibonacci.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int n;
	scanf("%d", &n);
	printf("0 0 %d\n", n);
	return EXIT_SUCCESS;
}

Ironic!!!