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;
string fj_list[MAX_N];

{
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++)
}

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++;
}

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;
}
pos++;
fin >> a;
}
Npos = pos;
}
fin.close();

for (int pos=0; pos<Npos; pos++)