Further optimize from top solution, it shows that i can be done in just 8
secs:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <hash_map>
#include <hash_set>
#include <exception>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
#include <sstream>
using namespace std;
using namespace stdext;
#define maxj 20000000 //magic number, maybe someone could explain this?
char h[11][maxj];
char buffer[100000];
int minimum[2048];
int base[10];
//adopt the best solution
char happy(int n, int base)
{
if (h[base][n] >=0)
return h[base][n];
h[base][n] = 0;
int m = n;
int k;
int next = 0;
while (m)
{
k=m % base;
m/=base;
next += k*k;
}
return h[base][n] = happy(next, base);
}
//convert array of bases into a bitmap
int basetoi(int* base, int size)
{
int ans = 0;
for (int i=0; i<size; i++)
{
ans |= (1<<base[i]);
}
return ans;
}
//this function return the maximum result from subset of bases previously
done
//e.g. now bases = {2,5,7,10}, previously we have done {2,5}, {2,10},
{5,7,10} (only subsets are considered), surely the solution will be larger
than the max(solution of these subsets)
int getmin(int b)
{
int ans = 2;
for (int i=0; i<2048; i++)
{
if ((b & i) == i && minimum[i] > ans)
ans = minimum[i];
}
return ans;
}
int main()
{
freopen("A-large.in", "r", stdin);
freopen("A-large.out", "w", stdout);
for (int i=0; i<11; i++)
for (int j=0; j<maxj; j++)
h[i][j] = -1;
for (int i=0; i<11; i++)
h[i][1] = 1;
for (int i=0; i<2048; i++)
minimum[i]=-1;
string s;
int T;
int pre=0, pst;
cin >> T ;
cin.ignore();
int b;
for (int i=1; i<=T; i++)
{
//read bases
cin.getline(buffer, 1000);
s.assign(buffer);
pre = 0;
pst = s.find(" ", pre);
int size=0;
while (pst != -1)
{
int ii = atoi(s.substr(pre, pst - pre).c_str());
base[size++] = ii;
pre = pst + 1;
pst = s.find(" ", pre);
}
pst = s.length();
int ii = atoi(s.substr(pre, pst - pre).c_str());
base[size++] = ii;
bool state;
int k;
//check whether the bases are done before
b = basetoi(base, size);
if (minimum[b] > 0)
k = minimum[b];
else
for (k=getmin(b); ;k++) //the trick here: based on previous cases, find a
higher starting point instead of 2
{
state = true;
for (int j=0; j<size; j++)
{
if (happy(k,base[j]) == false)
{
state = false;
break;
}
}
if (state)
break;
}
minimum[b] = k;
cout << "Case #" << i << ": " << k << endl;
}
return 0;
}
On Sun, Sep 13, 2009 at 4:57 PM, Nitin Kumar <nitinkumar...@gmail.com>wrote:
>
> It took my system to work on the large set around 3 and half hrs...
> yep... I used python.. and lists.. that might be the case also!!!
> but.. some of those who have made it through.. their code also took 14
> minutes!! after some optimization.. I was able to run it within 6
> mins...
> but.. all after.. the 1A round ended... :-(
>
> Nitin Kumar
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to google-code@googlegroups.com
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
