SUPERMAN - Editorial

PROBLEM LINK:

Practice
Contest

Author: Varun Singh

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graph, BFS

PROBLEM:

Given a list of n songs, generate a playlist of 9 songs that satisfied the given criteria.

EXPLANATION:

#include <bits/stdc++.h>
using namespace std;

struct Song {
  int num;
  string artist;
  vector<int> next_song;
  int color;
  Song(int nm, const string &a) : num(nm), artist(a), color(-1){};
};

vector<Song*> songs;

// With 10 colors 9 artists are almost 4 times as likely to get unique colors
// as with 9 colors. Prob of failing 2000 times is less than 1/1000
const int TIMES = 2000;
const int NCOLS = 10;

/* Assign random colors 0..NCOLS-1 to all songs. */
void rnd_col(){
  map<string, int> col;
  for (vector<Song*>::const_iterator s = songs.begin(); s != songs.end(); ++s) {
    if (col.count((*s)->artist) == 0) {
      col[(*s)->artist] = rand() % NCOLS;
    }
    (*s)->color = col[(*s)->artist];
  }
}

/* last song in a playlist (prefix), pointing back to previous nodes */
struct Node {
  Song *last; // last song in playlist
  int len;    // length of playlist
  Node *prev; // previous node in playlist
  int colors;    // colors used including last
  Node(Song *lst, Node *p=0) : last(lst), len(1), prev(p), colors(1 << lst->color) {
    if (prev) {
      assert(!(colors & prev->colors));
      len = 1 + prev->len;
      colors |= prev->colors;
    }
  };
};


/* print solution (reversed following Node->prev */
void print_sol(Node *n) {
  if (n->prev) {
    print_sol(n->prev);
    cout << " ";
  }
  cout << n->last->num;
}


void solve() {
  vector<int> seen(100*(1<<NCOLS), 0);
  int gen=0;
  bool success = false;
  // try up to TIMES random NCOLS colorings then give up
  for (int t = TIMES; t && !success; --t) {
    ++gen;
    // random coloring
    rnd_col();

    // queue of nodes to expand, start with single songs
    vector<Node*> q;
    int head=0;

    for (int i=0; i < songs.size(); ++i) {
      Node *n = new Node(songs[i]);
      q.push_back(n);
    }

    // BFS until empty queue or found length 9 playlist
    while (head < q.size() && !success) {
      // pop first node n and its song s
      Node *n = q[head++];
      Song *s = n->last;
      // try all songs that can follow s
      for (int i = 0; i < s->next_song.size(); ++i) {
  Song *s1 = songs[s->next_song[i]];
  // have we used color of s1 already?
  int bit = (1 << s1->color);
  if (n->colors & bit) continue;
  // have we already pushed equivalent Node on stack?
  int sig = (s1->num << NCOLS) + (n->colors | bit);
  if (seen[sig] == gen) continue;
  // add new node to queue
  seen[sig] = gen;
  Node *n1 = new Node(s1, n);
  q.push_back(n1);
  // if last node pushed completes playlist, success and print
  if (n1->len == 9) {
    success = true;
    print_sol(n1);
    cout << endl;
    break;
  }
      }
    }
    // delete nodes allocated for this BFS
    for (int i = 0; i < q.size(); ++i) delete q[i];
  }
  if (!success) cout << "fail" << endl;
}

int main() {
  srand(12345678);
  string s;
  int N;
  int n;
  int num=0;
  for (cin >> N; N; --N) {
    cin >> s >> n;
    Song *song = new Song(++num, s);
    int m;
    for (int i=0; i < n; ++i) {
      cin >> m;
      song->next_song.push_back(m-1);
    }
    songs.push_back(song);
  }
  solve();
  return 0;
}

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.