NYRCS pset 7 - Hints

Solution.md

Hints & solutions

Wormholes

Hint 1

When defining a DP function, think about all the possible ways to get to where you are from ONE step before.

Also assume that if your cases are correct, all your dp results are correct.

Hint 2 - What function to define?

f(i) = shortest time to get from planet #i from planet #0

Hint 3 - Base case

f(0) = 0 as you start there

Hint 4 - Hint for recursive case

You can only get to planet #i directly by
1. Travelling from #i-1
2. OR teleporting to #i from a planet before #i

Solution

Iterative with an array.

  - f(i) = shortest time to get to planet #i from planet #0
    | f(0) = 0 as you start there
    | f(i) = minimum among 
    |        1. getting to #i from #i-1 
    |        2. wormholing to #i through a wormhole that ends at #i
    |      = min(f(i-1) + 1, f(j) + 1 where j is the starting planet for a wormhole which ends at i.)
    |      (Notice that these two are the simplest cases which cover all possibilities.)
  

Flybot

Hint 1 - What function to define?

Let the top left corner be (0, 0). Where h is height and w is width, let bottom right corner be (w-1, h-1).
f(x, y) = Number of distinct ways to get from (0,0) to (x,y)

Hint #2

  +---+---+
  |   | b |
  +---+---+
  | a | c |
  +---+---+
  

You can only get to c from a and b as you can only move down and right.

Beareatrabbit

Hint 1 - Read the statement

Tastiness can be negative.

Hint 2 - What function to define?

f(n) = maximum tastiness after considering every rabbit from 1 to n

Hint 3 - Observation

It can be proven that as long as you guarantee you don't eat two rabbits one after the other, you are satisfying the constraint of both the front and back rabbits running away.

Solution

Let f(i) be the maximum total deliciousness after considering rabbits from 1 to i.
We consider two options for each rabbit:
1. Eat rabbit i: Then we must skip rabbit i−1, so we add A[i] to f(i−2).
2. Don't eat rabbit i: We just take the best result up to rabbit i−1, i.e., f(i−1).

  f(i) = max(
    f(i − 1),        // skip rabbit i
    f(i − 2) + A[i]  // eat rabbit i, skip i−1
  )
  

Base cases:

  f(0) = 0  (no rabbits)
  f(1) = max(0, A[1])  (eat or skip the first rabbit)
  

lol

Hint 1

Let's say instead of searching for 'lol' we are searching for 'ab'.

  String: abababaabbbaaab
  To find the number of ab sequences where the b is fixed as the b indicated by the arrow ^:
    abababaabbbaaab
    * * * **  ^
    Count the number of 'a' beside it.
  Thus, there are 5 ab sequences that end at the indicated b.
  

Hint 2 - An observation

  Notice we can do the process in hint #1 for every single b with a single pass, if we keep a running counter
          abababaabbbaaab
  A:      * * * **   ***
  Count:  112233455556788
           ^ ^ ^  ^^^   ^
  Answers: 1 2 3  555   8
Thus, the number of ab sequences here = sum from every b = 29

Solution (concept)

  To find the number of 'lol' sequences,
  Step 1: Find number of 'lo' sequences that end at every o
  loolololollol
  *  * * * ** *
  1112233445667
   ^^ ^ ^ ^  ^
   11 2 3 4  6
Step 2: Find number of 'lol' sequences that end at every l
For any particular l, it is the sum of all the counts of 'lo' on its left
l o o l o l o l o  l  l  o  l
'lo':        1 1   2   3   4        6  17
counter:   0 1 2 2 4 4 7 7 11 11 11 17 17
^     ^   ^   ^    ^  ^     ^
answers:   0     2   4   7    11 11    17
Step 3: Find total number of 'lol' by summing the number of 'lol' that end at all l.
Total = 52

lis_easy

Hint 1

The solution is O(n^2)

Hint 2 - What function to define?

f(i) = longest increasing subsequence which ends at index i

Solution

Watch this lol https://www.youtube.com/watch?v=iQP5XFeXiMQ

0-1 knapsack

Hint 1 - what function to define?

Define f(i, w) to be the maximum value that can be attained with weight less than or equal to w considering items from 1 to i.

Solution

Its a classic (NOT EASY) DP problem, do google for the solution.

housing

Good luck :)