Interactive problems shortlist

[•Cosmin]

http://infoarena.ro/blog/shortlist-interactive

[•a_h1926]

1.We will use binary search among the first k elements in the first sequence and we will assume that the selected element is also the k-th element in both arrays. To check this, we will use a binary search in the second sequence to count how many elements are less than the current one. If the index of the current element and the result of the 2nd binary search sum up to k, we found the result, if it is less than k we need to seek for a greater element, and if it is greater than k we have to search for a smaller one. However, this solution assumes that the k-th element is awlays in the first sequence, which is false. To solve this case, we will do the following: if at any moment, the search gives us that there are exactly k-1 elements in both sequences less than or equal to the current one, we only need to check if the next element in the second sequence is less than the next element in the first sequence, and if yes, we found the solution (which is in the second sequence). The worst-case number of steps is logN * (1 + logM).

4.We set the current minimum and current maximum equal to the first element. Now, we take pairs of elements (2-3, 4-5, etc.). For each pair, we compare the elements to see which one is less, then we compare the smaller one with the current minimum and the greater one with the current maximum and update them. For every 2 elements we make 3 comparisons, so the total number of comparisons is 3 * N / 2.

7.We will use a torunament-like strategy. Let x and y be two distinct persons in the group. We will make both queries x->y and y->x and will analize each result. There are four possible outcomes:
I.x knows y and y knows x. Neither of them is a candidate for a celebrity (since the celebrity doesn’t knows anybody).
II.x doesn’t knows y and y doesn’t know x. Neither of them is a candidate for a celebrity (since the celebrity is knows by everybody).
III.x knows y and y doesn’t know x (the fourth case is symmetrical and can be treated the same way). In this case, x can’t be a celebrity, but y might be. If initially we have N candidates for being a celebrity and make the comparisons 1-2, 3-4, ..., (N – 1)-N (or we leave N out if N is odd), we will have at most [N/2] (or [N / 2] + 1 if N is odd) remaining candidates. We repeat the process untill we have only one candidate, for which we can check with 2 * (N – 1) queries to see if it is indeed known by everybody and doesn’t know anybody. The total number of queries is 2 * (N - 1) + 2 * N * logN.

[•Vman]

1.We will use binary search among the first k elements in the first sequence and we will assume that the selected element is also the k-th element in both arrays. To check this, we will use a binary search in the second sequence to count how many elements are less than the current one. If the index of the current element and the result of the 2nd binary search sum up to k, we found the result, if it is less than k we need to seek for a greater element, and if it is greater than k we have to search for a smaller one. However, this solution assumes that the k-th element is awlays in the first sequence, which is false. To solve this case, we will do the following: if at any moment, the search gives us that there are exactly k-1 elements in both sequences less than or equal to the current one, we only need to check if the next element in the second sequence is less than the next element in the first sequence, and if yes, we found the solution (which is in the second sequence). The worst-case number of steps is logN * (1 + logM).

I don't think you need the second binary search. Since you are at position p in the first array and all the elements are distinct you may only want to check position k-p and k-p-1 in the second array.

[•Vman]

2. If we start from (1,n) we can only move either left or down => O(n+m)

[•a_h1926]

1.We will use binary search among the first k elements in the first sequence and we will assume that the selected element is also the k-th element in both arrays. To check this, we will use a binary search in the second sequence to count how many elements are less than the current one. If the index of the current element and the result of the 2nd binary search sum up to k, we found the result, if it is less than k we need to seek for a greater element, and if it is greater than k we have to search for a smaller one. However, this solution assumes that the k-th element is awlays in the first sequence, which is false. To solve this case, we will do the following: if at any moment, the search gives us that there are exactly k-1 elements in both sequences less than or equal to the current one, we only need to check if the next element in the second sequence is less than the next element in the first sequence, and if yes, we found the solution (which is in the second sequence). The worst-case number of steps is logN * (1 + logM).

I don't think you need the second binary search. Since you are at position p in the first array and all the elements are distinct you may only want to check position k-p and k-p-1 in the second array.

I didn't pay attention to that, thanks for correcting me.

[•MciprianM]

2. If we start from (1,n) we can only move either left or down => O(n+m)

If i1 <= i2 and j1 <= j2 then a[i1][j1] <= a[i2][j2]. Then the submatrix A[1...i][1...j] has the maximum element in A[ i ][j]. So we can binary search (i, j) such that all elements in A[1...i][1...j] are less than x and then binary search x on the i+1 and j + 1 line(column). That would be O(log n + log m).

L.E.: For the first binary search we can use middle =  ((left i + right i) / 2, (left j + right j) / 2)

[•Vman]

If i1 <= i2 and j1 <= j2 then a[i1][j1] <= a[i2][j2]. Then the submatrix A[1...i][1...j] has the maximum element in A[ i ][j]. So we can binary search (i, j) such that all elements in A[1...i][1...j] are less than x and then binary search x on the i+1 and j + 1 line(column). That would be O(log n + log m).

L.E.: For the first binary search we can use middle =  ((left i + right i) / 2, (left j + right j) / 2)

Could you be more specific on this solution? Maybe it's me, but i don't think you get the right answer in O(log n + log m) worst case

[•radu_voroneanu]

3) Let us define a function f(S) that returns the smallest 2 numbers of a set S and let N be the size of S

We form pairs of neighbouring positions in S ex. (1, 2); (3, 4); ... . If N is odd we keep position N by itself.
We proceed in doing [ N / 2 ] comparisons and finding the minimum of each pair. With this minimums we forms a second set S2. We call f(S2). The minimum in S is the minimum in S2 and the second minimum in S is the minimum between f(S2).second and pair( f(S2).first ). By pair(x) we denote the other element in the pair where we find x. For the example pair(2) = 1 and pair(3) = 4.

