USACO 2017-2018 January Contest

6 лет назад, # |

The contest should be over by now. Can anyone else confirm?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

Confirmed. "[...] as you start during the larger contest window starting the morning of Jan 19 and ending Jan 22 at 23:59 UTC-12 time" (see contest rules). Adding 4 hours, all contestants are done at 4:00 UTC-12. Now, it's 5:25 UTC-12.

How to solve gold 3?

→ Ответить

6 лет назад, # ^ |

First, notice that a string is good if and only if it has a substring consisting of K equal symbols. (That substring corresponds to the last stamp.)

I found it easier to compute the complement — the number of strings where no symbol appears more than K-1 times in a row. You can do that by finding some linear recurrences and then doing an O(N) dp.

→ Ответить

6 лет назад, # ^ |

← Rev. 4 →

Can you elaborate?

EDIT: I deduced a recurrence (see below) and will test it when USACO analysis mode opens. Thanks for the hint. Still interested in other approaches.

→ Ответить

vamaddur

6 лет назад, # ^ |

← Rev. 2 →

f(n) = (M-1)(f(n-1)+f(n-2)+f(n-3)+...+f(n-(k-1))

I found this pattern by working out a 2D DP table on paper, and I had also seen this problem prior to this contest for the two color case.

→ Ответить

6 лет назад, # ^ |

Here's another idea. Imagine an abitrary string s of length n with < k equal symbols in row (call s good). If we append a symbol x, there are two cases:

s ends with < k - 1 equal symbols or with k - 1 equal symbols and last symbol of s is different from x. In this case, new string remains good.
s ends with k - 1 equal symbols and last symbol is equal to x. Cut the last k symbols from s. We get a good string with n - k + 1 symbols. There are f(n - k + 1) such strings.

Thus, there are f(n) = M·f(n - 1) - f(n - k + 1) good strings.

→ Ответить

6 лет назад, # |

How to solve plat 2?

→ Ответить

kobortor

6 лет назад, # ^ |

Compress the edges.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

How can we prove this works? It seems like still O(n^2) worst case?

→ Ответить

6 лет назад, # ^ |

Can you construct a test case to make it even close to $\text{[math]}$ ? I tried but the worst I could get was something like $\text{[math]}$ .

→ Ответить

King

6 лет назад, # ^ |

← Rev. 2 →

Compress edges + dfs is still O(N^2) in worst case Consider the following test case

Spoiler

cout<<70000<<endl;

for(int i=2;i<70000;i+=3){

cout<<i<<' '<<1<<endl;

cout<<i<<' '<<i+1<<endl;

cout<<i<<' '<<i+2<<endl;

}

→ Ответить

i4gotmylunchih

6 лет назад, # ^ |

good point.

→ Ответить

6 лет назад, # ^ |

Have you tried this in contest and got AC or are you just saying that you think that this would work?

I came up with a weird solution out of contest that uses a Merge Sort Tree and BITs.

→ Ответить

kobortor

6 лет назад, # ^ |

I got AC with it during contest yeah.

→ Ответить

khokho

6 лет назад, # ^ |

What does “compress the edges” mean? Could you point me to some kind of tutorial on this?

→ Ответить

kobortor

6 лет назад, # ^ |

← Rev. 2 →

Compressing the edges means turning all nodes of degree 2 into a single edge with a larger weight.

For example A--B--C--D with each edge of length 1 might get compressed into A--D with length 4.

Regarding tutorial, sorry I don't know any.

→ Ответить

cheater2k

6 лет назад, # ^ |

+11

I came up with an O(nlogn) solution during the contest. (I'm not really sure about it though...)

First, let's talk about the obvious O(n²) solution. We just have to run a simple DFS in the tree with every root from 1 to n. Assume that the current root is r, let dep[u] be the depth of node u and mindist[u] be the minimum distance between a leaf in the subtree of u and u. Then we go down from the root and whenever we find a node u such that dep[u] ≥ mindist[u] we stop going down and continue the DFS progress with other nodes. Here for simplicity, let's say that "u is an optimal node for r".

Now, I will demonstrate my idea to optimize the above solution. We will find the result for node 1 first. Keep all optimal nodes for the subtree of u in an array save[u]. Suppose that we are currently located in node v, and its children are u₁, u₂, ... Then the candidates of the optimal nodes for v can be all nodes in save[u1], save[u2], ... and their direct parents. Obviously, we should choose the nodes greedily with the increasing order of the distance to node v. We can use some kind of STL like set to solve this. You may think that this is slow but there is a useful observation: a node can be an optimal node for at most 2 other nodes.

By doing that, we can easily compute the answer for node 1. To compute the answers for 2, 3, ..., n, when we run dfs(u, p) (u is the current node, p is the direct parent of the current node) we should save pair<int,int>(u, p) in a map. If we revisit the state dfs(u, p) we do not go down any further, instead, use the save[] array that we just find before. Since an edge (u, v) can be visited in two directions: (u, v) and (v, u), so this DFS progress should run approximately 2n times, I guess.

This requires a very complicated and tricky implementation. Also, I am not sure whether the solution runs in O(nlogn) because my solution is very slow in practice. If there are any counterarguments, please comment.

My code: https://pastebin.com/J2FmK10Y

→ Ответить

zeliboba

6 лет назад, # ^ |

← Rev. 2 →

Looks like node could be optimal for more than two other nodes. Consider star graph with attached paths of length 1 and 2. Central node of this graph will be optimal for central node of all attached paths length 2. But statement "Total number of optimal nodes for all vertices is linear" still could be correct.

→ Ответить

cheater2k

6 лет назад, # ^ |

Yeah, you are right... My observation is wrong. My solution cannot pass the "star graph" test case.

→ Ответить

geniucos

6 лет назад, # ^ |

I solved it in NlogN starting from the same N^2. With a couple of easy algebraic observations, I deduced a more exact way of seeing the properties that uniquely define those nodes u, and coded a nasty centroid decomposition. I don't understand the time limit/N limit. Most likely the author wasn't able to solve it in NlogN

→ Ответить

cheater2k

6 лет назад, # ^ |

+10

It sounds very interesting. Can you please explain your solution in more details?

→ Ответить

krijgertje

6 лет назад, # ^ |

← Rev. 3 →

+20

I had the same idea (centroid decomposition) but had to stop halfway during the contest, so I wasn't able to finish it. I don't think the approach is 'nasty' and actually quite like it.

The basic idea is to think of all paths starting in a node. We should count the number of paths where d[u]>=mindist[u] ONLY for the last node on the path (where d[u] is the distance to our starting node and mindist[u] is the minimum distance to a leaf).

With the centroid decomposition in a single step we consider only the paths going through the centroid. Now a path from u to v (not in the same subtree) should be counted for u iff 1) dep[u]+dep[v]>=mindist[v], 2) for all nodes on the path from u to the root dep[u]-dep[x]<mindist[x] and 3) for all nodes on the path from v to the root dep[u]+dep[x]<mindist[x]. The middle can be rewritten as dep[u]<dep[x]+mindist[x] for any proper ancestor of u and the first and last as mindist[v]-dep[v]<=dep[u]<min(mindist[x]-dep[x] where x is a proper ancestor of v). With one dfs we can precompute the ranges of depths for which a certain v can be counted and with another dfs update the answer for that subtree (first removing the subtree from the depths to be counted and re-adding it afterwards).

