It began with issues, it had to be postponed 15 minutes. TC has been misbehaving in the technical side lately.
So, let us return to a simple contest with the usual strategy to try to solve the medium problem first.
Div1 500: PrimeCompositeGame
Let us begin with a dynamic programming solution that runs in O(N*K) time. It is kind of standard but is not fast enough. The good news is that it is possible to turn it into O(N*log(N)).
It is the usual game theory approach for dynamic programming. Let us think of a recurrence F(T, N), it will give the result (negative # of steps if first player loses, positive if he wins) in the sub-case where it is Player T's turn (for convenience the first player is player 0, and the second is 1). If there are N stones.
To evaluate a given state F(T, N), pick all the K possibilities of the stones to remove (You can remove from 1 to K stones). And find F( !T, N - removed_amount). Then player #T would pick the most convenient number of rocks to remove based on that solution. Note that some of the moves are not valid and if no valid moves exist, the player just lost.
We now need to turn it into O(N*log(N)). Just notice that when solving F(T, N), we need to consider the previous values F(! T, x) where x is between (N-K and N-1). Of them, we would need to find, depending on the player , the values of F(!T, x) that are negative or positive and also depending of the player, the maximum and minimum of those values. By using a std::set you can do this if you add the appropriate values to the appropriate set after each evaluation for a value of N. Just make sure to remove values of x that are smaller than N-K if you find them.
The following code is awful and could get plenty of fixes, but it shows the idea, I think.
bool iscomposite[474748];
int dp[2][474748];
struct PrimeCompositeGame
{
int theOutcome(int N, int K)
{
memset(iscomposite,0, sizeof(iscomposite));
for (int i=2; i<=N; i++) {
if (! iscomposite[i]) {
for (int j=i+i; j<=N; j+=i) {
iscomposite[j] = true;
}
}
}
dp[0][1] = -1;
dp[1][1] = 1;
set< pair<int,int> > primePositive[2];
set< pair<int,int> > primeNegative[2];
set< pair<int,int> > compoPositive[2];
set< pair<int,int> > compoNegative[2];
for (int n=2; n<=N; n++) {
for (int cplayer=0; cplayer<2; cplayer++) {
//player 0
if (cplayer==0) {
//look for a positive dp[!cplayer][x] in the range n-K <= x <= n-1
// if it exists, return the minimum.
bool found = false;
int pick = 0;
{
set< pair<int,int> > & tm = primePositive[!cplayer];
while(! tm.empty() ) {
set<pair<int,int> >::iterator q = tm.begin();
if ( q->second < n-K ) {
tm.erase(q);
} else {
found = true;
pick = q->second;
break;
}
}
}
// if it does not exist, return the minimum negative dp[!player][x]
if (! found ) {
set< pair<int,int> > & tm = primeNegative[!cplayer];
while(! tm.empty() ) {
set<pair<int,int> >::iterator q = tm.begin();
if ( q->second < n-K ) {
tm.erase(q);
} else {
found = true;
pick = q->second;
break;
}
}
}
if(found) {
if (dp[!cplayer][pick] < 0) {
dp[cplayer][n] = dp[!cplayer][pick] - 1;
} else {
dp[cplayer][n] = dp[!cplayer][pick] + 1;
}
} else {
dp[cplayer][n] = -1;
}
}
// player 1
if (cplayer==1) {
//look for a negative dp[!cplayer][x] in the range n-K <= x <= n-1
// if it exists, return the maximum
bool found = false;
int pick = 0;
{
set< pair<int,int> > & tm = compoNegative[!cplayer];
while(! tm.empty() ) {
set<pair<int,int> >::reverse_iterator q = tm.rbegin();
if ( q->second < n-K ) {
tm.erase( tm.find(*q) );
} else {
found = true;
pick = q->second;
break;
}
}
}
// if it does not exist, return the maximum positive dp[!player][x]
if (! found ) {
set< pair<int,int> > & tm = compoPositive[!cplayer];
while(! tm.empty() ) {
set<pair<int,int> >::reverse_iterator q = tm.rbegin();
if ( q->second < n-K ) {
tm.erase( tm.find(*q) );
} else {
found = true;
pick = q->second;
break;
}
}
}
if(found) {
if (dp[!cplayer][pick] < 0) {
dp[cplayer][n] = dp[!cplayer][pick] - 1;
} else {
dp[cplayer][n] = dp[!cplayer][pick] + 1;
}
} else {
dp[cplayer][n] = 1;
}
}
}
// add to the sets
for (int cplayer=0; cplayer<2; cplayer++) {
assert(dp[cplayer][n] != 0);
if( iscomposite[n] ) {
if (dp[cplayer][n] > 0) {
compoPositive[cplayer].insert( make_pair(dp[cplayer][n], n) );
} else {
compoNegative[cplayer].insert( make_pair(dp[cplayer][n], n) );
}
} else {
if (dp[cplayer][n] > 0) {
primePositive[cplayer].insert( make_pair(dp[cplayer][n], n) );
} else {
primeNegative[cplayer].insert( make_pair(dp[cplayer][n], n) );
}
}
}
}
cout<<dp[0][N]<<endl;
int y = dp[0][N];
if (y > 0) {
return y - 1;
} else {
return y + 1;
}
}
};
During the match I had many problems implementing this. Which should be clear by the size of the code and the amount of repetition in it. I had to debug many problems and change the code a lot during the match.
DuckAligment
I will admit that by the time I opened this problem, I was confident about my 500. Its algorithm is correct after all, and its main risk was memory/time limits and I tested the largest case.
I checked the division summary, and it seemed anything above 230 was going to be a great score and seemed doable. So, I actually scored 230 points...
In problems like this, it is best to verify that the target solution space is rather small. There are at most O(N) columns/rows. And in each column/row, the first point of the line of ducks can be one of O(N) values. This means that the final setup of ducks can be one of O(N*N), we can just iterate through them all.
Once the final position is fixed, it will either be a line of ducks in a row or in a column. We can treat each case separately and they are in fact, symmetric (After solving for rows, just rotate your logic to solve for columns). So, given a row, and the cell in that row in which the line of ducks will begin - What is the minimum cost to move the ducks to those positions?
Now, let us think about the ducks themselves. Note that since the row in each of the target cells is always the same, the vertical cost will always be the same for a duck at a row y, no matter what cell we choose it to go. (The cost is y - i, where i is the number of the picked row). So we should only care about minimizing the horizontal distances. This is solvable with a greedy approach:
Let us say we have a row of ducks:
..*.*...**..*.*.*.
(This is the row after we move each duck to a position in the row, without accounting for horizontal moves).
And we want to turn it into:
....*******.......
(The target row).
Then you have to notice that the optimal way to move the left-most duck is to the left-most target cell. The second duck to the left, should move to the second target cell to the left. And so and so. We can simply sort the ducks by horizontal coordinate and move the i-th duck in the sorted list to the i-th cell in the target setup.
For columns , do exactly the same, just sort the ducks by row instead of column.
int minimumTime(vector <string> grid)
{
int w = grid.size();
int h = grid[0].size();
int n = 0;
vector< pair<int,int> > ducks;
for (int i=0; i<w; i++) {
for (int j=0; j<h; j++) {
if (grid[i][j] == 'o' ) {
ducks.push_back( make_pair(j,i) );
}
}
}
n = ducks.size();
sort(ducks.begin(), ducks.end() );
int res = 1000000000;
// a row
for (int x=0; x<w; x++) {
for (int y=0; y+n <= h; y ++) {
int cost = 0;
for (int i=0; i<n; i++) {
cost += abs( ducks[i].second - x) + abs( ducks[i].first - (y+i) );
}
res = std::min(res, cost);
}
}
// a column
for (int i=0; i<n; i++) {
swap( ducks[i].first, ducks[i].second );
}
sort(ducks.begin(), ducks.end() );
for (int y=0; y<h; y++) {
for (int x=0; x+n <= w; x ++) {
int cost = 0;
for (int i=0; i<n; i++) {
cost += abs( ducks[i].second - y) + abs( ducks[i].first - (x+i) );
}
res = std::min(res, cost);
}
}
return res;
}
Outcome
I passed system tests on both problems and got a very good position.
The admins are considering whether to make the match rated or not. I don't think it makes any sense to cancel the ratings in this match. The expected rating change for a coder that participates in a match is 0. Therefore, coders that were unable to participate did not lose (or gain) any rating unfairly. It is lame that they had to lose the match, and I hope the admins make a new December SRM. But the objective of the ratings is to measure performance objectively, and the ratings of the match do exactly that , because they consider only the coders that participated.
3 comments :
In fact, DuckAlignment can be done much simpler. I can't prove my solution mathematically, but I kinda proved it to myself during the contest and my submission passed system tests.
Solution. First, find a point with minimal sum of distances to every duck (this can be an empty point). Save this minimal sum of distances - min_d.
Then subtract from this min_d one for second and third duck, 2 for 4th and 5th, 3 for 6th and 7th and so on. That's the answer.
You know, I was not very sure about that solution. It passed system tests, but without a more formal proof it could be just that the tests were weak.
I guess that your idea is based around the idea that you can first select the center of the line. Ok, in that case the row cost (or column cost) will be constant regardless so we end up with the same subproblem of moving ducks from various positions in a row to consecutive positions in that row. So, in theory the middle of the row will coincide with the point with the minimum sum of distances. If that is true, it probably depends on the assumption that there will be at most one duck per row/column.
Do you happen to have found a more formal proof?
Hi Vexorian in DuckAlignment , (After solving for rows,i solve for columns)
I demonstrate that reduce to find a median .
If we define X[i] = position of the duck.
then we have find a position k (the begin of the queue) that minimize this expresion min( Sum( | X[i] - (k+i) | ) ) . If we take Y[i] = X[i] - i , then the expresion convert in min( Sum( | Y[i] - k | ) ) therefore this k = median of Y.
After all this aprouch is more eficient.
Post a Comment