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!

# (CLRS, agora scholarships 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.

# (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.

# (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.
# (CLRS, romanian national olympiad) Given an array A of n integers. Find the 2nd minimum in the array using as few comparisons as possible.
# (CLRS) Given an array A of n integers find out the minimum and maximum elements of the array using as few comparisons as possible.
# (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.

# (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. One query is what is the value of A[i][j]. Find a local minimum in as few queries as possible.

# (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.

# (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.
# (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

private

protected

8810