It seems a 'merge-small-to-large' kind of approach should also work, but (substantially) more difficult to code: Paths from one light subtree to another light subtree can be handled similarly as above. For paths from a light subtree to a heavy subtree we should do some preprocessing before going into the large subtree. For paths from a heavy subtree to a light subtree we should end the processing of a subtree with some information about the depth-ranges in it, so we can do some postprocessing after going into the large substree to handle these paths. In the end it should be possible to do all computations visiting the heavy subtree only once, so also resulting in an NlogN runtime.

→ Ответить

geniucos

6 лет назад, # ^ |

Yes, the idea was the exact same one. The approach itself is not "nasty". I was talking more about the code (specifically, my code, which was not the happiest implementation). But you're right, I may have exaggerated. Also, I'm not really sure I understood how you handle the middle condition. What I did was to prove that you don't need to make sure dep[i] > dep[x] + mindist[x] for any ancestor, but rather only for the immediate father, which significantly eases the solution.

→ Ответить

krijgertje

6 лет назад, # ^ |

← Rev. 2 →

I'm not sure which part you don't understand. Maybe my code clarifies things:

centroid decomposition [AC in 360ms]
merge-small-to-large [AC in 180ms]

→ Ответить

ainta

6 лет назад, # ^ |

I solved it with O((sum of answers) * log N). I think it is O(NlogNsqrt(N)), but I couldn't prove it.

