Analysis: Farmer John has no Large Brown Cow, by Brian Dean

The process of solving this problem is described in the video above; the final code is shown below.

As a note, the code below could be written so it runs even faster (not necessary here though since the limits were quite small). For example, we could have pre-computed the results of the num_choices() function and stored them in an array, to avoid calling this function over and over to compute the same thing (this is a central idea behind the more advanced technique of "dynamic programming"). Also, instead of stepping k forward one step at a time until we find the right value (which takes at most N steps), we could also have performed a binary search for the right value (which would have taken at most log N steps). Similarly, we could reduce the complexity of the num_before_on_fj_list() function from O(N) to O(log N) by pre-sorting FJ's list and then binary searching it to find the part of the list whose entries are less than s.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#define MAX_A 30
#define MAX_N 100
using namespace std;

int N, K, Npos;
int Nadj[MAX_A];
string adj[MAX_A][MAX_N];
string fj_list[MAX_N];

bool adjective_already_appears(int pos, string a)
{
  for (int i=0; i<Nadj[pos]; i++)
    if (adj[pos][i] == a) return true;
  return false;
}

int num_choices(int pos1, int pos2)
{
  int total = 1;
  for (int p=pos1; p<=pos2; p++)
    total *= Nadj[p];
  return total;
}

string get_kth_cow(int k)
{
  string s = "";
  for (int p=0; p<Npos; p++) {
    if (p>0) s = s + " ";
    s = s + adj[p][k / num_choices(p+1, Npos-1)];
    k = k % num_choices(p+1, Npos-1); 
  }
  return s;
}

int num_before_on_fj_list(string s)
{
  int total = 0;
  for (int i=0; i<N; i++)
    if (fj_list[i] <= s) total++;
  return total;
}

int main(void)
{
  ifstream fin("nocow.in");
  fin >> N >> K;
  for (int i=0; i<N; i++) {
    string farmer, john, has, no, a;
    fin >> farmer >> john >> has >> no >> a;
    int pos = 0;
    fj_list[i] = "";
    while (a != "cow.") {
      if (pos > 0) fj_list[i] += " ";
      fj_list[i] += a;
      if (!adjective_already_appears(pos, a)) {
        adj[pos][Nadj[pos]] = a;
        Nadj[pos]++;
      }
      pos++;
      fin >> a;
    }
    Npos = pos;
  }
  fin.close();

  for (int pos=0; pos<Npos; pos++) 
    sort (adj[pos], adj[pos]+Nadj[pos]);

  int k = K-1;
  while (k - num_before_on_fj_list(get_kth_cow(k)) < K-1)
    k++;

  ofstream fout("nocow.out");
  fout << get_kth_cow(k) << "\n";
  fout.close();

  return 0;
}