Question

http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf

Code

#include "cave.h"
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 5001;
int status[MAXN] , door[MAXN] , guess[MAXN];

void exploreCave(int N){
  memset(door , -1 , sizeof(door));
  for(int n = 0 ; n < N ; n++){
    int r = tryCombination(status);
    int low = 0 , high = N - 1;
    while(low != high){
      bool changed = false;
      int a = low , b = (low + high) / 2;
      for(int i = 0 ; i < N ; i++){
        if(i >= a && i <= b){
          if(door[i] != -1){
            guess[i] = status[i];
          }
          else {
            guess[i] = !status[i];
            changed = true;
          }
        }
        else guess[i] = status[i];
      }
      int K = r;
      if(changed) K = tryCombination(guess);
      if(r == n){
        if(K > n || K == -1)
          high = b;
        else low = b + 1;
      }
      else {
        if(K == n) high = b;
        else low = b + 1;
      }
    }
    door[low] = n;
    if(r == n) status[low] = !status[low];
  }
    answer(status , door);
}

Issue

While this is a working and correct code, I runs at O(NlogN) time(I think). Is there a possible way to further shorten the time complexity? This code uses binary search.

Prefer Clear Naming over using namespace std

Before I go into why

using namespace std;

is to be avoided, in the case of this program it is not needed since there is no use of any functions that derive from the std namespace in this code.

According to the MSDN website:

Namespaces are used to organize code into logical groups and to prevent name collisions that can occur especially when your code base includes multiple libraries.

A collision is when 2 different functions have the same name, the same arguement types and a similar functionallity (this is why they have the same name). Someone developing software may want to override a function such as std::cout, std::cin or they may want to override the functionallity of a class such as std::vector or std::stack. Namespaces allow these constructs to be overriden.

The use of the programming statement:

using namespace std;

hides the fact that cin, cout, vector and stack are coming from the namespace std where cin, cout,
vector and stack are used in the code. This can cause confusion of where the code is actually
coming from.

As the software becomes more complex and uses more libraries this becomes a bigger problem.

For a more detailed discussion of why it is a bad idea to use using namespace std; see this stackoverflow question and stackoverflow question.

Use Standard Libraries When Possible

Instead of writing a binary search it might be better to use the one provided by the standard template library. It saves time when writing code, and every effort has been made to make the standard library functions as efficient as possible, which means you won’t generally have to optimize it.

To use the standard library binary search you would need to include the algorithm header

#include <algorithm>

Reduce Complexity, Follow SRP

The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows:
A class should have only one reason to change.

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines well.

The void exploreCave(int N) function could be broken up into at least two functions. This code specifically seems to be a good candidate for a function.

    while (low != high) {
        bool changed = false;
        int a = low;
        int b = (low + high) / 2;
        for (int i = 0; i < N; i++) {
            if (i >= a && i <= b) {
                if (door[i] != -1) {
                    guess[i] = status[i];
                }
                else {
                    guess[i] = !status[i];
                    changed = true;
                }
            }
            else guess[i] = status[i];
        }
    }

The more separate functions there are the easier it is to understand or read the code. This also makes it easier for any programmer to maintain or debug the code.

Use Meaningful Variable Names

The variables r, K and N do not help the reader understand the code. It’s not clear at all what the variables r and K are. N is defined only if one reads the problem description, which is not currently included in the question. There are some good variable names such as guess, status, and changed although it might be better to make the array names plural. Variable naming should be consistent. The function name exploreCave is quite clear as well. Using i and j is quite common and understandable, but what is r and K? A second question is why is K needed since r does not change between it’s assignment and usage?

Use One Statement to Declare and Initialize a Single Variable

When the arrays status, door and guess are declared as when the variables low and high are declared and initialized it is done so on a single line. This makes the code harder to read and maintain. I initially missed the declaration and initialization of high. To make the code more readable and easier to maintain declare variables on separate lines in new statements.

    int low = 0;
    int high = N - 1;

is much easier to read and maintain than

    int low = 0 , high = N - 1;

You may not be the person maintaining the code, and even if you are it may be multiple years between initially writing the code and modifying it. It is important to make the code as readable as possible.