→ Ответить

eddy1021

6 лет назад, # ^ |

+23

Considering a star graph, insert one vertex into each edge.

i.e.

The sum of answer will be O(|V|²)

→ Ответить

zeliboba

6 лет назад, # |

Who know any easy solution for plat 1? Have idea how solve it by maintaining k queues and calculate n·k dynamics using them, but this looks hard to code for me.

→ Ответить

6 лет назад, # ^ |

Use dp, with state dp[interval][skipped], the brute force transition will be another k factor, but it turns out that you only need to consider one transition (from the leftmost interval that intersects the current interval).

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

+38

I have an easy DP (I was to lazy to do the contest but it should work).

If there is an interval that covers another one fully, remove the smaller one and decrease K (obviously there is no point in saving a small interval, if we can save a larger).

After this process sort all intervals that are left by r in increasing order. For every pair i < j these inequalities will hold: l_i < l_j and r_i < r_j.

We start iterating the intervals in increasing order of their r or l. Now consider the following DP:

dp[current interval][number of removed intervals][0/1 flag showing if we have chosen interval i] = answer if we consider all intervals until "current interval" (including it).

We can easily compute dp[i][j][0] - it's simply equal to max(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0]). Now the dp[i][j][1] we will use a small observation: If we chose (not remove) interval x

and let the interval y be the leftmost interval with r_y ≥ l_x. We can safely remove all intervals in the range [y + 1;x] as they will simply won't change the answer. And the more intervals we remove from there, the less the answer will be.

From this we get that dp[i][j][1] = max(dp[p][j — (i — p)][0], dp[p][j — (i — p)][1]), where p is the leftmost interval with r_p ≥ l_i, because it's enough to consider only two case — we either will get the previous interval or won't.

The complexity will obviously be $\text{[math]}$ .

PS: Maybe some minor details like (+1 or -1 in the DP states) are wrong in the explanation as I haven't checked it, but I think one can get the general idea from reading this.

→ Ответить

My Code Without Memory Optimization (Also Need Help to Fix WAs on Cases #2 and #3)

6 лет назад, # ^ |

+19

Exactly what I did! Except I switched dp[i][j][0] and dp[i][j][1].

Passed all test cases during the contest.

→ Ответить

WhaleVomit

6 лет назад, # ^ |

I only looked at dp[i-1] instead of dp[p]. Still somehow got AC :D

→ Ответить

vamaddur

6 лет назад, # ^ |

← Rev. 3 →

@Svlad_Cjelli @radoslav11

How can one efficiently save the previous DP states for p when calculating dp[i][j][1] (assuming NK memory MLEs on USACO servers)?

→ Ответить

6 лет назад, # ^ |

NK memory was completely fine for me.

→ Ответить

minimario

6 лет назад, # ^ |

Is it possible to apply wqs on this task to solve K <= 100000 as well? (Something like, let the score for a set S of lifeguards fired be [amount we can cover + X * len(S)], and then binary search on X)?

I'm not sure if this would work, since the cost function here is linear rather than quadratic.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

I used convex hull optimization. I think that is what zeliboba was thinking of. Still only O(NK)

→ Ответить

fmqjpt

6 лет назад, # ^ |

← Rev. 3 →

How do you use convex hull trick here? The cost function doesn't look anything like a product, right?

→ Ответить

6 лет назад, # ^ |

It’s increasing and that’s what matters My code

→ Ответить

fmqjpt

6 лет назад, # ^ |

← Rev. 2 →

Wait how does this work? Doesn't convex hull trick help you find min/max among a set of lines? Or is this something else?

→ Ответить

6 лет назад, # ^ |

Convex hull trick helps you maintain the set of dp states that will be helpful at some point in a way that the best past dp state is easily found. I'm talking about the one in this video: here

→ Ответить

minimario

6 лет назад, # ^ |

This isn't a convex hull optimization, but I do think it uses it (dp[n] = dp[i] + smth * (n-i) type) but if it should work I think it will be something like N log N (maybe some more logs)

→ Ответить

geniucos

6 лет назад, # ^ |

Yes, it can be solved in NlogN. I don't know how to prove it, but it works (using alien's trick)

