Dashboard - Qualification Round 2008 - Google Code Jam
The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine's name, the universe does implode!
To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they're received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.
Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.
Each case starts with the number S -- the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.
The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.
X. http://www.cnblogs.com/clive/archive/2009/08/13/Google_code_jam_2008_QR_SavingtheUniverse.html
#define Rep(i,n) for (int i(0),_n(n); i<_n; ++i)
int main()
{
int T;
//freopen("..\\s.in","r",stdin);
//freopen("..\\s.out","w",stdout);
scanf("%d", &T);
Rep(t, T) {
int S;
scanf("%d", &S);
string q;
getline(cin, q);//a unread '\n' in scanf
Rep(i, S) {
getline(cin, q);
}
int Q;
scanf("%d", &Q);
getline(cin, q);
stdext::hash_set<string> st;
int count = 0;
Rep(i, Q) {
getline(cin, q);
if (st.find(q) == st.end()) {
if (st.size() == S-1) {
st.clear();
count++;
}
st.insert(q);
}
}
printf("Case #%d: %d\n", t+1, count);
}
}
X. Another DP Solution:
Def. Cost[k][i] as the min switches
when k queries come and current search engine is i
0<=i<=S
0<=k<=Q
1. Optimal: if i!=id[k]: Cost[k][i]=min{..., Cost[k-1][i-2]+1, Cost[k-1][i-1]+1, Cost[k-1][i], Cost[k-1][i+1]+1, Cost[k-1][i+2]+1,...}
else: Cost[k][i]=min{..., Cost[k-1][i-2]+1, Cost[k-1][i-1]+1, Cost[k-1][i+1]+1, Cost[k-1][i+2]+1,...}
2. Init: Cost[0][i]=0 static Scanner sc = new Scanner(System.in);
public static void main(String[] args){
int n = Integer.parseInt(sc.nextLine());
for(int id = 1; id <= n; id++){
int s = Integer.parseInt(sc.nextLine());
String[] engines = new String[s];
for(int i = 0; i < s; i++) engines[i] = sc.nextLine();
int q = Integer.parseInt(sc.nextLine());
String[] queries = new String[q];
for(int i = 0; i < q; i++) queries[i] = sc.nextLine();
int[][] table = new int[q + 1][s];
for(int i = 1; i <= q; i++) Arrays.fill(table[i], Integer.MAX_VALUE);
for(int i = 0; i < q; i++){
for(int j = 0; j < s; j++){
if(table[i][j] < Integer.MAX_VALUE){
for(int k = 0; k < s; k++){
if(!queries[i].equals(engines[k])){
table[i + 1][k] = Math.min(table[i][j] + (j == k ? 0 : 1) , table[i + 1][k]);
}
}
}
}
}
int res = Integer.MAX_VALUE;
for(int j = 0; j < s; j++){
res = Math.min(table[q][j], res);
}
if(res == Integer.MAX_VALUE) throw new RuntimeException();
System.out.printf("Case #%d: %d%n", id, res);
}
}
Read full article from Dashboard - Qualification Round 2008 - Google Code Jam
Problem
The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share... It is true! Please don't try it, or tell anyone. All right, maybe not. We are just kidding. The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine's name, the universe does implode!
To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they're received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.
Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.
Input
The first line of the input file contains the number of cases, N. N test cases follow. Each case starts with the number S -- the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.
The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.
In the first case, one possible solution is to start by using Dont Ask, and switch to NSM after query number 8.
For the second case, you can use B9, and not need to make any switches.
For the second case, you can use B9, and not need to make any switches.
X. http://www.cnblogs.com/clive/archive/2009/08/13/Google_code_jam_2008_QR_SavingtheUniverse.html
#define Rep(i,n) for (int i(0),_n(n); i<_n; ++i)
int main(){ int T; //freopen("..\\s.in","r",stdin); //freopen("..\\s.out","w",stdout); scanf("%d", &T); Rep(t, T) { int S; scanf("%d", &S); string q; getline(cin, q);//a unread '\n' in scanf Rep(i, S) { getline(cin, q); } int Q; scanf("%d", &Q); getline(cin, q); stdext::hash_set<string> st; int count = 0; Rep(i, Q) { getline(cin, q); if (st.find(q) == st.end()) { if (st.size() == S-1) { st.clear(); count++; } st.insert(q); } } printf("Case #%d: %d\n", t+1, count); }}X. Another DP Solution:
Def. Cost[k][i] as the min switches
when k queries come and current search engine is i
0<=i<=S
0<=k<=Q
1. Optimal: if i!=id[k]: Cost[k][i]=min{..., Cost[k-1][i-2]+1, Cost[k-1][i-1]+1, Cost[k-1][i], Cost[k-1][i+1]+1, Cost[k-1][i+2]+1,...}
else: Cost[k][i]=min{..., Cost[k-1][i-2]+1, Cost[k-1][i-1]+1, Cost[k-1][i+1]+1, Cost[k-1][i+2]+1,...}
2. Init: Cost[0][i]=0 static Scanner sc = new Scanner(System.in);
public static void main(String[] args){
int n = Integer.parseInt(sc.nextLine());
for(int id = 1; id <= n; id++){
int s = Integer.parseInt(sc.nextLine());
String[] engines = new String[s];
for(int i = 0; i < s; i++) engines[i] = sc.nextLine();
int q = Integer.parseInt(sc.nextLine());
String[] queries = new String[q];
for(int i = 0; i < q; i++) queries[i] = sc.nextLine();
int[][] table = new int[q + 1][s];
for(int i = 1; i <= q; i++) Arrays.fill(table[i], Integer.MAX_VALUE);
for(int i = 0; i < q; i++){
for(int j = 0; j < s; j++){
if(table[i][j] < Integer.MAX_VALUE){
for(int k = 0; k < s; k++){
if(!queries[i].equals(engines[k])){
table[i + 1][k] = Math.min(table[i][j] + (j == k ? 0 : 1) , table[i + 1][k]);
}
}
}
}
}
int res = Integer.MAX_VALUE;
for(int j = 0; j < s; j++){
res = Math.min(table[q][j], res);
}
if(res == Integer.MAX_VALUE) throw new RuntimeException();
System.out.printf("Case #%d: %d%n", id, res);
}
}
Read full article from Dashboard - Qualification Round 2008 - Google Code Jam
