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

A: Can't Wait for Holiday

We simply find the index in the week, and print $$$7-i$$$ (taking care to order the days correctly so Sunday gives us $$$7$$$ as the output).

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

String w = "SUNMONTUEWEDTHUFRISAT"; // this is sort of a bad way to do this
String s = in.next();
int i = w.indexOf(s) / 3;
out.println(7 - i);

B: ROT N

We can simply loop through the string and increment each character by $$$N$$$, taking care to subtract $$$26$$$ if we go past the end of the alphabet.

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

int n = in.nextInt();
char[] s = in.next().toCharArray();
for (int i = 0; i < s.length; i++) {
    s[i] += n;
    if (s[i] > 'Z')
        s[i] -= 26;
}
out.println(String.valueOf(s));

C: Buy an Integer

For a given length $$$L$$$, we can consider the maximum integer we can afford of that length (this is easy to calculate because given a fixed $$$d(N)$$$, the cost is monotonic in $$$N$$$). There are only a small number of possible lengths, so we may loop through them.

Note that if any number greater than $$$10^9$$$ is affordable, then $$$10^9$$$ is as well (since it has smaller-or-equal numeric value and length than any number greater than it).

Runtime: $$$\mathcal{O}(\log_{10} X)$$$.

long a = in.nextInt(), b = in.nextInt();
long x = in.nextLong();

long answer = 0;
for (int len = 1; len <= 18; len++) {
    long aBudget = x - b * len;
    long n = aBudget / a;
    if (String.valueOf(n).length() > len)
        continue;
    answer = Math.max(answer, n);
}
answer = Math.min(answer, 1000000000);

out.println(answer);

D: Coloring Edges on Tree

We can construct an optimal coloring by greedily assigning colors to edges while traversing the tree. Given a vertex $$$v$$$, we can assign colors $$$1$$$ through $$$\mathrm{deg}(v)$$$ to its unassigned incident edges (if one of them is already assigned, we leave it as-is). The final answer for total colors is $$$\mathrm{max}_v(\mathrm{deg}(v))$$$.

I implemented this using a BFS through the tree. When visiting a node, at most one of its edges is already assigned (the one we just came from, if we aren't at the root), so we simply skip this one and note that we can't use its color for another edge on this node.

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

int n = in.nextInt();
List<Integer>[] adj = new List[n];
for (int i = 0; i < n; i++)
    adj[i] = new ArrayList<>();
HashMap<Pair<Integer, Integer>, Integer> edgeIndex = new HashMap<>();
for (int i = 0; i < n - 1; i++) {
    int a = in.nextInt() - 1, b = in.nextInt() - 1;
    adj[a].add(b);
    adj[b].add(a);
    edgeIndex.put(Pair.of(a, b), i);
    edgeIndex.put(Pair.of(b, a), i);
}

int[] color = new int[n - 1];
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>();
q.add(Pair.of(0, -1));
while (!q.isEmpty()) {
    Pair<Integer, Integer> p = q.poll();
    int cur = p.first;
    int parent = p.second;
    int colorOfParent = parent == -1 ? 0 : color[edgeIndex.get(Pair.of(cur, parent))];
    int skippedColor = -1, skippedEdge = -1;
    for (int i = 0; i < adj[cur].size(); i++) {
        if (adj[cur].get(i) == parent) {
            skippedColor = i + 1;
            continue;
        }
        if (i + 1 == colorOfParent) {
            skippedEdge = edgeIndex.get(Pair.of(cur, adj[cur].get(i)));
        } else {
            color[edgeIndex.get(Pair.of(cur, adj[cur].get(i)))] = i + 1;
        }
        q.add(Pair.of(adj[cur].get(i), cur));
    }
    if (skippedEdge >= 0)
        color[skippedEdge] = skippedColor;
}
out.println(Util.max(color));
for (int x : color)
    out.println(x);

E: Rem of Sum is Num

First, we can consider all sums modulo $$$K$$$ throughout this problem. Let's weaken the constraints of what we're looking for and consider the number of elements modulo $$$K$$$ for a moment as well.

Notice that if we let $$$S_n = \sum_{i=1}^n A_i$$$ (and $$$S_0 = 0$$$), then the sum of a range $$$[i, j]$$$ (1-indexed) is $$$S_j - S_{i-1}$$$ and the number of elements in it is $$$j - (i-1)$$$.

This leads us to compute $$$P_i = S_i - i$$$ for $$$0 \le i \le n$$$, and we look for pairs $$$i < j$$$ such that $$$P_i \equiv P_j \pmod K$$$ (corresponding to taking the range $$$A_{i+1}, \ldots, A_j$$$).

Note that we actually have one more constraint: we shouldn't actually take the number of elements modulo $$$K$$$, so we need the number of elements modulo $$$K$$$ to be equal to the actual number of elements, so we require $$$j-(i-1) < K$$$.

We can count the pairs by maintaining a hashmap of the counts of values of $$$P_n$$$ within a sliding window of the past $$$K$$$ items (these are our candidates for the first coordinate of our range), and adding the count that match each possible second coordinate of our range. Each update takes constant time, so overall this solution takes linear time.

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

int n = in.nextInt();
int k = in.nextInt();
int[] a = in.readIntArray(n);
for (int i = 0; i < n; i++)
    a[i] %= k;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + a[i];
}
for (int i = 0; i <= n; i++) {
    prefix[i] = ((prefix[i] - i) % k + k) % k;
}