→ Ответить

6 лет назад, # ^ |

← Rev. 3 →

I tried to solve it using alien's trick but something is not working and I can't find out what (it works on 6 tests cases out of 10). Can someone please help me?

Code

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 200111

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

ll n, k;
pll p[maxn];
ll dp[maxn], from[maxn];
pll pre[maxn];
bool take[maxn];	// 0 - we don't take guard, 1 - we take guard
set<pll> s;

bool comp(pll a, pll b){
	if(a.fi != b.fi)
		return a.fi < b.fi;

	return a.se > b.se;
}

ll solve(ll C, bool pr){
	dp[0] = 0;
	take[0] = 0;
	from[0] = -1;
	pre[0] = mp(0, 0);

	s.clear();

	ll ind = 0;
	for(ll i = 1; i <= n; i++){
		while(ind + 1 <= n && p[ind + 1].se <= p[i].fi){
			ind++;
			s.erase(mp(dp[ind] - p[ind].se, ind));
		}

		take[i] = 0;
		dp[i] = dp[i - 1];			// we don't take this guard
		from[i] = i - 1;

		if(pr) cout << i << "  " << dp[i] << "  " << from[i] << "  " << take[i] << endl;

		pll cur;
		if(s.size()){
			cur = *(--s.end());
			if(p[i].se + cur.fi - C > dp[i]){				// we take guard (intersect with some previous one)
				take[i] = 1;
				dp[i] = p[i].se + cur.fi - C;
				from[i] = cur.se;
			}
		}

		if(pr)cout << i << "  " << dp[i] << "  " << from[i] << "  " << take[i] << endl;

		cur = pre[ind];
		if(p[i].se - p[i].fi + cur.fi - C > dp[i]){		// we take guard (doesn't intersect with some previous one)
			take[i] = 1;
			dp[i] = p[i].se - p[i].fi + cur.fi - C;
			from[i] = cur.se;
		}

		if(pr)cout << i << "  " << dp[i] << "  " << from[i] << "  " << take[i] << endl;

		s.insert(mp(dp[i] - p[i].se, i));
		pre[i] = max(mp(dp[i], i), pre[i - 1]);
	}

	ll x = n;
	ll num = 0;
	while(x > 0){		// count number of guards used in optimal solution
		num += take[x];
		x = from[x];
	}
	return num;
}

int main(){
	freopen("lifeguards.in", "r", stdin);
	freopen("lifeguards.out", "w", stdout);


	scanf("%lld%lld", &n, &k);
	for(ll i = 1; i <= n; i++)
		scanf("%lld%lld", &p[i].fi, &p[i].se);
	
	sort(p + 1, p + 1 + n, comp);

	ll mx = 0, cnt = 0;
	p[0] = mp(-1, -1);
	for(ll i = 1; i <= n; i++){
		if(mx >= p[i].se)
			continue;

		mx = max(mx, p[i].se);
		p[++cnt] = p[i];
	}

//	for(int i = 0; i <= cnt; i++)
//		printf("%lld %lld\n", p[i].fi, p[i].se);

	k -= n - cnt;
	n = cnt; 

	ll bound = n - k;
	ll l = 0, d = INF, mid, ans = 0;

	while(l <= d){
		mid = (l + d) / 2;
		if(solve(mid, 0) <= bound){
			d = mid - 1;
			ans = mid;
		}
		else
			l = mid + 1;

	}

	solve(ans, 0);

//	for(ll i = 1; i <= n; i++)
//		printf("%d %lld\n", i, dp[i]);
	
	printf("%lld\n", dp[n] + bound * ans);



	fclose(stdin);
	fclose(stdout);
	return 0;
}

→ Ответить

6 лет назад, # ^ |

Haven't looked at the DP but how are you sure that the "cost" in the aliens trick will be an integer?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

I was thinking about this but if I used doubles then the answer wouldn't be accurate. Also I remember that we could use integer cost in this problem: https://csacademy.com/contest/archive/task/or-problem/statement/

→ Ответить

6 лет назад, # ^ |

Weird. For the CS Academy problem, my solution passed during the contest but now by making the costs integers it doesn't. Also I don't understand your point of "the answer wouldn't be accurate".

→ Ответить

6 лет назад, # ^ |

