ELHIDARR - Editorial

PROBLEM LINK:

Practice

Contest

Author: Praveen Dhinwa

Tester: Misha Chorniy

Editorialist: Animesh Fatehpuria

PROBLEM

There is a hidden sorted array of length N. Each number in the array appears exactly K times, except one element, which appears at least once, but less than K times. The task is to identify that element.

You’re given N but not K. You are allowed to ask the judge the following query: What is the value of the element at index i of the array? Identify the value of the element with frequency less than K by asking at most 60 such queries.
Constraint: 3 \le N \le 10^5.

EXPLANATION

First, we note that the amount of allowed queries is roughly 3 * \log(N). We’ll divide the solution into
two steps which collectively take 3 * \left\lceil{\log{N}}\right \rceil steps in the worst case.

Finding the value of K

This can be done using one binary search. Since we know that A is sorted, we can find the frequency of
A_1 with one binary search by finding the last occurrence of A_1 in A. This takes \left\lceil{\log{N}}\right \rceil queries. Let X denote the frequency of A_1.

From the problem statement, we can be sure that either K = X or A_1 is the odd element. We need to find out which one of the two cases it is. To do that, we can utilize O(1) more queries to compute the frequency of A_{X + 1}. This is quite simple to do so I’ll leave it as an exercise.

Solving for the odd element

Now we have K, and we have at least 2 \cdot \left\lceil{\log{N}}\right \rceil queries to spare. We present a solution that uses binary search (yet again!) to solve for the odd element. Consider maximal groups of equal values in our hidden array A. There are exactly \left\lceil{\frac{N}{K}}\right \rceil groups. Let’s call them G_1, G_2, \cdots, G_{\left\lceil{\frac{N}{K}}\right \rceil}. The problem we’re trying to solve is equivalent to finding the odd sized group i.e. the only group fo size less than K.

To do this, we can do a binary search on “groups”. We’ll assume every group is of size K (for now). Suppose we’re looking at the middle group, with index j. Look at the last element of G_{j} (which is A_{j * K}) and the first element of G_{j + 1} (which is A_{j * K + 1}). What can we say if these two quantities are equal? It means that there
exists a group of size < K to the left of group j, so we can recurse on that half. Similarly, if these two values
are unequal, we are sure that all groups upto group j have size K, so the answer lies in the right half.

Since on each step we make two queries, overall this procedure makes 2 \cdot \left\lceil{\log{N}}\right \rceil queries
which is within our limit.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

Sir I have used the same approach to solve the above question, and on analyzing it, time complexity seems to be fine O(log(n)) but on submission it gives a “time limit exceed” error. I tried it on my created dataset and it seems to work just fine.

Please help me to find where and how I am wrong.

P.S. Problem says that you will get wrong Answer" if your queries exceed 60, so that should not be the case, then how come TLE error.

Submission link : https://www.codechef.com/viewsolution/17076282
Submission no. : 17076282

It seems that you are using fflush stdout before the cout line. You should use it after the cout statement. Flush the standard output after you have printed something, rather than printing before. It could potentially be an issue. Just check if it is the case.

No, I changed it to print after cout statement. still result is the same.
tasukettedasai

Sir time complexity of my algo is O(log(n)), still i am getting TLE.
Please help me to find where and how I am wrong.

I have used cout.flush() after cout.

Link to my submission: https://www.codechef.com/viewsolution/17725568