Small cases, greedy and proof

Questions 1 to 5 of 7

1. 1. An AI proposes a greedy for the exactly-k excedances problem. Its code prints the sample answer for 5 2 correctly. What should you do next?

   Submit it, since it passed the sampleRun it against a brute force on many small inputs, and keep the smallest failing input as the counterexampleAdd more large random inputs and check only the running timeAsk the AI to explain the greedy in more words
2. 2. The tempting greedy prints 3 2 1 for n = 3 and k = 2. How many excedances does that output have?

   Type a number.

3. 3. Your bakery solution reads each job with this line, but the input gives each line as t d (service time, then deadline): ``cpp for (auto &[d, t] : jobs) cin >> d >> t; `` What goes wrong?

   The first number is stored as the deadline and the second as the time, so the feasibility check uses swapped values on lines where they differNothing, because the names in the brackets do not affect what cin readsThe program does not compile, because cin cannot read into a structured bindingThe 64-bit total overflows, but only on the largest input
4. 4. Which of these are proof habits the lesson teaches?

   Pick every answer that is true.

   Exchange argument: swap pieces of another solution, one at a time, until it matches yours without getting worseLoop invariant: a statement that is true before the loop, stays true after each pass, and so holds at the endThe sample passed, so the greedy is proven correctBounds check: write the largest value each variable can reach, and check that its type can hold it
5. 5. Your fast solution prints 1 on a small input and the brute force prints 2. Which step comes first?

   Average the two answers and submit the middle valueSubmit the fast solution, since fast code is usually rightShrink the input and trace both programs by hand until you find the step where they part waysIncrease n, since larger inputs usually settle a disagreement