← Rev. 4 →

Answer of the problem is integer. Won't answer differ because of rounding (doubles usually have precision problems)?

→ Ответить

6 лет назад, # ^ |

No, as the answer in the end is something like "DP answer" + cost * K. You know that "DP answer" is "integer — cost * K", so the end result will be really close to a integer. I get the final answer by doing rounding down of ("DP answer" + cost * K + 0.5) as you can be confident that the double precision error is less than 0.5.

→ Ответить

6 лет назад, # ^ |

Aha ok, thank you. I will change that.

→ Ответить

6 лет назад, # ^ |

I changed cost from long long to long double, but now the answer differs even more (I guess because now all dp values are long doubles). Can you please tell me what I need to change so it will work.

Code

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 200111

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

ll n, k;
pll p[maxn];
ld dp[maxn], from[maxn];
pair<ld, ll> pre[maxn];
bool take[maxn];	// 0 - we don't take guard, 1 - we take guard
set<pair<ld, ll> > s;

bool comp(pll a, pll b){
	if(a.fi != b.fi)
		return a.fi < b.fi;

	return a.se > b.se;
}

ll solve(ld C, bool pr){
	dp[0] = 0.0;
	take[0] = 0;
	from[0] = -1;
	pre[0] = mp(0.0, 0);

	s.clear();

	ll ind = 0;
	for(ll i = 1; i <= n; i++){
		while(ind + 1 <= n && p[ind + 1].se <= p[i].fi){
			ind++;
			s.erase(mp(dp[ind] - p[ind].se, ind));
		}

		take[i] = 0;
		dp[i] = dp[i - 1];			// we don't take this guard
		from[i] = i - 1;

		if(pr) cout << i << "  " << dp[i] << "  " << from[i] << "  " << take[i] << endl;

		pll cur;
		if(s.size()){
			cur = *(--s.end());
			if(p[i].se + cur.fi - C > dp[i]){				// we take guard (intersect with some previous one)
				take[i] = 1;
				dp[i] = p[i].se + cur.fi - C;
				from[i] = cur.se;
			}
		}

		if(pr)cout << i << "  " << dp[i] << "  " << from[i] << "  " << take[i] << endl;

		cur = pre[ind];
		if(p[i].se - p[i].fi + cur.fi - C > dp[i]){		// we take guard (doesn't intersect with some previous one)
			take[i] = 1;
			dp[i] = p[i].se - p[i].fi + cur.fi - C;
			from[i] = cur.se;
		}

		if(pr)cout << i << "  " << dp[i] << "  " << from[i] << "  " << take[i] << endl;

		s.insert(mp(dp[i] - p[i].se, i));
		pre[i] = max(mp(dp[i], i), pre[i - 1]);
	}

	ll x = n;
	ll num = 0;
	while(x > 0){		// count number of guards used in optimal solution
		num += take[x];
		x = from[x];
	}
	return num;
}

int main(){
	freopen("lifeguards.in", "r", stdin);
	freopen("lifeguards.out", "w", stdout);


	scanf("%lld%lld", &n, &k);
	for(ll i = 1; i <= n; i++)
		scanf("%lld%lld", &p[i].fi, &p[i].se);
	
	sort(p + 1, p + 1 + n, comp);

	ll mx = 0, cnt = 0;
	p[0] = mp(-1, -1);
	for(ll i = 1; i <= n; i++){
		if(mx >= p[i].se)
			continue;

		mx = max(mx, p[i].se);
		p[++cnt] = p[i];
	}

//	for(int i = 0; i <= cnt; i++)
//		printf("%lld %lld\n", p[i].fi, p[i].se);

	k -= n - cnt;
	n = cnt; 

	ll bound = n - k;
	ld l = 0, d = 1e14, mid, ans = 0;

	for(int r = 0; r < 100; r++){
		mid = (l + d) / 2;
		if(solve(mid, 0) <= bound){
			d = mid;
			ans = mid;
		}
		else
			l = mid;

	}

	solve(ans, 0);

//	for(ll i = 1; i <= n; i++)
//		printf("%d %lld\n", i, dp[i]);
	
	cout << (ll) (dp[n] + bound * ans + 0.5) << endl;



	fclose(stdin);
	fclose(stdout);
	return 0;
}

→ Ответить

khokho

6 лет назад, # |

plat 3?

