Kattis of the Week

4 September 2024

Since I am no longer teaching CS2040 (Data Structures and Algorithms) as an undergraduate teaching assistant in NUS, I thought it would be nice to dump some additional Kattis problems here (initially for my students) that I usually call as KOTW (stands for the article title). Future CS2040 students might find this article useful.

Little warning that these problems are almost sorted by difficulty.

T2: Sorting

Missing Gnomes Literally the last question of this tutorial (first permutation thingy)
Height Ordering Simulate insertion sort
Messy lists Suppose S is the sorted version of A, how many values of i such that S[i] != A[i]?
Pivot (hard problem) You probably see this question very often in your VisuAlgo quiz. If an element is a possible pivot, all elements to its left must be smaller and all elements to its right must be larger. To keep track of this, you can use an array to keep track of the minimum/maximum so far as you iterate through array from the right/left direction. This technique is also known as the running min/max


T3: Lists, Stacks, Queues

Circuit Math Now we deal with postfix expressions! Same idea, but instead you can use one stack: if you see an operator, pop the operator and pop the two operands, and push the evaluation result, rinse and repeat
Bracket Sequence (slightly harder) Now we deal with infix expressions! Again same idea, with an extra toggle whether you should add everything or multiply everything. Read tokens until a you see a close bracket
Find my Family (hard but useful) My fellow ex-tutor Eric Leow has provided the entire explanation for you, here we introduce you to a special kind of stack, the monotonic stack!
Stol Also a video by Eric
Bungee Builder Now that you've learnt about monotonic stacks, try this out :)


T4: Hashing

I Wanna Be The Very Best Have a hashset that contains top K attacks, top K defense, and top K health. Report the length of the hashset (which should at most 3K)
CD Just populate the two sets A and B and report the size of the intersection. You can use a for loop to do this :)
Variable Names Have a hashtable of (number: variable_index) and simulate the process until the number reaches 104, if the number isn't taken yet it shouldn't be an existing key inside the hashtable
Quickscope (fun + hard? combo?) TLDR: stack-of-hashmaps and hashmap-of-stacks
This is quite hard, but gives an idea of a bi-map where you store the mapping for both directions: one map tells which levels of nesting a variable has and one map tells what variables are on a particular nesting level.
Suppose we have a stack of hashmaps called S and another hashmap called T. At any point of time, let K be the hashmap on the top of S.
Our goal is such that for each hashmap in S, it stores the variables in the corresponding nesting level and their type as a key-value pair. As for T, the keys are the variables and the values are stacks of the nesting levels this variable is currently used.
  • If you detect a new level of nesting being added (i.e. detect a "{"), push another empty hashmap to S (this is the new K). This ensures that the hashmap on top of the stack refers to the current nesting level you're at
  • If you see a DECLARE x y, add x as the key of K and y as the value. If x already exists beforehand as a key in K, you know it's a MULTIPLE DECLARATION, print that and terminate the code immediately. Otherwise, you also need to add the nesting level into T accordingly (check if x is already a key in T and then handle the addition accordingly)
  • If you see a TYPEOF x, then you know that we can always look at the last element of T[x], say it's d, and report S[d][x] (the stack S must be an arraylist so we can still access S easily) or UNDECLARED if T[x] is empty
  • If you detect the end of the nesting (i.e. a "}"), we need to do two things in this order: ensure that you have popped this nesting level from T on all variables contained in K. After that, you safely pop K out of S (K changes to the current top of S)
This ensures that the time complexity of each query is O(1), note that the preprocessing happens on the first and last bullet points where you have to go through all variables within that nesting level!

Here's an example to visualize what's going on. Suppose we have this as the input
DECLARE a int
DECLARE b float
{
DECLARE b int
DECLARE c int
}
DECLARE d double

then our S looks like [{a: int, b: float, d: double}, {b: int, c: int}] and our T looks like {a: [0], b: [0, 1], c: [1], d: [0]}


T5: PQ

Continuous Median One of my favourite Leetcode problems. The idea is to have one max heap to store the first half of the "array" and then one min heap to store the latter half. For every iteration, insert to one of the heaps and balance the sizes whenever necessary (e.g. ensure that max heap size is N/2 and min heap size if N−N/2). When reporting the median, check whether you need to peek the max heap or do you have to take the average of both heap peeks (depends on whether N is currently odd or even)!
Koffínhraði Quite a big brain problem, thought I'd like to share with you guys. The idea is to sort the tasks by the DEADLINE because obviously you want to finish things due earlier first. Next, have a max heap to store the task times and a variable to keep track of the sum of the elements in the max heap so far. As you go through the sorted task list, we need to ensure that this sum does not exceed the deadline time of the task you're dealing with. Otherwise, until the sum is before the deadline, keep taking the task with the largest time (thus a max heap), half it, and put it back into the heap. This ensures that after completely processing the task, the sum of the task time so far will never exceed the deadline of the last task.
One more thing is that we take the task with the largest time because the amount of time saved by halving would be the most when performed on this particular task. For example, 5 -> 2 saves 3 seconds but 100 -> 50 saves 50 seconds!

Pseudocode would be something like this:
pq = max heap initially empty
sum = 0
ans = 0
sort the tasks by increasing deadline
for each task in the sorted task list:
    pq.push(task_time)
    sum += task_time
    while sum > task_deadline:
        t = popped task_time from pq
        pq.push(t/2)
        sum = sum - t + t/2
        ans += 1
