Hi all, Atcoder Beginner Contest 171 was today. I wrote an unofficial English editorial. Hope it helps!

A: αlphabet

We simply write an if statement.

Runtime: $$$\mathcal{O}(1)$$$.

char x = in.next().charAt(0);

if (x >= 'A' && x <= 'Z')
    out.println("A");
else
    out.println("a");

B: Mix Juice

We want to buy the cheapest fruits, so we can sort the array and then pick the first $$$K$$$ fruits.

Runtime: $$$\mathcal{O}(N \log N)$$$.

int n = in.nextInt(), k = in.nextInt();
int[] p = in.readIntArray(n);

Util.safeSort(p); // this shuffles and sorts to avoid hacks

long answer = 0;
for (int i = 0; i < k; i++) {
   answer += p[i];
}

out.println(answer);

C: One Quadrillion and One Dalmatians

The trick is to look at the letters starting from the end of the names. You can see the last letter repeats every $$$26$$$ names. The second-to-last letter repeats every $$$26^2$$$ names (after you skip the first $$$26$$$ names that are too short). The third-to-last letter repeats every $$$26^3$$$ names (after you skip the first $$$26 + 26^2$$$ names that are too short).

This gives rise to a solution where we extract the last letter first by setting $$$N = N-1$$$, then looking at the value modulo $$$26$$$. Then to shift everything over, we divide by $$$26$$$, and repeat the whole process as necessary. The subtraction of $$$1$$$ at the beginning of the loop accounts for skipping all the necessary shorter strings.

Take care to reverse the string.

Runtime: $$$\mathcal{O}(\log_{26} N)$$$, or equivalently $$$\mathcal{O}(L)$$$ where $$$L$$$ is the length of the answer.

long n = in.nextLong();

StringBuilder answer = new StringBuilder();
while (n > 0) {
    n--;
    answer.append((char) ('a' + n % 26));
    n /= 26;
}

out.println(answer.reverse());

D: Replacing

A few quick observations:

• The order of $$$A$$$ doesn't matter.
• Once two elements of $$$A$$$ are equal, they will never diverge.

This motivates us to think about the counts of each element in $$$A$$$, rather than the elements themselves. Because the elements are small (less than $$$10^5$$$), we can easily store the counts in an array.

In order to process a query, we move everything from $$$B_i$$$ to $$$C_i$$$ and update our sum appropriately. This means adding $$$\mathrm{count}[B_i]$$$ to $$$\mathrm{count}[C_i]$$$ and setting $$$\mathrm{count}[B_i]$$$ to zero, as well as changing our running sum by $$$\mathrm{count}[B_i] (C_i - B_i)$$$.

Take care to use $$$\mathrm{count}[B_i]$$$ before you set it to zero.

Runtime: $$$\mathcal{O}(N + Q + M)$$$, where $$$M = 10^5$$$, the largest possible element value.

int n = in.nextInt();
int[] a = in.readIntArray(n);
long sum = 0;

long[] count = new long[MAX];
for (int i : a) {
    sum += i;
    count[i]++;
}

int q = in.nextInt();
for (int query = 0; query < q; query++) {
    int b = in.nextInt(), c = in.nextInt();

    sum -= count[b] * b;
    sum += count[b] * c;
    count[c] += count[b];
    count[b] = 0;

    out.println(sum);
}

E: Red Scarf

The key observation (and super useful fact about xor in general) is that $$$x \oplus x = 0$$$ for any $$$x$$$. This means a lot cancels out.

Let $$$c_i$$$ be a valid original array of cats (so, this is our answer we want to output).

Let's first rewrite $$$a_i$$$ using our observation above. Let $$$X$$$ be the xor of all elements in $$$c$$$. Then $$$a_i = X \oplus c_i$$$.

So, we can simply compute $$$c_i = X \oplus a_i$$$ and we are done.

Runtime: $$$\mathcal{O}(N)$$$.

int n = in.nextInt();
int[] a = in.readIntArray(n);

int xor = 0;
for (int x : a)
    xor ^= x;

int[] answer = new int[n];
for (int i = 0; i < n; i++) {
    answer[i] = xor ^ a[i];
}

out.println(Util.join(answer));

F: Strivore

Let's consider the end result of this process and what it can look like. It will be a string of length $$$N = K + |S|$$$ that contains $$$S$$$ as a subsequence.

We'll use $$$Z = 26$$$ for readability.

In order to count these, let's first note that there are $$$Z^N$$$ total strings of length $$$N$$$, and we want to remove all the strings that don't contain $$$S$$$ as a subsequence (this is a bit easier than counting the strings that do contain $$$S$$$, because a string could contain $$$S$$$ multiple times and be overcounted).

Let's consider the length of the maximum prefix of $$$S$$$ that's a subsequence of our string $$$T$$$. Going from left to right within $$$T$$$, we can check when this increases -- it increases from $$$X$$$ to $$$X+1$$$ when our current character is $$$S_{X+1}$$$. In order for it to not increase, we need our current character to not be $$$S_{X+1}$$$.

So let's say this length is exactly $$$M$$$. Then it must have increased from $$$0$$$ to $$$M$$$ (one at a time, of course), so we pick $$$M$$$ indices in $$$T$$$ to be the indices where it increases, and those have only one choice of character. The remaining characters have $$$Z-1$$$ choices. So for length $$$M$$$, we have $$$\binom{N}{M} (Z-1)^{N-M}$$$ possibilities.

In order to not contain $$$S$$$ as a subsequence, $$$M$$$ can be anything from $$$0$$$ to $$$|S| - 1$$$. Now, recall these are the strings we don't want, so we subtract them from the total.

Therefore, our final answer is $$$\displaystyle Z^N - \left[\sum_{M=0}^{|S|-1} \binom{N}{M} (Z-1)^{N-M}\right]$$$.

Runtime: $$$\mathcal{O}(K + |S|)$$$.

final int Z = 26;
int k = in.nextInt();
char[] s = in.next().toCharArray();
int l = s.length;
int n = k + l;

// this is all just some precomputation, so we can
// get powers and nCr in O(1) later
mod.fact(n);
long[] powers = new long[n + 1];
powers[0] = 1;
for (int i = 0; i + 1 < powers.length; i++) {
    powers[i + 1] = mod.mult(powers[i], Z - 1);
}

long answer = mod.pow(Z, n);
for (int match = 0; match < l; match++) {
    long val = mod.mult(powers[n - match], mod.ncr(n, match));
    answer = mod.subtract(answer, val);
}

out.println(answer);

You can see my submissions here as well, if you prefer that to reading the code in the blog.

Thanks for reading! Let me know if you have any questions or feedback for me.