1400.md (6699B)
1 Source: https://codeforces.com/blog/entry/81916 2 3 Haven't done one of these for a while! Here are my approaches to the problems: 4 5 #### [1400A - String Similarity](/contest/1400/problem/A "Educational Codeforces Round 94 (Rated for Div. 2)") 6 7 We just need to make sure our string of $n$ characters matches each of the $n$ substrings in at least one spot. The easiest way to do this is to take every other character from $s$. Code: [90908018](/contest/1400/submission/90908018 "Submission 90908018 by neal") 8 9 Another fun solution: we can generate random strings and check them until we find one that matches everything. This works because the probability of failing to match any particular substring is $\frac{1}{2^n}$, so as $n$ gets bigger the probability of failing gets extremely low. Code: [90999219](/contest/1400/submission/90999219 "Submission 90999219 by neal") 10 11 #### [1400B - RPG Protagonist](/contest/1400/problem/B "Educational Codeforces Round 94 (Rated for Div. 2)") 12 13 First iterate on the number of swords we will personally take. Then we should greedily take as many war axes as we can until we run out of money. At this point, our follower needs to take as many items as possible. They can do this by greedily taking whichever of swords or war axes are cheaper until they run out, followed by taking the more expensive of the two. Code: [90918673](/contest/1400/submission/90918673 "Submission 90918673 by neal") 14 15 #### [1400C - Binary String Reconstruction](/contest/1400/problem/C "Educational Codeforces Round 94 (Rated for Div. 2)") 16 17 Note that $s_i = 1$ means "either $w_{i - x} = 1$ or $w_{i + x} = 1$," whereas $s_i = 0$ means "both $w_{i - x} = 0$ and $w_{i + x} = 0$." We can greedily solve this by starting out our string $w$ with all 1's, then marking $i - x$ and $i + x$ as 0 whenever we are forced to because $s_i = 0$. Then we can simply check whether all of the $s_i = 1$ conditions are valid to confirm. Code: [90915688](/contest/1400/submission/90915688 "Submission 90915688 by neal") 18 19 #### [1400D - Zigzags](/contest/1400/problem/D "Educational Codeforces Round 94 (Rated for Div. 2)") 20 21 We can rethink this as counting the number of equal pairs $(a_i, a_j) = (a_k, a_l)$ where $i \lt j \lt k \lt l$. To do this we loop over $j$ from right to left and make sure we have all $(a_k, a_l)$ pairs where $k \gt j$ counted in a map. Then we simply iterate over $i$ and add up the number of occurrences of each $(a_i, a_j)$ in the map. 22 23 For implementation details, note that we don't actually want to use a map and make our code slower. We can just use an array of size $n^2$ and convert the pair $(a_i, a_j)$ to the number $a_i \cdot n + a_j$ since the $a_i$ are in the range $[1, n]$. As a bonus, even if the $a_i$ were larger than $n$, we could just compress them down to $[1, n]$ and repeat the solution above. Code: [91019003](/contest/1400/submission/91019003 "Submission 91019003 by neal") 24 25 #### [1400E - Clear the Multiset](/contest/1400/problem/E "Educational Codeforces Round 94 (Rated for Div. 2)") 26 27 Notice that we can reorder the operations in any way we want without affecting the result. So let's do all of the first-type operations before the second-type operations. Then it's clear that the number of second-type operations we'll need is the number of nonzero elements left over after the first-type operations. So we just want to choose first-type operations to minimize the number of first-type operations plus the number of nonzero elements left after we're done. 28 29 Let's say we have an array $a$ where $a_m$ is the minimum value (if there is a tie, you can pick any tied index). I only have a messy proof for this at the moment, but it turns out we only need to consider two options: either take all $n$ second-type operations, or use $a_m$ first-type operations on the entire array and then recursively solve $a_1 - a_m, ..., a_{m - 1} - a_m$ and $a_{m + 1} - a_m, ..., a_n - a_m$ separately. This leads to a simple $n^2$ solution: [90999997](/contest/1400/submission/90999997 "Submission 90999997 by neal"). 30 31 Note that by using [RMQ](https://en.wikipedia.org/wiki/Range_minimum_query) we can improve this to $\mathcal{O}(n \log n)$ or even $\mathcal{O}(n)$. The idea is very similar to the solution to problem G [here](https://codeforces.com/blog/entry/64833). 32 33 #### [1400F - x-prime Substrings](/contest/1400/problem/F "Educational Codeforces Round 94 (Rated for Div. 2)") 34 35 The key observation is that since $x$ is only up to 20, there can't be that many different $x$-prime strings total--turns out there are only about 2400 for the worst case of $x = 19$. So we can generate all of them and perform a DP where our state is represented by the longest prefix of any of the strings we currently match. We can do this by building a trie of all of the $x$-prime strings. We then need to be able to transition around in this trie; it turns out this is exactly what [Aho-Corasick](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm) does for us. In particular, knowing which node of the Aho-Corasick tree we are currently at gives us the full information we need to determine whether or not we will match one of the strings after adding more characters later. This leads to a fairly simple DP: [90977148](/contest/1400/submission/90977148 "Submission 90977148 by neal") 36 37 #### [1400G - Mercenaries](/contest/1400/problem/G "Educational Codeforces Round 94 (Rated for Div. 2)") 38 39 In order to take care of the $l_i$ and $r_i$ constraints, we can iterate on the number of mercenaries we'll choose and find the number of choices for each count. The key constraint in this problem is that $m$ is at most 20, which means that there can only be a few connected components that aren't just a single node. In particular, the largest possible connected component size is 21 (since a connected graph with $m$ edges has at most $m + 1$ nodes). 40 41 This means that for each connected component we can iterate over all of the subsets of nodes in that component and check whether the subset is a valid choice (i.e., is an independent set). We can then do a DP for each component where dp(mask, k) = the number of submasks of mask that have k ones and represent a valid independent set subset of the component. 42 43 Finally we can iterate over the total number of mercenaries we want. We can then do a knapsack over each of the components, making sure to only consider nodes in each component where $l_i$ and $r_i$ work with our number of mercenaries. Finally we determine how many valid $l_i, r_i$ mercenaries are available outside of our components, and the rest is a simple choose function. Code: [90977154](/contest/1400/submission/90977154 "Submission 90977154 by neal")