SRM 709, D2, 250-Pointer (Robofactory)

James S. Plank

Wed Mar 8 02:06:28 EST 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: February, 2017
Competitors who opened the problem: 412
Competitors who submitted a solution: 345
Number of correct solutions: 164
Accuracy (percentage correct vs those who opened): 39.8%
Average Correct Time: 23 minutes, 33 seconds.

This problem belongs to a class of Topcoder problems that typically gets low scores for the participant. It's a problem where you have to read the description carefully and then craft a solution based on that careful reading. It doesn't fit a paradigm that you, as a computer scientist, are used to, like Depth-First-Search, or sorting. You simply have to reason through a solution.

So let's reason through a solution.

First, you can test very easily to see if a robot has given an incorrect answer. That should be your first pass -- run through the vectors, and make sure that the answer in answers[i] is correct for the number in query[i]. If it's not, then return i. Go ahead and write that code. That will solve examples 0 and 5, where a robot gave a wrong answer.

Now, if your code hasn't found the offending robot at this point, it's because all of the robots answered correctly. So now, you should run through the robots again, and determine whether they could be corrupted. This happens in one of two circumstances:

The robot is robot 0.
The robot is not robot zero, and the robot before this one had an odd number.

Make a second pass through the robots and count the number of them that could be corrupted. If that number is one, then robot 0 is the corrupted one. Otherwise, there is more than one robot that could be corrupted, so you return -1. You're done.

Go ahead and write this up. I'll include my answer below, but you should try this one on your own at this point! It's not a complex program.

My solution:

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef vector <int> IVec;
typedef vector <string> SVec;

class Robofactory {
  public:
    int reveal(vector <int> query, vector <string> answer);
};

int Robofactory::reveal(vector <int> query, vector <string> answer)
{
  int i;
  int could_be_corrupted;

  /* Pass one -- if any robots give the wrong answer, return the robot. */

  for (i = 0; i < query.size(); i++) {
    if (query[i] % 2 == 0 && answer[i] == "Odd") return i;
    if (query[i] % 2 == 1 && answer[i] == "Even") return i;
  }

  /* Pass two -- count the number of robots who could be corrupted.  This
     means that the robot is either robot 0, or the previous robot was 
     given an odd number. */

  could_be_corrupted = 0;
  
  for (i = 0; i < query.size(); i++) {
    if (i == 0 || query[i-1]%2 == 0) could_be_corrupted++;
  }

  /* If only one robot could be corrupted, it's robot 0. */

  if (could_be_corrupted == 1) return 0;

  /* Otherwise, there are multiple robots that could be corrupted, 
     so you return -1. */

  return -1;
}