→ Ответить

6 лет назад, # ^ |

I need this one too

→ Ответить

xaz3109

6 лет назад, # ^ |

There are 2 realizations: 1. The area being water/fertilized will always be one big region 2. The only possible way for a rectangular region to be both water and fertilized is for one sprinkler to be on the SW corner and the other one on the NE corner.

I used 2 arrays to keep track of the running minimum and maximum of the region. I also kept track of the corner/critical points (only the max) (there are redundant points that take up time to calculate). Instead of cycling through all the points for every point which takes O(N^2), I only cycle through the critical points and skip the irrelevant maxs.

In the end, I had to subtract the region that was calculated twice. My AC code

→ Ответить

6 лет назад, # ^ |

I don't think it has to be one big region — for example you could have sprinklers at (0,4), (2,6), (4,0), (6,2).

But it probably doesn't make a difference for the algorithm.

→ Ответить

6 лет назад, # ^ |

Here is my O(N) solution. It is similar to xaz3109's solution, but I used prefix sums and some math to speed things up: link

→ Ответить

joseacaz

6 лет назад, # |

Can you help me find a solution for Gold 2?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

Root the tree at Bessie's start and use DP to compute number of farmers for each subtree. Utilize the distance to nearest leaf and compare with distance from Bessie's start. Does this hint suffice?

→ Ответить

joseacaz

6 лет назад, # ^ |

So, the state for the DP will only include the node? Don't you have to also include distance from the root, which will inevitably run out of time and memory.

→ Ответить

-osdajigu-

6 лет назад, # ^ |

← Rev. 2 →

Actually, I don't think is DP. It is just a bfs traverse from Bessie's start. So, before, you should have precalculated the distance to closest leaf for each node. In the bfs, each time you arrive at a node which minimal distance from any leaf is lower than Bessie's start, you count one to answer and don't push neighbors in the queue (cause you put the farmer in that leaf and for sure Bessie can't go further).

→ Ответить

joseacaz

6 лет назад, # ^ |

It makes a lot of sense actually. To precalculate the distance from any node to its closest leaf I assume it's just a BFS from each leaf, but this would be N BFSs at worst. Any hint for this precalculation?

→ Ответить

-osdajigu-

6 лет назад, # ^ |

← Rev. 2 →

Yes, Since only you care is the minimal distance from a leaf, you can do a multisource bfs. So first push all leafs to queue with distance 0, and then just do normal bfs.

→ Ответить

WhaleVomit

6 лет назад, # ^ |

You could also observe that the number of nodes each farmer will move up is floor(depth/2), if you root the tree at Bessie's start. Then use binary lifting to efficiently calculate the kth ancestor of each leaf.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

OK. In fact, I solved it using DP. Let dp[i] denote the minimum number of farmers required for the subtree rooted at vertex i. If the distance from start to i is ≥ distance to nearest leaf from i, we have dp[i] = 1. Else, we have $\text{[math]}$ where sum is taken over all children of i.

→ Ответить

Rezwan.Arefin01

6 лет назад, # ^ |

← Rev. 2 →

I did a greedy solution, maybe over complicated it.

Lets make a DS, that can solve these queries -
1. Activate a node.
2. Find minimum distance to an active node from a given query node.
It can be done with Centroid Tree.

Now, in our problem, lets sort the leafs according to their distance from Bessie. Call them v₀, v₁, ..., v_k - 1. Now pseudo code is something like this —


for i = 0 to k - 1: 
    if(dist(bessie, v[k]) < ds.query(v[k])) 
        ans++; 
	ds.activate(v[k]);

→ Ответить

6 лет назад, # |

Exactly same with Gold 1: http://www.spoj.com/problems/ADABRANC/

By the way, how to solve Gold 3? Tried dp with inclusion-exclusion, but seems it was not enough to find solution.

→ Ответить

vamaddur

6 лет назад, # ^ |

Start reading here. :)

→ Ответить

Geothermal

6 лет назад, # ^ |

+10

Hi there, I'm the problem-writer behind Gold 1 :)

First of all, I hadn't seen this problem before writing my problem. However, because USACO Silver and Gold use very limited subsets of the material tested in programming contests, it's natural that problems will use similar ideas over time. Indeed, after I wrote the problem (but before the USACO contest), a problem on a CF round reused an extremely similar idea: http://codeforces.com/contest/915/problem/F

