 # SUPERMAN - Editorial

Author: Varun Singh

MEDIUM

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();

vector<Node*> q;

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
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.

//