Embercode: AI-powered software engineer course

1. Which statements about the moves table reach[k][m] in the egg drop lesson are true? Pick all that apply.

Pick every answer that is true.

reach[1][m] equals m for every number of moves mreach[2][m] equals C(m,1) + C(m,2), the triangular numbersreach[k][0] equals k, because k eggs start with k movesreach[3][4] equals 14reach[2][3] equals 3

2. What does this program print? ``

cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<long long> reach(3, 0);
    for (int move = 1; move <= 3; ++move) {
        for (int k = 2; k >= 1; --k) {
            reach[k] = reach[k - 1] + reach[k] + 1;
        }
    }
    std::cout << reach[1] << ' ' << reach[2] << '\n';
}

``

3 92 53 61 3

3. Why does fewest_drops_by_moves update the eggs from eggs down to 1?

Because the answer must be printed from the largest egg count firstBecause reach[k] needs the old reach[k - 1] from the previous move, and a downward loop still has that old valueBecause reach[0] is undefined and the loop must skip itBecause the vector is sorted in descending order

4. The lesson builds a topological order with a queue and in-degrees. Which person's name is given to that method? Write the surname only.

Type your answer.

5. What does this program print? ``

cpp
#include <iostream>
#include <vector>

struct Edge {
    int from;
    int to;
    int weight;
};

int main() {
    constexpr long long kNoPath = -1000;
    const std::vector<Edge> edges = {{0, 1, 2}, {0, 2, 5}, {1, 2, 1},
                                     {1, 4, 5}, {2, 3, 2}, {3, 4, 1}};
    std::vector<long long> dist(5, kNoPath);
    std::vector<int> parent(5, -1);
    dist[0] = 0;
    for (const Edge& e : edges) {
        if (dist[e.from] == kNoPath) {
            continue;
        }
        const long long candidate = dist[e.from] + e.weight;
        if (candidate > dist[e.to]) {
            dist[e.to] = candidate;
            parent[e.to] = e.from;
        }
    }
    std::cout << dist[4] << ' ' << parent[4] << '\n';
}

``

7 18 17 38 3

Egg drop and DAG DP