The similarity between these two problems is not quite so uncanny, but anyone who had solved both would surely notice that they rely on the same idea.

Moreover, it's worth noting that anyone who has studied the Silver and Gold-level material so thoroughly as to be able to find this type of thing on short notice probably is ready for promotion anyway. Any contestant who had somehow already seen this problem almost certainly did so in the process of solving a far greater number of relevant problems, in which case they'd most likely achieve promotion regardless.

My apologies for the similarity--however, as we've seen here, it is extremely difficult to create ideas that nobody has ever come up with before when we're able to use such a small subset of the contest material. Situations like this should definitely be avoided in Platinum, but for the lower divisions, they're very likely to show up simply because almost all elementary ideas have been discovered already.

→ Ответить

6 лет назад, # ^ |

Of course, it is really hard to came up with new problem with unused idea. I wrote above comment without any offense :)

→ Ответить

Geothermal

6 лет назад, # ^ |

None taken! I just wanted to clarify, especially to make it clear that the problem was not written directly as a copy of the one you linked. :)

→ Ответить

RedGrape

6 лет назад, # ^ |

Noam527 solved it with combi (not sure if PIE), maybe you can pm him

→ Ответить

Noam527

6 лет назад, # ^ |

I didn't, I just thought it was with combinatorics before I solved it.

→ Ответить

dhruvsomani

6 лет назад, # |

How do you do Gold 1?

→ Ответить

6 лет назад, # ^ |

Sort the queries by threshold and use DSU to update tree. Since number of vertices is required to be reported, store size of each set/component and union-by-size will give you AC.

→ Ответить

6 лет назад, # ^ |

Code, idea is exactly same as [user:neutron-byte] said.

int par[maxx];

void init(){
    for(int i = 1; i < maxx; i++){
        par[i] = -1;
    }
}

int Find(int node){
    return par[node] < 0 ? node : (par[node] = Find(par[node]));
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x == y) return;
    if(par[x] > par[y]) /// size(x) = -par[x] < size(y) = -par[y]
        swap(x, y);
    par[x] += par[y];
    par[y] = x;
}

int n, q, ans[maxx];
vector < pair < pair <int, int>, pair <int, int> > > v;

int main() {
    freopen("mootube.in","r",stdin);
    freopen("mootube.out","w",stdout);
    IO;
    init();
    cin >> n >> q;
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.pb ({{c, 1}, {a, b}});
    }
    for (int i = 1; i <= q; i++) {
        int k, vv;
        cin >> k >> vv;
        v.pb ({{k, 0}, {vv, i}});
    }
    sort (rall (v));
    for (int i = 0; i < n - 1 + q; i++) {
        if (v[i].F.S == 0) {
            ans[v[i].S.S] = -par[Find(v[i].S.F)];
        } else {
            Union (v[i].S.F, v[i].S.S);
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] - 1 << endl;
    }
    return 0;
}

→ Ответить

brothermax

6 лет назад, # |

Any prediction of gold-to-platinum promotion cutoff?

→ Ответить

QSDF

6 лет назад, # ^ |

I've looked and in the past years for January it seems to be 700 or below.

(Personally) I found the gold contest quite lenient on the partial credit, as I was able to get about 70% for #1 and #2 without really understanding the correct solution (probably ~700-720 total). For #3 I did an N^2 dp instead of the correct O(N) and only got the first 9/12, as I imagine many others did as well So I'm worried a relatively high amount of partial credit awarded might make the cutoff 750 or above,

Anyone else have any thoughts on the relative difficulty? This is only second gold contest for me so I'm still new

→ Ответить

brdy

6 лет назад, # ^ |

For G1 I got 9/10 with suboptimal solution :)

→ Ответить

michaelw12

6 лет назад, # |

Does anyone know how to compute continuous intervals for S1?

→ Ответить

6 лет назад, # ^ |

Make an array len[] which len[i] means how many units of i'th interval will remain from intersections to other intervals if delete i'th inverval. For calculating len[], sort intervals by R and update len[i] like sweep line. Rest is easy.

→ Ответить

rahejamehul

6 лет назад, # |

I tried to download the test cases for plat 2 but when I open test case #2, a string of seemingly random characters in a variety of languages appears. Anyone have a solution to this?

→ Ответить