This poor match's problem set was not enjoyed by many coders. Because it was a 9:00PM match (they typically have low participation) AND there was no invitation email out.
I was going to have issues participating in this match. I had class at 8:00 PM. My original plan was to leave class early (but not too early) so I could arrive at 9:45 PM and have 30 minutes to at least solve the 250 (I keep forgetting about the 10 minutes delay that was added after the scheduled coding phase time).
Change of plans though, public transport organized a 48 hours strike, because they are evil and stuff. But due to class suspensions I was able to participate!
It seems I did fine. Writing this before the challenge phase starts. Let us see how it goes...
Div1 250: The one with patrol points
Ok, I keep seeing some very short codes for this. But mine is a little more complicated.
First of all, let us forget about minT and just count those that have distance <=maxT. In order to calculate the final result we can just find F(maxT) - F(minT). This is a normal way to remove variables and simplify a problem, seems few people actually needed this today though.
Let us try to separate X and Y, they are sort of independent, the problem is that the maxT condition requires them both. Let us say that we know the result if the cost in X-axis is exactly xMoves. Then the cost in the y-axis can be at most (maxT - xMoves).
So, what is the number of coordinates for X that we can use so that their cost is exactly xMoves? We need a tuple (a,b,c) - The x-coordinates of the points, they need to be pair-wise distinct. Also |a-b|+|b-a|+|c-a| = xMoves. (And of course, a,b,c < X)
The fun thing about the formula is, assume (a < b < c ) The result of using the formula will be: 2c - 2a = xMoves. Now asssume (a < c < b), the result of the formula is : 2b - 2a ) = xMoves. Repeat this with the 6 possible permutations for the order between a,b and c , and you will find it is always like : 2*(smallest) - 2*(largest) = xMoves. One conclusion from this is that xMoves must be even. Assuming xMoves is even, then there is only one value for (largest) for a given (smallest). Then we can pick any of the points between (smallest) and (largest) for the remaining point. Now note that for each of these triples (a,b,c) (a < b < c), 2*c - 2*a = xMoves, there are 6 different ways in which they can be used in the equation |b-a|+|c-b|+|c-a| = xMoves. Even though the statement says order does not matter when counting, this will be important later.
Now, if we want to count the tuples (a,b,c) for the Y coordinate. Note that this time we want the cost to be at most yMoves = (maxT - xMoves). But we can just use the previous logic and accumulate the number of tuples in an array.
So, we got the number of tuples (a < b < c) that are valid for X and the number of tuples (a < b < c). Is the result multiplying the tuples? I first thought so, but my results were equal to correct result/6. Order does not matter, but there are still 6 different ways to combine each X-tuple with each Y-tuple.
long acumY[20001] = {};
struct PatrolRoute
{
long countRoutes(int X, int Y, int maxT)
{
acumY[0] = 0;
for (int ymove = 2; ymove <= maxT; ymove+=2) {
acumY[ymove-1] = acumY[ymove-2];
long q = 0;
for (int a=0; a<Y; a++) {
// 2c - 2a = ymove
// c - a = ymove / 2
// c = ymove / 2 + a
// if xmove is odd, there is no way, skip
int c = ymove / 2 + a;
// b can be any a < b < c
if ( (c - a >= 2) && (c < Y) ){
q += c - a - 1;
}
}
acumY[ymove] = (q + acumY[ymove-2]) % MOD;
}
if (maxT&1) {
acumY[maxT-1] = acumY[maxT-2];
}
long res = 0;
for (int xmove=2; xmove<=maxT; xmove+=2) {
long p = 0;
// p = ways to pick a,b,c such that |a-b|+|b-c|+|a-c| = xmove
// a,b,c < X
// 2a
for (int a=0; a<X; a++) {
// 2c - 2a = xmove
// c - a = xmove / 2
// c = xmove / 2 + a
// if xmove is odd, there is no way, skip
int c = xmove / 2 + a;
// b can be any a < b < c
if ( (c - a >= 2) && (c < X) ) {
p += c - a - 1;
}
}
p %= MOD;
int ymove = maxT - xmove;
// q = ways to pick a,b,c such that |a-b|+|b-c|+|a-c| <= ymove
// a,b,c < Y
long q = acumY[ymove];
res += (p * q) % MOD;
}
// multiply by 6
res = ( (res%MOD)*6) % MOD;
return (res);
}
int countRoutes(int X, int Y, int minT, int maxT)
{
long p = countRoutes(X,Y, maxT);
long q = countRoutes(X,Y, minT-1);
cout << p << " ;"<<q<<endl;
return (int)( (p - q + MOD) % MOD );
}
};
#undef long
// BEGIN KAWIGIEDIT TESTING
Div1 500: The one with the dictionary
After I finished 250, I noticed that nika had already solved both problems. Somehow this gave me the vibe that 500 was doable.
The other clue was that there are at most 16 words. So, exponential time dp? I would say yes, but something that was complicating things was the length of the words.
Not that much. You can represent the state as a subset of the words. Let me explain.
Let us say you pick one of the positions for the first element of the permutation. Then all the words that have the smallest character in this position are candidates for the lexicographically-first word. These words make a new sub-set.
But just the subset does not seem enough, how would you know which letters you picked? - That's not so hard, actually. If in any position, all the words in the sub-set have the same character, then that position was already picked. We just need to pick the remaining positions.
Thus the solution goes like this. F(set) returns an array of n elements with the probability each word is the first in the sorted list, given that the current candidates are those in the set, which means that any character positions they have in common has already been picked for p[]. The recursion step involves picking a new position, finding all the words that have the smallest character in this position (a new subset). Solve F(subset), multiply probabilities in F(subset) with the probability the position is picked in the permutation and add those results for F(set).
This is the best I can do to explain for now, sorry.
bool sameChar[1<<16][50];
struct StrangeDictionary2
{
int n, len;
vector<string> words;
double dp[1<<16][16];
bool visited[1<<16];
void rec(int mask) {
if (visited[mask]) {
return;
}
visited[mask] = true;
int t = 0;
for (int i = 0; i < len; i++) {
t += (! sameChar[mask][i]);
}
if (t == 0) {
// base case?
assert( __builtin_popcount(mask) == 1);
for (int i=0; i<n; i++) {
if (mask & (1<<i)) {
dp[mask][i] = 1.0;
}
}
} else {
for (int i = 0; i < len; i++) if (! sameChar[mask][i]) {
// pick this position as the next character in permutation...
// Find the subset of {mask} that has the smallest character
// in this position.
char minchar = 'z'+1;
int nmask = 0;
for (int j=0; j < n; j++) if ( (1<<j) & mask ) {
if ( words[j][i] < minchar ) {
minchar = words[j][i];
nmask = 0;
}
if ( words[j][i] == minchar ) {
nmask |= ( 1 << j);
}
}
assert(nmask);
// solve for the subset:
rec(nmask);
// add probabilities
for (int j=0; j<n; j++) {
dp[mask][j] += dp[nmask][j];
}
}
for (int i = 0; i < n; i++) {
// multiply by the probability to pick each of the positions (1/t)
dp[mask][i] /= t;
}
}
}
vector <double> getProbabilities(vector <string> words)
{
this->words = words;
n = words.size();
len = words[0].size();
for (int mask=0; mask<(1<<n); mask++) {
for (int i=0; i<len; i++) {
sameChar[mask][i] = true;
char ch = '?';
for (int j=0; j<n; j++) {
if (mask & (1<<j)) {
char ch2 = words[j][i];
if ( ch == '?') {
ch = ch2;
} else if (ch != ch2) {
sameChar[mask][i] = false;
}
}
}
}
}
memset(visited, 0, sizeof(visited));
memset(dp, 0, sizeof(dp));
// In the main case, all the words are in the set:
rec( (1<<n) - 1);
vector<double> res(n);
for (int i=0; i<n; i++) {
res[i] = dp[(1<<n) - 1][i];
}
return res;
}
};
The rest
I finished these problems faster than usual. Paranoia about having made a lame mistake was inevitable. I spent all time making sure there is no mistake anywhere.
Challenge phase started and Smylic challenged forest's 500 very fast. I was scared, but it turns out it was just a blind challenge he made after noticing forest submitted in the last minute.
Passed system tests! I bet that although this is one of my best matches in months, I will not even come close to recovering my rating after last match's awful day.
0 comments:
Post a Comment