Atcoder Beginner Contest 143 — Unofficial English Editorial
Difference between en1 and en2, changed 6,884 character(s)
Hi all, [Atcoder Beginner Contest 143](https://atcoder.jp/contests/abc143) was today. I wrote an unofficial English editorial. Hope it helps!↵

### [A: Curtain](https://atcoder.jp/contests/abc143/tasks/abc143_a)↵

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)$.↵

<spoiler summary="Sample code">↵
~~~~~↵
int a = in.nextInt(), b = in.nextInt();↵
out.println(Math.max(0, a - 2 * b));↵
~~~~~↵
</spoiler>↵

### [B: TAKOYAKI FESTIVAL 2019](https://atcoder.jp/contests/abc143/tasks/abc143_b)↵

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

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

<spoiler summary="Sample code">↵
~~~~~↵
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);↵
~~~~~↵
</spoiler>↵

### [C: Slimes](https://atcoder.jp/contests/abc143/tasks/abc143_c)↵

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)$.↵

<spoiler summary="Sample code">↵
~~~~~↵
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);↵
~~~~~↵
</spoiler>↵

### [D: Triangles](https://atcoder.jp/contests/abc143/tasks/abc143_d)↵

The total number of (unordered) triples of sticks is $\binom{n}{3} = n(n-1)(n-2)/
3$. 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, then if we have a triple $(i,j,k)$ with $i < j < k$, we also know $L_i \le L_j \le L_k$.↵

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

<spoiler summary="Sample code">↵
~~~~~↵

~~~~~↵
</spoiler>↵

### [E: Travel by Car](https://atcoder.jp/contests/abc143/tasks/abc143_e)↵

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

<spoiler summary="Sample code">↵
~~~~~↵

~~~~~↵
</spoiler>↵

### [F: Distinct Numbers](https://atcoder.jp/contests/abc143/tasks/abc143_f)↵

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

<spoiler summary="Sample code">↵
~~~~~↵

~~~~~↵
</spoiler>↵
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)$.↵

<spoiler summary="Sample code">↵
~~~~~↵
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);↵
~~~~~↵
</spoiler>↵

### [E: Travel by Car](https://atcoder.jp/contests/abc143/tasks/abc143_e)↵

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)$.↵

<spoiler summary="Sample code">↵
~~~~~↵
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);↵
}↵
~~~~~↵
</spoiler>↵

### [F: Distinct Numbers](https://atcoder.jp/contests/abc143/tasks/abc143_f)↵

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})$.↵

<spoiler summary="Sample code">↵
~~~~~↵
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);↵
}↵
~~~~~↵
</spoiler>↵

You can see my submissions [here](https://atcoder.jp/contests/abc143/submissions?f.Task=&f.Language=&f.Status=AC&f.User=AnandOza) 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.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English AnandOza 2019-10-21 07:50:40 464 added O(N) solution by Tejs for B
en3 English AnandOza 2019-10-19 17:12:46 2 fixed runtime on A
en2 English AnandOza 2019-10-19 17:09:26 6884 (published)
en1 English AnandOza 2019-10-19 16:33:11 2669 Initial revision (saved to drafts)