output ans
Stock Prices Have a max heap for the buy prices and min heap for sell prices, keep polling from both queues accordingly using a while loop!


T6: UFDS

Union-Find It's literally union find without any modification, like, at all.
Reachable Roads If u and v are connected by an edge, just merge u and v in the UFDS, reachable if they belong to the same set
Graduation Merge accordingly and find the number of disjoint sets left
Bus Numbers UFDS from 1 to 1000, keep track of min and max of each set
Tildes Keep track of size, then answer the query accordingly


T7: BST

Continuous Median (again!) Yes, again you can use BST for this instead of priority queue, just repeated use the select method from AVL tree as you insert elements into it
Galactic Collegiate Programming Contest Store all the teams into an AVL tree, update the points by deleting the node corresponding to the particular team and then reinsert the updated node corresponding to that same team. Note that you need to use the rank function in AVL tree!
99 Problems You can use the successor method in AVL trees or just use the TreeSet/TreeMap methods such as floorKey or higherKey! The rest is straightforward based on the instructions
Classrooms (hard problem?) See interval scheduling on Wikipedia for the official term for this problem but you use an AVL tree to store the compatible intervals so far!


T8: Graph DS and Trav

Cut the Negativity Basic conversion from adjacency matrix to edge list, a simple nested for loop will do
Map of Sweden Most graph problems in Kattis involve 2D grids, so let's get familiar with making the adjacency list for this one, and then we can also represent each cell as one element of an UFDS on top of the adjacency list. Then for each query, it will be just the combination of enumerating the neighbours of the adjacency list and the merge part of UFDS
Running MoM Let's apply cycle checking for this one. Report 'safe' is there is a cycle involving the city in query, 'trapped' otherwise.
Námsleið Use Kahn's algorithm to keep track of the maximum distance between a node and any node with indegree 0. This can be done by carrying the current depth into the queue (store (node, depth) instead of just node, then you can update into (next_node, depth+1)). Finally, use a hashmap to keep track which modules to take for each depth value, assuming the graph is a DAG.
Pachinko Probability (slightly hard) Interesting problem that uses toposort to count the number of paths from any vertex with indegree 0 to those with outdegree 0, then among those paths how many land on the squared vertices (if you're using Kahn's algorithm, accumulate the number of paths in reverse topological order)


T9: MST

Minimum Spanning Tree Basic MST problem, given input output MST weight and all the edges
Freckles Simply the MST cost
Nature Reserve Prim's, this tutorial's last question (the power plant thingy)
Treehouses Run Kruskal's with all the first e houses merged on the same set in the UFDS
Grid MST (very hard, proceed with caution) Kruskal's but you need a way to reduce the graph using BFS since without it O(N2logN) is too big thus TLE, more details are omitted in this article


T10: SSSP P1

Button Bashing First question of the tutorial (unlocking the lock), same idea!
Fire Same as the fire tutorial question!
Fire! Same as the fire tutorial question!
Slikar Same as the fire tutorial question! Had enough dejavus?
Ocean Currents (useful!) I'd like to introduce you guys to a variant of BFS callled 0-1 BFS. Assuming you managed to populate the graph, you will see that the edge weights are either 0 or 1. Instead of using a queue to perform the BFS, use a double-ended queue! This is because you have to either append the next state to the front of the queue or the back of the queue, depending on the edge weight, the front if it's 0 and the back if it's 1. This ensures that the double-ended queue will preserve the ordering of the distances taken so far (remains sorted)!
Get Shorty Similar to the money question, use negative log transformation and then just use Dijkstra!
Single source shortest path, negative weights Interesting SP problem, even with negative cycles doesn't mean the shortest path to any vertex cannot be found since it may be outside the negative cycle itself

How to tackle: Run bellman ford and compare the (V−1)-th iteration with the next k iterations (at most V−1 more iterations). If the value doesn't change, that's the SP already. Otherwise, the vertex is part of a negative cycle. You can use a while loop to keep track of which vertices has its value changed but not marked as part of negative cycle.


T11: SSSP P2 + APSP

Fend Off Titan Just a regular Dijkstra but instead of storing (sp_estimate, node) in the priority queue, store (num_of_titans, num_of_shamans, sp_estimate, node) instead, since we are comparing the values in this order
Invasion Also another variant of Dijkstra, but keep track of what's unsafe until the sp_estimate reaches k!
Tima goes to Xentopia The idea is to clone the graph and run regular Dijkstra, very similar to that of Finals 20/21 Sem 2 Q19
Real Manhattan Distance (hard problem) The hard part is how to construct the adjacency list since it involves linear algebra to some extent. Otherwise, it's just Dijkstra
VisuAlgo Online Quiz A variant of Dijkstra algorithm where instead of storing just a single integer on the D array, you store a pair (sp_estimate, num_of_paths). Make sure you managed to update the value of num_of_paths accordingly, whether D[node] == curr_sp_estimate or D[node] > curr_sp_estimate (to which you have to reset it to 0)
Hopscotch 50 MSSP with Dijkstra from all the 1 tiles to any one of the k tiles. Note that you can always convert MSSP to SSSP using the concept of super-source and super-sink!
Arbitrage? Classic Floyd-Warshall using negative-log transformation but check the diagonal entries if there are negative values!