Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

AnandOza's blog

By AnandOza, history, 3 months ago, In English,

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

Sample code

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

Sample code

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

Sample code

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

Sample code

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

Sample code

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

Sample code

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

Read more »

 
 
 
 
  • Vote: I like it
  • +36
  • Vote: I do not like it

By AnandOza, history, 4 months ago, In English,

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

Sample code

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

Sample code

Alternate solution (and code) by Tejs:

The product can be rewritten as $$$\frac{1}{2} \left[ \left(\sum_i d_i\right)^2 - \sum_i d_i^2\right]$$$.

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

Sample code

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

Sample code

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

Sample code

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

Sample code

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

Sample code

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +101
  • Vote: I do not like it

By AnandOza, 8 months ago, In English,

Hi all, Atcoder Beginner Contest 132 was today. Atcoder only publishes Japanese editorials for beginner contests, so I wrote an unofficial English editorial. Hope it helps!

A: Fifty-Fifty

After sorting the input, a "good" string will look like "AABB". Therefore, we simply sort and check for this format.

Sample code

B: Ordinary Number

It suffices to simply check every range of 3 and see if its middle element should be counted. A simple way is to sort each range of 3 and check that the middle element remains in the middle.

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

Sample code

C: Divide the Problems

If we first sort the problems by difficulty, the necessary condition is equivalent to "the first half of the problems will be for ABCs, and the second half will be for ARCs". If we assign $$$B$$$ to the hardest ABC problem (problem $$$(N/2)$$$, after sorting) and $$$R$$$ to the easiest ARC problem (problem $$$(N/2+1)$$$, after sorting), we need to select $$$K$$$ such that $$$B < K \le R$$$.

Therefore, we have $$$R-B$$$ choices for K. (Note: if $$$R$$$ and $$$B$$$ are equal, there is no choice of $$$K$$$ that splits the problems in half.)

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

Sample code

D: Blue and Red Balls

In order for Takahashi to take exactly $$$i$$$ moves, we need $$$i$$$ separate "buckets" of blue balls. Let us say we have $$$R = N-K$$$ red balls and $$$B = K$$$ blue balls. Then, we may separately compute $$$X$$$ as the number of ways to order the $$$R$$$ red balls and the $$$i$$$ buckets of blue balls, and compute $$$Y$$$ as the number of ways to distribute the $$$B$$$ blue balls into the $$$i$$$ buckets. The output for $$$i$$$ moves is then $$$X \cdot Y$$$.

Let us compute $$$X$$$. If we imagine the $$$R$$$ red balls already in a row, there are $$$R+1$$$ spaces to put a bucket of blue balls (it can go left of all the balls, right of all the balls, or in the $$$R-1$$$ gaps between consecutive red balls). Therefore, $$$X = \binom{R+1}{i}$$$.

Let us now compute $$$Y$$$. To distribute $$$B$$$ blue balls into $$$i$$$ buckets, we can imagine all the blue balls in a row and insert $$$i-1$$$ dividers into the $$$B-1$$$ spaces between the balls to separate them into buckets. Therefore, $$$Y = \binom{B-1}{i-1}$$$.

Note: computing binomial coefficients can be done for this problem either by precomputing Pascal's Triangle in $$$O(N^2)$$$ time or by precomputing factorials and their inverses, since $$$N \le 2000$$$.

Sample code

E: Hopscotch Addict

Repeating ken-ken-pa $$$k$$$ times corresponds to following a path of length exactly $$$3k$$$ in the graph. Therefore, we need to find the shortest path from $$$S$$$ to $$$T$$$ whose length is a multiple of 3.

In order to solve this, we create a new graph $$$G'$$$ with $$$3N$$$ vertices and $$$3M$$$ edges. For each vertex $$$v_i$$$ in the original graph $$$G$$$, we create three vertices $$$v_0$$$, $$$v_1$$$, and $$$v_2$$$ in $$$G'$$$. For every edge $$$(u, v)$$$ in $$$G$$$, we create edges $$$(u_0, v_1)$$$, $$$(u_1, v_2)$$$, and $$$(u_2, v_0)$$$ in $$$G'$$$.

In this way, a path from $$$u_i$$$ to $$$v_j$$$ in $$$G'$$$ corresponds to a path in $$$G$$$ whose length is congruent to $$$j-i \text{ (mod 3)}$$$.

Therefore, we can run a BFS on $$$G'$$$ to find the shortest path from $$$S_0$$$ to $$$T_0$$$, which corresponds to the shortest path with length a multiple of 3 in $$$G$$$. If we find such a path, we simply divide its length by 3 to get the number of ken-ken-pa.

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

Sample code

F: Small Products

Let's divide the numbers from $$$1$$$ to $$$N$$$ into "small" and "big" numbers. We call "small" numbers those that are at most $$$\sqrt{N}$$$, and "big" numbers those that are greater than $$$\sqrt{N}$$$.

This means that any two small numbers can be adjacent, and no two big numbers can be adjacent. When putting a small number $$$s$$$ and a big number $$$b$$$ adjacent, we require $$$s \cdot b \le N$$$.

Thus, we can split the possible values of $$$b$$$ into $$$\sqrt{N}$$$ buckets $$$B_i$$$ based on the maximal small number they can be paired with (for example, if $$$N=10$$$, the big numbers $$$4$$$ and $$$5$$$ can be paired with the small number $$$2$$$, but not with $$$3$$$, so they would go in $$$B_2$$$).

When we have built a partial sequence, we only care about the last value in the sequence when deciding how to build the rest of the sequence. Moreover, we actually only care about the $$$2\sqrt{N}$$$ categories the last element can fall into (either a small number or a bucket of big numbers).

Let $$$s(i, j)$$$ be the number of sequences of length $$$i$$$ ending with a small number $$$j$$$. Let $$$b(i, j)$$$ be the number of sequences of length $$$i$$$ ending with a big number in $$$B_i$$$.

A small number $$$j$$$ can be placed after any other small number, or after a big number in $$$B_k$$$ where $$$k \ge i$$$.

$$$\displaystyle s(i,j) = \sum_{k=1}^{\sqrt{N}} s(i-1,k) + \sum_{k=j}^{\sqrt{N}} b(i-1,k)$$$

A big number $$$j$$$ can be placed after any small number $$$k \le j$$$. We have $$$|B_j| = \frac{N}{j} - \frac{N}{j+1}$$$ possibilities for this big number.

$$$\displaystyle b(i,j) = \left( \frac{N}{j} - \frac{N}{j+1} \right) \sum_{k=1}^{j} s(i-1,k)$$$

This directly leads to an $$$\mathcal{O}(k \sqrt{N}^2)$$$ dynamic programming solution, which can be sped up to $$$\mathcal{O}(k \sqrt{N})$$$ by precomputing $$$\sum_{k=1}^j s(i-1,j)$$$ and $$$\sum_{k=j}^{\sqrt{N}} b(i-1,k)$$$ for all j, after we compute everything for $$$i-1$$$ and before we compute everything for $$$i$$$.

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

Sample code

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

Read more »

 
 
 
 
  • Vote: I like it
  • +124
  • Vote: I do not like it