Div 1 450: The one with houses
Ok, so you have N houses numbered from 0 to N-1 (1 to N in the problem, but I don't care). You have to build M roads connecting pairs of different cities such that if their numbers are a and b, |a-b| must not exceed K. Also, the number of roads connect to every house must be even.
Sounds complicated, until you note that the constraints are sort of low. Specially for K (less than 9).
Here is a dynamic programming sketch: First of all, imagine we were building roads in ascending order of house numbers. Which means that you first decide what roads to build for house 0, then house 1, etc.
In reality, let's focus only on roads connecting the current house to houses with a number smaller than its number - The roads connecting it to larger numbers will be dealt with when you build the roads of those houses. There will be at most K houses you can connect to.
How about remembering the parity of all of the relevant houses? Including the current one, that's only (K+1) parities to remember. The total number of different parity combinations to remember is 2^(K+1).
Thus we can just do a dynamic programming solution that remembers the parity of the last K+1 houses and then builds roads between the current house and houses with smaller numbers.
... There is a catch, and it caused me a huge delay. You have to be careful not to be counting road combinations twice. To fix this, just include also the number of the last lesser-numbered house you built a road to, and make sure to never build roads to houses with a smaller number again.
Some care is needed. When you move on to a new house, you have to make sure that the house K units behind has an even parity, because there will be no way to fix an odd parity anymore.
const int MOD = 1000000007;
// I hate long long. It is so ridiculous, why didn't they change it to just long
// already!?
typedef long long int64;
#define long int64
struct DengklekBuildingRoads
{
int K, N;
long mem[1<<9][31][31][9];
// M*N*N
int indent;
long rec(int mask, int M, int house, int ik) {
long & res = mem[mask][M][house][ik];
if (res == -1) {
res = 0;
if (M == 0) {
// Base case: no more roads to build
if ( mask == 0) {
res = 1;
} else {
res = 0;
}
} else if (house == N) {
res = 0; //could not build enough roads (another base case)
} else if (ik == K) {
// build no more roads between this house and things before it
// make sure 0-th previous house is even!
if ( (mask & 1) == 0) {
res = rec( mask >> 1, M, house+1, 0);
}
} else {
int o = house - K + ik;
if (o >= 0) {
//build a road between house and ik ?
res = 0;
int nmask = mask ^ (1<<K) ^ (1<<ik);
res += rec( nmask , M-1, house, ik);
// don't build more roads between these houses
res += rec( mask, M, house, ik+1 );
res %= MOD;
} else {
res = rec(mask, M, house, ik + 1);
}
}
}
return res;
}
int numWays(int N, int M, int K)
{
this->K = K;
this->N = N;
memset(mem, -1, sizeof(mem));
return rec(0,M, 0, 0);
}
};
#undef long
Div 1 300: The one with the chains
You have a set of up to 50 strings containing three characters each. The characters can be . or digits. Concatenate the strings together in any order, then pick a contiguous substring of digits and calculate the sum of these digits. Find the largest possible sum.
I came up with something horribly complicated for this problem. In retrospect, I can now think of a simple way to implement the same idea.
First of all, there is a special case in which the best substring will be completely inside one of the strings in the input. For example ".9." might be the best score if all the other combinations deal with a smaller sum.
Assuming you take case of that special case, then we have to deal with the case in which the string is composed of at least two links (two strings from the array). Then let's just bruteforce for all pairs of different strings that could be the left and right extreme. Let us define the score of a left extreme: The sum of the digits that are contiguous to the right side of a string. The score of a right extreme is the same but backwards (The right extreme scores of "..9", "567" and ".6." are 9, 18 and 0, respectively).
We would just need to pick the best strings for the middle part of the string. Note that all of these strings must contain no '.', thus we can just use them all (as we want the maximum result).
struct DengklekMakingChains
{
int gradeRight(string s)
{
int p = s.size()-1;
int score = 0;
while ( (p>=0) && (s[p] != '.' ) ) {
score += (s[p] - '0');
p--;
}
return score;
}
int gradeLeft(string s)
{
reverse(s.begin(), s.end());
return gradeRight(s);
}
int gradeAll(string s)
{
int best = 0;
int score = 0;
s += '.';
for_each(ch, s) {
if (*ch == '.') {
best = std::max(best, score);
score = 0;
} else {
score += (*ch - '0' );
}
}
return best;
}
int maxBeauty(vector <string> chains)
{
int best = 0;
for (int i=0; i<chains.size(); i++) {
// Consider individual links:
best = std::max( score, gradeAll(chains[i]) );
for (int j=0; j<chains.size(); j++) {
if (i!=j) { //make sure to avoid using the same string twice!
int score = gradeLeft(chains[i]) + gradeRight(chains[j]);
for (int k=0; k<chains.size(); k++) {
if ( k!=i && k!=j ) {
string s = chains[k];
if ( count(s.begin(), s.end(), '.' ) == 0) { //can use in the middle
//use it
score += gradeAll(s);
}
}
}
best = std::max(best, score);
}
}
}
return best;
}
};
//
Making sure you don't pick the same two extremes at the same time is what caused me to first do something very complicated and also caused a great deal of mistakes during the match. Without care, you can fail a test case like {"9.9", "1"} by picking the first string twice.
Challenge
I knew that 300 was tricky, but decided to go get launch during the challenge phase instead. The codes in 300 were so complicated I would not have found the mistakes anyway,
Outcome
I finished typing this once I learned that I passed both problems. Yay.
0 comments:
Post a Comment