8/21-8/28 Slides

A - Primary Task

• Each string has to be at least 3 characters
• Has to start with ‘10’
• Third character can’t be ‘0’, and also can’t be ‘1’ if the string is only 3 characters long

B - Seating in a Bus

• The first person can sit anywhere
• Update the seats where people can sit whenever someone sits down
• If someone sits in an invalid seat then they didn’t follow directions

C - Numeric String

Template

• Map each template and string to its “indexed group” form
• {3, 5, 2, 1, 3} -> {0, 1, 2, 3, 0}
• "abfda" -> {0, 1, 2, 3, 0} (matches, so YES)
• "afbfa” -> {0, 1, 2, 1, 0} (does not match, so NO)

D - Right Left Wrong

• Optimal to start from the outermost LR and then work your way in
• The reverse of this will satisfy the requirements of the problem
• Need to calculate all sorts of sums in the range
• Use prefix sums
• Need to work your way from out to in
• Two pointers

E - Photoshoot for Gorillas

• Optimal to put the tallest gorillas in the squares that will be in the most subsquares
• Calculate how many times each square will be counted
• Pair the tallest gorillas with the squares that are most counted and work your way down

F - Color Rows and Columns

We do knapsack dp on the minimal number of operations with the state [first i rectangles][getting j points].

G - Call During

the Journey

We Dijkstra from “n” to find the latest time you are allowed to leave the i-th node. Before adding a state involving using a bus to the priority queue, make sure we are allowed to use the bus. Before adding a state involving walking to the priority queue, make sure it is not a better decision to simply wait and use a bus. Try not to TLE on test case 17 :(

H - Ksyusha and the Loaded Set

Maintain a segment tree of size MAX_X throughout all test cases. Maintain vals below

Answer +/- queries by setting the index to true or false in the segment tree

For ? queries, binary search on the first index such that [0, idx] has a continuous string

of 0s of length k. If no such values exist, print last_true_idx + 1, else print idx - x + 1

At the end, reset the segment tree by setting all values back to false