After I solved problem B (albeit with an overflow bug), I was not able to submit. Some time later codeforces announced the unofficial match won't be rated because unofficials weren't able to submit. At then I stopped trying. Around some time later I check back codeforces and it seems that submission is possible again. So I tried to submit B, failed, fixed and then suddenly I had only less than an hour left... I wish things went differently, I got problem D solved, kind of.
Problem B linky
Only Karts that have stools will be discounted. Now note that once you put a stool in the kart, then you would like to avoid to place any element with smaller cost. Placing elements with larger cost will not change the discount (but it might make you miss the opportunity to receive a discount on that same item in another kart). So, once you place a stool, you really should avoid placing any other item altogether. In cases where there are more karts than stools, there will be plenty of karts to place the elements you do not want to place in karts that already have stools. In the other case, where the number of stools is less than or equal to the number of karts, then there is no need to place those unwanted elements in more than one kart with a stool. Doing this will make you unable to get the discount for that stool, and in fact will make you get a discount for the least expensive item overall.
The best discount you can get will get from stools. If there are less discountable karts than stools, it is better to pick the largest stools to place into each of those karts. Thus the logic goes as follows:
- If there are less stools than karts: Pick a kart for each stools. Distribute the remaining items in the stool-less karts (make sure to place at least one item in each, but the actual distribution does not matter).
- Else, you will need to forcefully place the minimum price kart and a stool in one kart. Place the best (k-1) stools in the other karts and any other element in the kart that has the least expensive element.
Problem A linky
At first I thought you would need fancy std::sets, but since x and y are always the same for all soldiers, it gets a little simple.
Assume that you have the soldiers and vests sorted non-decreasingly.
Now, let us say you are picking the i-th soldier in such order. Since we have already made decisions for all the soldiers with a smaller a_i, then we can get rid of all vests that are smaller than a_i - x. The smallest vest greater than or equal to a_i-x will remain, note that if this vest is less than or equal to a_i+y, you can match it to the soldier, and in fact, you must match it to the soldier. Else it will be impossible to match the vest, but it might be possible to match it with a soldier with a higher preference.
Problem C linky
Seemed interesting, but submission counts suggested D was easier, and they both have the same score, so I skipped to D.
Problem D linky
Since it is a tree, it is quite dp-friendly. Assume we have
decided an arbitrary root for the tree, and such each node is either the root or has a parent and all the other adjacent nodes are children. Let us say we constructed a table dp[x][k], which returns the number of (grand) children of x at a minimum distance equal to k. Once the tree gets an arbitrary root, it is easy to calculate this table: dp[x][0] is 1 for all nodes (the node itself is at 0 units of distance), then it is sum(dp[y][k-1]) for all y that are children of x.
Let us count all the pairs (x,y) that are K edges away and x is a (Grand) parent of y. This is precisely equal to dp[x][K].
But there is a catch, sometimes the parent node x may be just part of the K-size path between two nodes that are children of it (Do not worry about parents of x, you will consider their involvement when they themselves become x).
Well, not so hard, let starting from dp[y][a] for all children y of x, you can easily count the number of paths of length a+1 that start at x and go through the y child. You can merge all such the paths of different sizes a and b such that a+b = k. This requires some trick to make sure the algorithm is not very slow (Let sum[a] be the total sum of paths of length a, sum[a] - dp[y][a] will give the number of paths that do not go through y).
This takes you to a O(n * k) algorithm. Note that the number of edges is O(n), (in the second part whilst doing all the merges, you visit all edges O(k) times).
Edit: here is the code for problem D. I mostly finished it during the match but had the typical bug of increasing the wrong counter inside a for. Then it turns out that when practice room becomes active I actually time out in the largest case. It turns out that the constraints were too large and you couldn't use memoization in the dp part. That's kind of lame.
//================================
// Program:
//
int n, k;
int u[50000]; //note that I use 0-based indices instead of 1-based
int v[50000]; //because 1-indexing is crud.
int degree[50000];
vector<int> G[50000];
int parent[50000];
void dfs(int x, int p)
{
if (parent[x] == -2) {
parent[x] = p;
for (int i=0; i<degree[x]; i++) {
dfs( G[x][i] , x );
}
}
}
// dp[j][x] how many grand children does x have away of j distance units?
int dp[501][50000];
long long solve()
{
fill(degree, degree+n, 0);
for (int i=0; i<(n-1); i++) {
degree[ u[i] ]++;
degree[ v[i] ]++;
}
for (int i=0; i<n; i++) {
G[i].resize(degree[i]);
degree[i] = 0;
}
for (int i=0; i<(n-1); i++) {
G[u[i]][degree[ u[i] ]++] = v[i];
G[v[i]][degree[ v[i] ]++] = u[i];
}
fill(parent, parent+ n, -2);
dfs(0, -1);
for (int j=0; j<=k; j++) {
for (int x=0; x<n; x++) {
if (j==0) {
//Base case, when k = 0, the only "child" at a distance 0 is
// the node x itself.
dp[j][x] = 1;
} else {
dp[j][x] = 0;
// Else the sum of dp[j-1][y] for every children y of x.
for (int i=0; i<degree[x]; i++) {
int y = G[x][i];
if (y != parent[x]) {
dp[j][x] += dp[j-1][y];
}
}
}
}
}
long long res = 0;
for (int i=0; i<n; i++) {
res += dp[k][i]; //Paths that start at node #i
// Paths that go through node #i, without using the edge connecting it
// to its parent.
long long sum[k+1];
fill(sum, sum+k+1, 0);
int active = 0;
for (int j=0; j<degree[i]; j++) {
if (G[i][j] != parent[i]) {
active++;
for (int p = 0; p <= k; p++) {
sum[p] += dp[p][ G[i][j] ];
}
}
}
if (active > 0) {
long long tem = 0;
for (int j=0; j<degree[i]; j++) {
if (G[i][j] != parent[i]) {
active++;
for (int p = 1; p <= k-1; p++) {
//a: number of paths of length p that go from node i
//and use the edge towards child j.
//b: number of paths of length k-p that go from node i
//and don't use the edge that towards child j.
long long a = dp[p-1][ G[i][j] ];
long long b = sum[k - p - 1] - dp[k - p - 1][ G[i][j] ];
tem += a*b;
}
}
}
res += tem / 2;
}
}
return res;
}
0 comments:
Post a Comment