HashMap<Long, Integer> count = new HashMap<>();
count.put(0L, 1);
long answer = 0;
for (int i = 1; i <= n; i++) {
    if (i - k >= 0) {
        count.merge(prefix[i - k], -1, Integer::sum);
    }
    answer += count.getOrDefault(prefix[i], 0);
    count.merge(prefix[i], 1, Integer::sum);
}

out.println(answer);

F: Sugoroku

Let's make a few observations.

Observation 1: in order to minimize the number of steps, we should take steps that are as large as possible. We don't have to worry about a smaller step ever being better, because if in one step we can choose to go to either $$$i$$$ or $$$j$$$ (with $$$i < j$$$), then anything reachable from $$$i$$$ is also reachable from $$$j$$$ in the same-or-fewer steps. To prove this, consider an index $$$k > j$$$ that is reachable from $$$i$$$. At some point when traveling from $$$i$$$ to $$$k$$$, we will take a step that passes $$$j$$$. At this point, the endpoint of that step is also reachable from $$$j$$$ in one step (because it's at most $$$M$$$ away from a square that's before $$$j$$$), so we could have gotten here at least as fast from $$$j$$$.

Observation 2: in order to find the lexicographically-smallest sequence for a given number of steps, we need to put the largest steps at the end of the sequence. Therefore, we can start at $$$N$$$ and takes steps as large as possible towards $$$0$$$, then reverse the order of the steps at the end for printing.

Observation 3: Let's say we took a (backwards) step from $$$L$$$ to $$$C$$$ just now ($$$L > C$$$), and $$$C$$$ is the minimum index reachable in one step from $$$L$$$ (since we take the biggest steps possible). Then when evaluating the candidates for our next move, we don't need to evaluate anything that's $$$\ge (L-M)$$$, because those are all either unreachable or greater than $$$C$$$. This optimizes our runtime from quadratic to linear, since we only end up looking at each candidate once ever.

We can put this all together to code up a fairly straightforward linear-time solution.

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

int n = in.nextInt();
int m = in.nextInt();
char[] inputS = in.next().toCharArray(); // len n+1
boolean[] s = new boolean[n + 1];
for (int i = 0; i < n; i++) {
    s[i] = inputS[i] == '1';
}

Deque<Integer> answer = new ArrayDeque<>();

int cur = n;
int last = Integer.MAX_VALUE;
outer:
while (cur > 0) {
    for (int i = Math.max(0, cur - m); i < cur && i < last - m; i++) {
        if (!s[i]) {
            answer.addFirst(cur - i);
            last = cur;
            cur = i;
            continue outer;
        }
    }
    out.println(-1);
    return;
}

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

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