777B: Games of Credit Cards

This problem took me too much time!!! Probably because I had to wake up at 4 am….

To give max hits, map M’s 9 to S’s 8, 8 to 7,….etc. With carry over potentially positive balances

To recieve min # of hits, map S’s 9 to M’9, the hit is whenever there is a positve delta

Note that we care about only positive deltas, we ignore negative delta, because in the end we will use left over postive deltas to fill those negative deltas, because two strings have same length, we know they will match

777C:Alyona and Spreadsheet

for each row, calculate the earliest start of the increasing subsequenceo

when answering the query [l,r], just look up r and find if answer <= l

777D:Cloud of Hashtags

Instead of calculating min # of removal, we calculate max # of keeps, because adding letter only “increases” a word, we start from the tail, and try adding letter as much as we can

so the last one, we can keep all letters the previous one, we can keep max prefix <= last one
keep going until the first one

776C: Molly’s Chemicals

Calculate the prefix sum, and find how many prefix sum before the current one, such that ps(current) - ps(previoius) = power of k

Since we care only about the previous prevous sums, we can calculate final answer while we build that, so that we don’t have to worry about interference of prefix sums after i

Overall run time O(n * log(k, 10^14))

Corner case k = 1 or -1 !!!