Let T(N) the number of comparisons for a set of N elements. It can be obtained by the reccurence T(N) = floor(N / 2) + T( floor((N+1) / 2) ) + 1. T(2) = 1; Solving the reccurence  gives us T(N) = N + ceil(log2(N)) - 2 for any N >= 2.

[•claudiumihail]

Regarding 7)

I think we can do it in O(n): We start with a list of n candidates (each person is initially considered as a candidate). We take the first person from the list and do the following:

1) If x (the current person considered) knows y (the next person in the list) then x cannot be a celebrity and we move to y as the next person considered and take y from the list.

2) If x doesn't know y then y cannot possibly be a celebrity so we remove y from the list and continue with step 1) with the next person in the list z.

At the end of this process we will be left with an empty list and a single candidate. For that candidate we check that indeed everybody knows him and that he knows nobody.

Overall number of queries should: N (for the initial steps 1-2) + 2*N (for the last verification step).

[•Cosmin]

@Ciprian I can prove you need more than log n + log m queries in the worst case for problem 2) so your solution is probably wrong.

@Vlad can you detail your solution?

@Radu On problem 3) your solution works but it's easier to explain finding the 2nd best element this way: think of it as a tennis tournament. In n-1 games you find out the winner of the turnament. Now the second best guy was beaten by the best guy in the turnament. So you need to find the best guy from all the guys that the winner of the turnament won over. there will be log n losers to the winner so it takes log n -1 more games to find out the 2nd best tennis player.

[•PetcuIoan]

2) we chose the middle column, binary search on it for x, if we do not find it we have obtained 2 matrixes totaling n*m / 2 elemenst,

in the following matrix i will show what we keep, s is smaller than x b is bigger t is unknown:

tttsttt
tttsttt
tttbttt
tttbttt
tttbttt

we can easily realise that in the matrix above we actually have:

ssssttt
ssssttt
tttbbbb
tttbbbb
tttbbbb

so we continue the algoritm on the matrices formed by t's , untill we have no more matrices or we have found x, giving us O(log^3) (not sure)

3) we do the following starting from both ends:
we keep the candidate for the minimum element,and compare it with the next(we stop at the middle) when we find a element smaller than the element we have we keep the last min in a last position, at the end we compare the 2 mins, the smaller will be the 2nd min giving us N compare operations

4)we compare each element i form 1 to n/2 to i + n/2, if it gives 1 we put it to left otherwise to right(reverse for the other one)
on those 2 halves we find the min respectively the max, giving us O(3N/2)

[•Cosmin]

@Petcu
For 1) that's the cleanest solution I know. Good job! I like it more than Vlad's improvement over Andrei's solution.

For 2) you're wrong. I can prove you need at least min(n, m) queries to solve the problem. It's not trivial to prove and lots of people fall into the mistake of thinking some di. Can you guys see a proof?

3) You're wrong. Read Voroneanu's solution or my solution to see something that works in n + log n - 2 queries. I doubt one can do better.

4) Andrei has another 3n/2 - 2 solution I think. It's in line with my own.

@Claudiu your celebrity problem solution is the one I had in mind.

So we're left with
2) showing a worse case, and Vlad to explain his solution.
5), 6), 8 ), 9)

[•PetcuIoan]

2) Yea, i solved the recurence now giving a worse complexity than O(N + M) , worst case for my sol i think it's when we have T(N) = log(n) + 2 * T(N / 4)
3) Ah I assumed I could make the 2 ends meet in the minimum of the sequence, my bad.



5) we take every number with an odd index, and perform a query on it and its neighbours , after which it's easy to determine, for an element which is the middle of a querry directly and for another we have the result of it's query indirectly from the 2 nearby querys, giving n/2 querys worst case

[•Cosmin1490]

2. isn't it T(N) = 3 * T(N/2) ?
at each step u eliminate 1 out of 4 ?

LE: O(N^(log(2,3)))

[•Cosmin]

@Petcu You can solve 5) better than n/2 queries

[•Vman]

2) As i was saying, if we start from (1,n) and compare x to that element we can drop either the first line or the last column (actually if we append the last column to the first line then we can do a binary search and drop more than 1line/col, but let's stay with the worst case). So then we have to solve the same problem on a smaller matrix. Worst case is reached when we move near diagonal. I think it's pretty obvious why this works and why we get n+m.

As for the lower bound, i'll give it a shot:
If we pick the element at (x,y) we split the original matrix in 4 other ones: (x-1)x(y-1) and (n-x)x(n-y) and the other 2 ones which are similar. Suppose our number is larger than a(x,y) we can drop the first matrix. Now minimize t(n,n) = 1+t(x-1,y-1) + t(n-x, y)+t(x,n-y)

I'm mobile so excuse my lack of details

[•googolplexe]

3.

Cod:

int f(A)
{
min1=min2=A[0];
for(i = 1;i < A.length; i++)
if(A[i] <= min1)
{
min2 = min1;
min1 = A[i];
}
return min2;
}

My best try so far... 

[•MciprianM]

I found my mistake:

If i1 <= i2 and j1 <= j2 then a[i1][j1] <= a[i2][j2]. Then the submatrix A[1...i][1...j] has the maximum element in A[ i ][j]. So we can binary search (i, j) such that all elements in A[1...i][1...j] are less than x and then binary search x on the i+1 and j + 1 line(column).

Once you find (i, j), x could be in any cell that hasn't got the coordinates less than (i, j).