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

A: Curtain

The curtains can cover a maximum of $$$2B$$$. So either they don't cover the whole window and the remainder is $$$A-2B$$$, or they do and the remainder is $$$0$$$. So the answer is $$$\max(0, A-2B)$$$.

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

int a = in.nextInt(), b = in.nextInt();
out.println(Math.max(0, a - 2 * b));

B: TAKOYAKI FESTIVAL 2019

We can simply loop through every pair (taking care not to double count) and add the health points restored.

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

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

long answer = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        answer += d[i] * d[j];
    }
}

out.println(answer);

C: Slimes

We have to count the number of "runs" of consecutive slimes of the same color. We can do this by looping through the array and checking whether the current slime continues the run, then incrementing our answer when we reach the end of a run.

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

int n = in.nextInt();
char[] s = in.next().toCharArray();

int answer = 0;
for (int i = 0, j = 0; i < n; i = j) {
    while (j < n && s[i] == s[j])
        j++;

    answer++;
}
out.println(answer);

D: Triangles

The total number of (unordered) triples of sticks is $$$\binom{n}{3} = n(n-1)(n-2)/6$$$. I think it's simplest to count the number of triples that cannot form a triangle, and subtract them. Let's first sort the input array, so if we have a triple $$$(i,j,k)$$$ with $$$i < j < k$$$, we also know $$$L_i \le L_j \le L_k$$$.

Then, we can loop through all pairs $$$(i,j)$$$ and determine how many values of $$$k$$$ make an invalid triple (but still maintaining $$$i<j<k$$$). Note that because we picked the two smaller sticks of our triple, we know the only possible disqualifying condition is $$$L_k \ge L_i + L_j$$$. We can find the smallest such value of $$$k$$$ using binary search, and then subtract $$$n-k$$$ from our answer.

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

int n = in.nextInt();
Integer[] L = in.readIntegerArray(n);

Arrays.sort(L);

long answer = ((long) n) * (n - 1) * (n - 2) / 6;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        int sum = L[i] + L[j];

        // binarySearch(condition) finds the first index such that condition is true
        int k = binarySearch(index -> {
            if (index >= n)
                return true;
            if (index < 0)
                return false;
            return L[index] >= sum;
        });

        answer -= n - k;
    }
}

out.println(answer);

E: Travel by Car

First, observe that any path that has $$$K$$$ refills can be split into $$$K+1$$$ paths, each of which can be completed (starting with a full tank of gas) without refilling.

So, we can begin by finding all pairs of cities that can be traveled between on a full tank of gas without refilling. To do this, we can find the shortest path between all pairs of cities (for example, using Floyd-Warshall). Then, we build a new adjacency matrix for these paths, where two cities with distance $$$\le L$$$ have an edge of cost $$$1$$$, and two cities with distance $$$> L$$$ have no edge (or an edge with cost $$$\infty$$$). Then we compute the shortest path between all pairs using this new adjacency matrix, which tells us the minimum number of segments a valid path in the original graph can be broken into.

Then, given a query $$$(s,t)$$$, we simply find the distance in the new shortest-paths matrix and subtract $$$1$$$, and we have our answer (or print $$$-1$$$ if it's unreachable). We have to remember to subtract $$$1$$$ because it takes $$$K$$$ refills for a path of $$$K+1$$$ segments (or equivalently, the first tank of gas is free).

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

int n = in.nextInt();
int m = in.nextInt();
long l = in.nextLong();

long[][] adj = new long[n][n];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        adj[i][j] = i == j ? 0 : INF;
    }
}
for (int i = 0; i < m; i++) {
    int a = in.nextInt() - 1;
    int b = in.nextInt() - 1;
    long c = in.nextLong();

    adj[a][b] = adj[b][a] = c;
}

// Floyd-Warshall
for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
        }
    }
}

long[][] oldAdj = adj.clone();

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        adj[i][j] = oldAdj[i][j] <= l ? 1 : INF;
        if (i == j) {
            adj[i][j] = 0;
        }
    }
}

// Floyd-Warshall
for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
        }
    }
}

int q = in.nextInt();
for (int query = 0; query < q; query++) {
    int s = in.nextInt() - 1;
    int t = in.nextInt() - 1;

    long answer = adj[s][t];
    if (answer >= INF) {
        answer = -1;
    } else {
        answer--; // first fill free
    }
    out.println(answer);
}

F: Distinct Numbers

The key observation is that if you pick $$$M$$$ distinct numbers and remove all instances of them, and you have $$$S$$$ total numbers left, the maximum number of operations you can do is bounded above by $$$S/(K-M)$$$. Then, note that picking the $$$M$$$ most frequent distinct numbers gives the tightest bound (so instead of all subsets, we need to consider a lot less stuff).

So, we can count the instances of each number, so we end up with an array $$$C$$$ containing these frequencies. We can sort these frequencies, then for each value of $$$M$$$, compute the number of remaining numbers after we remove all instances of the top $$$M$$$ (let's call this $$$S_M$$$).

The function $$$f_K(M) = \frac{S_M}{K-M}$$$ is first decreasing, then increasing, so we can find its minimum by binary searching to find the first $$$M$$$ for which it increases. This gives us the tightest bound available. Once we do that, we simply need to check against the simple bound $$$N/K$$$ and return our answer.

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

int n = in.nextInt();
int[] a = in.readIntArray(n);
Integer[] count = new Integer[n];
Arrays.fill(count, 0);

for (int x : a) {
    count[x - 1]++;
}

Arrays.sort(count, Comparator.reverseOrder());

int[] remain = new int[n];
remain[0] = n - count[0];
for (int i = 1; i < n; i++) {
    remain[i] = remain[i - 1] - count[i];
}

out.println(n); // k=1
for (int kLoop = 2; kLoop <= n; kLoop++) {
    int k = kLoop;
    int bound = n / k;
    
    // finds the first i s.t. the condition is true
    int index = BinarySearch.binarySearch((i) -> {
        if (k - 1 - i <= 0)
            return true;
        if (i <= 0)
            return false;

        double boundCur = ((double) remain[i]) / (k - 1 - i);
        double boundPrev = ((double) remain[i - 1]) / (k - 1 - (i - 1));
        return boundPrev < boundCur;
    });

    index--;
    bound = Math.min(bound, remain[index] / (k - 1 - index));
    out.println(bound);
}

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.