Interactive problems shortlist

Cosmin Negruseri
16 martie 2013

Interactive problems aren't very popular in coding contests because they involve additional effort from the problem writers. But they are usually pretty creative. I've made a shortlist below. Have fun solving them in the comments section!

1. (CLRS, agora scholarships finals 2004) You are given two arrays A and B of n and m elements. The elements in each array are sorted and distinct. Find the kth element in the union of two arrays using as few comparisons as possible.
2. (CLRS, interview question) You are given a matrix A with n rows and m columns. The elements in each row and each column are distinct and sorted. One query is what’s the value of A[i][j]. Find out if element x is in the matrix using as few queries as possible.
3. (CLRS, romanian national olympiad) Given an array A of n integers. Find the 2nd minimum in the array using as few comparisons as possible.
4. (CLRS) Given an array A of n integers find out the minimum and maximum elements of the array using as few comparisons as possible.
5. (romanian ioi team selection 2006) You are given a cyclic array A of n distinct elements. query(i, j, k) returns the order of the elements A[i], A[j] and A[k] (for example a result can be A[i] < A[j] < A[k] or A[i] < A[j] > A[k]). Find a local minimum using as few queries as possible.
6. (Bulgarian OI) You are given a matrix A with n rows and m columns. An cell is considered a local minimum if it’s row and column neighbours have higher values. You can query the value of A[i][j]. Find a local minimum in as few queries as possible.
7. (folklore) A celebrity in a group of n people is a person that is known by everybody but doesn’t know anybody. Given a group of n people you can query if person x knows person y. Using the fewest number of queries possible, find out if there’s a celebrity in that group.
8. (CLRS) Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Less than n/2 chips are bad. Help the professor find the good chips using as few tests as possible. The four possible outcomes of a test are as follows:
   • Chip A says: B is good, Chip B says: A is good, Conclusion: both are good, or both are bad
   • Chip A says: B is good, Chip B says: A is bad, Conclusion: at least one is bad
   • Chip A says: B is bad, Chip B says: A is good, Conclusion: at least one is bad
   • Chip A says: B is bad, Chip B says: A is bad, Conclusion: at least one is bad
9. (martin gardner, romanian ioi team selection 98) On the bottom floor of a building there are 11 wire ends. On the top floor there are the other 11 ends of the wires. An electrician has to figure out which end above matches with which end below. To accomplish this he can do two things: 1) tie any two ends together on the same floor. 2) test for a closed circuit by applying a device to two ends. What’s a method that minimizes the number of times the electrician needs to climb the stairs.

When I ask for the minimum number of queries I'm talking about worse case behavior.