Algorithmic Thinking: A Problem-Based Introduction Homepage for the book Algorithmic Thinking: A Problem-Based Introduction

Solving a USACO Problem, MooTube Silver

Hi everyone,

I recently found a USACO problem that fits in really well with the material from Chapter 4. I included in the book one of my favourite USACO problems, but there are so many more to look at.

… like this one! It’s a graphs problem, and you can use breadth-first search to solve it.

(True but pointless story: USACO problems almost all deal with cows. So I tried to sneak the word encownter into the book. I got it past a few people but eventually it was caught. I pushed back – gotta know what’s worth fighting for, eh? – but, nope, no go. Next time I have to slip this kind of thing into the book riiiiight before it goes to print :) )

The problem is called MooTube, and it’s from the Silver January 2018 contest.

Please read the problem. Then close my blog! Yeah, for real… close it. You can do this. Keep in mind what you learned from the Book Translation problem that we worked through in Chapter 4. For those who don’t have access to the book: don’t worry, the code for the book is all here in this code archive.

You can start with the code for Book Translation, and modify it to arrive at a solution to MooTube. In fact that’s just what I did!

Don’t worry if you get stuck here. I’ve provided a solution below, so you’re not going to leave this problem without being able to directly connect it to what you learned in the book. Getting stuck can be a very productive learning experience, because it zones you in on exactly what you need to learn next. So, give it a good try, and then, once your ready, see below for my solution.

Here’s the code I came up with.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VIDEOS 5000

typedef struct edge {
  int to_video, relevance;
  struct edge *next;
} edge;

typedef int board[MAX_VIDEOS + 1];
typedef int positions[MAX_VIDEOS + 1];


// Return 1 if to_video is added as a new position, 0 otherwise.
int add_position(int from_video, int to_video,
                 positions new_positions, int *num_new_positions,
                 board min_moves) {
  if (min_moves[to_video] == -1) {
    min_moves[to_video] = 1 + min_moves[from_video];
    new_positions[*num_new_positions] = to_video;
    (*num_new_positions)++;
    return 1;
  }
  return 0;
}

int solve(edge *adj_list[], int relevance, int video, int num_videos) {
  static board min_moves;
  static positions cur_positions, new_positions;
  int num_cur_positions, num_new_positions;
  int i, from_video;
  int total = 0;
  edge *e;
  for (i = 1; i <= num_videos; i++) {
    min_moves[i] = -1;
  }
  min_moves[video] = 0;
  cur_positions[0] = video;
  num_cur_positions = 1;

  while (num_cur_positions > 0) {
    num_new_positions = 0;
    for (i = 0; i < num_cur_positions; i++) {
      from_video = cur_positions[i];
      e = adj_list[from_video];

      while (e) {
        if (e->relevance >= relevance) {
          if (add_position(from_video, e->to_video,
                           new_positions, &num_new_positions, min_moves))
            total++;
        }
        e = e->next;
      }
    }

    num_cur_positions = num_new_positions;
    for (i = 0; i < num_cur_positions; i++)
      cur_positions[i] = new_positions[i];
  }
  return total;
}

int main(void) {
  static edge *adj_list[MAX_VIDEOS + 1] = {NULL};
  int i, num_videos, num_queries, from_index, to_index, relevance, video, result;
  edge *e;

  freopen("mootube.in", "r", stdin);
  freopen("mootube.out", "w", stdout);

  scanf("%d%d", &num_videos, &num_queries);

  for (i = 0; i < num_videos - 1	; i++) {
    scanf("%d%d%d", &from_index, &to_index, &relevance);
    e = malloc(sizeof(edge));
    if (e == NULL) {
      fprintf(stderr, "malloc error\n");
      exit(1);
    }
    e->to_video = to_index;
    e->relevance = relevance;
    e->next = adj_list[from_index];
    adj_list[from_index] = e;
    e = malloc(sizeof(edge));
    if (e == NULL) {
      fprintf(stderr, "malloc error\n");
      exit(1);
    }
    e->to_video = from_index;
    e->relevance = relevance;
    e->next = adj_list[to_index];
    adj_list[to_index] = e;
  }

  for (i = 0; i < num_queries; i++) {
    scanf("%d%d", &relevance, &video);
    result = solve(adj_list, relevance, video, num_videos);
    printf("%d\n", result);
  }

  return 0;
}

Just a few notes here that I’d like to highlight as differences from Book Translation:

Thank You!

I hope you were able to make a lot of practice here! For more, check out the little collection of exercises that I’ve posted.

Written on January 20th, 2021 by Daniel Zingaro
Feel free to share!

You may also enjoy: