Practice: Complexity and limits
0 of 4 solved
About these problems
Apply, Connect, Reason and Stretch describe difficulty within this topic, not an official contest rating. Open any problem in any order; reading the chapter first is optional.
- 1Square budgetA routine performs exactly n*n operations. A machine budget allows b operations. Print YES if the routine fits, otherwise NO.ApplyNot started
- 2Pair iterationsA loop visits every pair of positions i, j satisfying 1 <= i < j <= n. Print how many iterations it performs.ConnectNot started
- 3Halving logStart with x=n. While x>0, record one operation and replace x by floor(x/2). Print the number of recorded operations.ReasonNot started
- 4Batch pair workloadThere are t independent batches of sizes n_i. In each batch a routine compares every unordered pair of different items once. Print the total comparisons across all batches. Items in different batches are never compared.StretchNot started