I’ve finally decided to bury the singular depressing post on this site with other stuff. Unfortunately, competitive programming is also a depression trigger for some people (read: me), so the whole place is unfortunately still depressing.
At least it makes me look like I can program (which as you will see below, is not true).
Anyways, have a link to the contest problemset. As per usual with these log-type blogs, everything below is a spoiler.
A – Water Station
Too lazy to think, so I ran with a loop that looked sort of like this:
for (int i = 0; i <= 100; i += 5) {
dist = min(dist, abs(x - i));
}B – ABCDEFG
Did a prefix sum on {3, 1, 4, 1, 5, 9} for the positions of the characters, then just took the absolute difference after finding the positions of the two characters.
C – Snuke the Cookie Picker
The problem statement made me feel illiterate, so I jumped straight to the test case to try to understand what the problem was asking. Fortunately, the samples were really easy to understand.
Basically, find the top left and bottom right corners of the shape by taking the minimum and maximum row and column numbers, respectively, and then just loop through the cells finding the one sussy empty cell.
D – Sleep Log
This one took me a really long time. I swear I could’ve fed an entire community with the amount of bugs I cooked up. The takeaway is that I really fucking hate indexing.
Anyway, compress every possible point in time (including the points of time in the queries), then just do a prefix sum/difference like structure where you increment the structure by 1 at $t = L_i$ and decrement it by 1 at $t = R_i + 1$. Remember to take into account the fact that the time points are compressed from the original.
E – Art Gallery on Graph
Just do a multi-source BFS, taking guarded nodes as the start nodes while expanding the nodes with higher weight first. The intuition for this is exactly the same as Dijkstra’s algorithm, to avoid visiting some node twice as much as possible. Use your language’s Heap/Priority Queue container to make life easier.
F – Dungeon Explore
Even when the problem is interactive, test locally before submitting, people. Don’t risk CEs and WAs due to forgotten debug code. Don’t be like me.
Implement DFS in an interactive way, while taking care not to visit the same node twice. Using recursion makes life easier as you can just do the following.
void hoge(int curNode, int parent) {
// move into current node
for (auto& adj : adjList[curNode]) {
// do stuff
}
// move back to parent
}G – Banned Substrings
Solved this one post-contest due to my amazing tendency of producing typos at perfectly comical timings.
Think of a way to solve this when $N \leq 10^5$. DP instantly comes to mind. Below is the equation I thought of, in unoptimized Python and without memoization code for readability.
def f(remaining_len, last_six_chars):
if remaining_len == 0:
return 1
ans = 0
for added_char in "AB":
next_last_six_chars = last_six_chars + added_char
if len(next_last_six_chars) > 6:
next_last_six_chars = next_last_six_chars[1:]
if not is_banned(next_last_six_chars):
ans += f(remaining_len - 1, next_last_six_chars)
return ansYou can optimize away the string stuff to check whether or not it’s banned by using bitmasks for everything. I encoded mine as $(|substring|, substring)$, where substring is a bitmask with $A = 1$ and $B = 0$.
For example:
- ABAB is
(4, 0b1010 [10]) - AAABAB is
(6, 0b111010 [58]) - BBAAA is
(5, 0b00111 [7])
Then, appending to a string is just something like this.
def append(substring, added_char):
length, substring = substring
length = min(6, length + 1)
return (length, (substring << 1 | (added_char == 'A')) % 2**6)Remember that the solution so far only works for $N \leq 10^5$. Realizing that the transformation from $f(n, ?)$ to $f(n + 1, ?)$ can be modeled by a matrix takes us the rest of the way. Use the classic fast exponentiation trick on matrices to allow for computing $M^{10^{18}}$ in a reasonable amount of time.
I didn’t bother with the matrix stuff and just plugged the first few terms computed via DP into Black Magic. Always works.
Ex – Shojin
My blue ass ain’t even gonna bother trying.