USACO 2017-2018 February Contest

7 years ago, # ^ |

→ Reply

Flying_Dragon_02

7 years ago, # ^ |

For more information:http://www.usaco.org/index.php?page=instructions

→ Reply

7 years ago, # |

-18

Predictions for Silver Cutoff? I got 700 exactly.

→ Reply

zscoder

7 years ago, # ^ |

+34

Contest is not over yet.

→ Reply

7 years ago, # ^ |

← Rev. 3 →

-19

Sorry

→ Reply

skipiano

7 years ago, # ^ |

+11

Please don't discuss any part of the contest until it is over. It is not allowed.

→ Reply

7 years ago, # |

The contest should be over. Can anyone confirm?

→ Reply

Benq

7 years ago, # ^ |

← Rev. 2 →

Thank you very much for an easy #2. :)

→ Reply

Aviously

7 years ago, # |

← Rev. 2 →

+58

Contest is over for everyone.

For those who competed in Platinum:

Problem 1: Slingshot

Problem 2: New Barns

Problem 3: Cow Gymnasts

→ Reply

7 years ago, # ^ |

← Rev. 5 →

+21

Very nice solution of 2. I was trying to come up with something like this (sparse table + LCA) but I did not notice all the properties of a diameter. I ended up coding offline centroid decomposition...

Every node and a query appear at a different time. You will be answering the query, using values which appeared before that query.

The idea is that for each query, you will be traversing the centroid tree (going up by centroid parents), calculate the distance from the query node to centroid and from centroid to node with max distance, in a different subtree.

In each centroid you store the vector of 2 best pairs(max distance, direct child of a centroid, through which this distance is realized) — second pair must have a different direct child than the best one, for each node in centroid component.

First, you record a distance and a direct child of a centroid, for each node within centroid component (you start dfs from each child of a centroid, calculate distances and remember the root). You record these values under different times as every node has a different arriving time. You have the best pair for each particular time and you sort these values acording to time.

Then you count best and second best pair for each prefix (the best values seen so far). We need that as we will be looking for a max among the nodes which arrived earlier than our query. It means that if we have a worse value at time j than at time i and j > i, we should use value from time i instead.

You answer each query by traversing the whole centroid tree and for each centroid get the max value for max time, which is less than the query time — upper_bound. You just need to check if the direct child of the centroid, which realizes best value, is the parent of the query node. If that is the case, use the second best value, for a different direct child. Also at the beginning you should check that the centroid appeared before the query, if this is not the case, skip it and go to the parent centroid.

Quite an overkill thow, compared to the nice, online solution...

→ Reply

7 years ago, # ^ |

← Rev. 3 →

Intended solution is n root n but I didn't notice the better way. This is also better than it...

It was supposed to be batch processing, LCA on the root N in the block for their shortest distances, and then every time the block reaches root N to perform a tree DP to update the distances for each node. But it turns out there are much better solutions.

→ Reply

P_Nyagolov

7 years ago, # ^ |

I have a solution to Slingshot which could possibly be interpreted as simpler than yours.

First of all, let's notice that the slingshot you use for a query, if any, is going to shoot you in the same direction. So we can separately consider left-to-right slingshots and queries and then right-to-left slingshots and queries.

I will explain how to solve the left-to-right case. For the right-to-left one, just swap the x and y values for all queries and slingshots which were right-to-left initially.

Consider some query (X, Y). Regarding the positioning on the number line, we can distinguish 4 cases for the optimal slingshot (A, B, T), if any:

X ≤ A ≤ B ≤ Y. In this case the cost is A - X + T + Y - B = (Y - X) + A + T - B. Since Y - X is constant for a given query, our task is to find the minimize A + T - B among all slingshots satisfying the aforementioned condition.
X ≤ A ≤ Y ≤ B. In this case the cost is A - X + T + B - Y = ( - Y - X) + A + T + B. Since - Y - X is constant for a given query, our task is to find the minimize A + T + B among all slingshots satisfying the aforementioned condition.
A ≤ X ≤ B ≤ Y. In this case the cost is X - A + T + Y - B = (Y + X) - A - B + T. Since Y + X is constant for a given query, our task is to find the minimize - A - B + T among all slingshots satisfying the aforementioned condition.
A ≤ X ≤ Y ≤ B. In this case the cost is X - A + T + B - Y = ( - Y + X) - A + B + T. Since - Y + X is constant for a given query, our task is to find the minimize - A + B + T among all slingshots satisfying the aforementioned condition.

Turns out that we can solve all four cases independently offline with the help of sweep line and segment tree for minimum.

In cases 1 and 2, we sort the queries and slingshots in order of decreasing X or A. Then we loop over all queries while also keeping a pointer of the last slingshot inserted into the segment tree. Whenever the X of the current query becomes less than or equal to the A of the next slingshot to be inserted, we simply update on position B with + A + T - B for case 1 and + A + T + B for case 2. After all updates resulting from the current query are done, we simply try to update the answer of the current query with (Y - X) + minquery(X, Y) in case 1 and with ( - Y - X) + minquery(Y, ∞)) in case 2.

Cases 3 and 4 can be handled in the same way, we just have to sort the queries and slingshots in order of increasing X and A.

The whole code isn't that long if you implement the segment tree structure once and use it for all 4 cases. It was about 200 lines of code for me, also including some long comments before all cases. Unfortunately, I delete all my codes after a contest and I have to wait for the final results before I can access my solution and post it here.

→ Reply

7 years ago, # ^ |

can I ask, why do you delete the code after contest?

→ Reply

P_Nyagolov

7 years ago, # ^ |

+10

Because for contests I have a folder Work and in there I create all A/B/C/... folders and then when the next contest comes, I have to empty the Work folder and create new folders :D Just bad practice, I don't know how I employed it :D

→ Reply

SaYami

7 years ago, # ^ |

← Rev. 2 →

Here is my AC code for Slingshot. It uses the same solution described by P_Nyagolov.

→ Reply

P_Nyagolov

7 years ago, # ^ |

Code.

→ Reply

WhaleVomit

7 years ago, # ^ |

← Rev. 4 →

I heard from bovinophile that problem 1 can also be done with a k-d tree.

PS: I used a 2d segment tree (which is O((N + M)log²N)) to do queries online for #1 but it only got 3/10. Turns out that the brute force O(NM) solution got 5/10. :(

→ Reply

radoslav11

7 years ago, # ^ |

+15

Well this is expected if you do dynamic 2D segment tree instead of the compressed offline one, because the constant in it turns out to be huge.

→ Reply

WhaleVomit

7 years ago, # ^ |

I agree, but I feel like this should get at least as much credit as brute force. :P

→ Reply

imaxblue

7 years ago, # ^ |

+16

At least you didn't spend 3 hours constant optimizing Nlog^2N for p2 and then thinking about how to remove a logN factor, to no avail.

Guess thats what happens when you make everything a function

→ Reply

WhaleVomit

7 years ago, # ^ |

Hey that's basically what I did for p1 :P

→ Reply

Franklyn_W

7 years ago, # ^ |

+18

At least you weren't 5 seconds away from a correct solution to 2. Had two cases, submitted the correct solution without having a print statement, got WA on sample, added print statement, uploaded, just as time ran out...

→ Reply

Franklyn_W

7 years ago, # ^ |

+16

And the new code gets 9 cases out of 10. Sad life.

→ Reply

AkshajK

6 years ago, # ^ |

sad :(

→ Reply

kamishogun

7 years ago, # ^ |

This is my code for Problem #2 if anyone needs it; it's pretty short and simple. My solution was inspired by this problem that I encountered before. Thanks to Aviously for giving me credit for the solution.

Code (C++11)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
constexpr int inf = 0x3f3f3f3f;

template <class T> inline void chmax(T& x, T y) {if (x < y) x = y;}
template <class T> inline void chmin(T& x, T y) {if (x > y) x = y;}
inline int LSB(int i) {return (i & -i);}

constexpr int maxn = 1e5+5;

//Par stores the root of the i'th tree
int q, n, par[maxn], p[maxn][20], level[maxn];
//First and Second node of diameter in i'th tree + diameter of i'th tree
int f[maxn], s[maxn], diameter[maxn];
char a;
int b;
vector <int> adj[maxn];

void add(int node, int cur){
    p[cur][0] = node;
    level[cur] = level[node] + 1;

    for (int j = 1; 1 << j < n; j++){
        if (p[cur][j - 1] != -1){
            p[cur][j] = p[p[cur][j - 1]][j - 1];
        }
    }
}

int lca(int x, int y){
    if (level[x] < level[y]) swap(x, y);

    int log;
    for (log = 1; 1 << log <= level[x]; log++);
    log--;

    for (int i = log; i >= 0; i--){
        if (level[x] - (1 << i) >= level[y]){
            x = p[x][i];
        }
    }

    if (x == y) return x;
    for (int i = log; i >= 0; i--){
        if (p[x][i] != -1 && (p[x][i] != p[y][i])){
            x = p[x][i], y = p[y][i];
        }
    }

    return p[x][0];
}

int dist(int a, int b){
    return level[a] + level[b] - (2 * level[lca(a, b)]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    freopen("newbarn.in", "r", stdin);
    freopen("newbarn.out", "w", stdout);

    cin >> q;
    for (int i = 0; i < q; i++){
        cin >> a >> b;
        if (a == 'B'){
            if (b != -1) {
                adj[b].push_back(++n);
                adj[n].push_back(b);
                par[n] = par[b];
                add(b, n);

                int c = par[n];
                int d1 = dist(n, f[c]);
                int d2 = dist(n, s[c]);

                if (d1 >= diameter[c] && d1 >= d2){
                    diameter[c] = d1;
                    s[c] = n;
                }
                else if (d2 >= diameter[c] && d2 >= d1){
                    diameter[c] = d2;
                    f[c] = n;
                }
            } else par[++n] = n;
        }
        else {
            if (adj[b].size() == 0) printf("%d\n", 0);
            else {
                printf("%d\n", max(dist(b, f[par[b]]), dist(b, s[par[b]])));
            }
        }
    }

    return 0;
}

→ Reply

7 years ago, # ^ |

← Rev. 2 →

I also remembered that problem but I did not notice hint 2 (in the post above) and wrote that whole centroid stuff. I am a little angry as it would have taken me 5 minutes to change that solution, instead of 2 hours to implement and 1 hour to debug the new approach...

At least got some centroid practice :)

→ Reply

kaldiuo

7 years ago, # ^ |

When adding a node and the diameter changes, why must one of the endpoints be one of the old diameter's endpoints?

→ Reply

7 years ago, # ^ |

+15

You can use well know fact (or prove it on the paper) that if you have node x, go to the farthest node y, then go to the farthest node from y, z. y-z is a diameter.

Now you have d1-d2 (diameter) and you add x. Let's assume that for parent[x], d1 was the farthest (based on the property above). Then for x also d1 is the farthest. For d1 so far d2 was the farthest and now it could be changed only to x. If that's the case, we have a new diameter.

→ Reply

fmqjpt

7 years ago, # ^ |

← Rev. 3 →

Notice that when you add a leaf u as child of a parent p the distance between all other pairs of vertices remains constant.

This means that the new diameter must either be the previous diameter v - w or be u - x for some vertex x. Suppose it was u - x. Then x must be the farthest vertex from u. But the farthest vertex from u is obviously the farthest vertex from p, which must be v or w. So thus the resulting diameter after adding u is either v - w, w - u, or u - v. Thus, when processing an add query, you can just check these three cases (using lca or whatever) in O(logn) in order to determine which of them it actually is.

→ Reply

7 years ago, # |

Silver 3? I'm pretty sure it had something to do with medians- sort of like a 1d minimum sum of distances problem with a twist.

→ Reply

amanbol

7 years ago, # ^ |

← Rev. 2 →

No, it's a ternary search.

→ Reply

radoslav11

7 years ago, # |

← Rev. 3 →

If anyone needs codes for the Platinum problems, here are my accepted solutions. I think they are the same as the ones in Aviously's comment, but I'm not sure as I haven't read his whole comment.

Problem 1: Slingshot

Problem 2: New Barns

Problem 3: Cow Gymnasts

→ Reply

7 years ago, # ^ |

← Rev. 2 →

+10

In problem 2, your solution is offline, whilst Aviously's solution is online. You don't need to read everything first, to build LCA structure.

Edit. I like that feeling when I barely manage to solve one task during the contest and later I discover that everybody here is getting max score :) Congrats!

→ Reply

7 years ago, # |

+11

Results are out!! http://www.usaco.org/index.php?page=feb18results

→ Reply

zadrga

7 years ago, # |

← Rev. 3 →

I have a problem. Code I submitted for Platinum 1 gets 1/10 at competition site. But if I download test cases and run them locally one by one, all of them are correct. When I run all them with my grader, the same problem occurs as at competition site (results are large negative numbers). Can please someone explain why this happens and how can it be avoided?

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> pii;

vector<vector<ll> > v[2], q[2], poy[2];
ll ans[maxn];
map<ll, ll> id;


struct segtree{
	ll minus[4 * maxn], plus[4 * maxn];
	multiset<ll> splus[4 * maxn], sminus[4 * maxn];

	void build(ll x, ll l, ll d){
		if(l > d)
			return;

		if(l == d){
			splus[x].clear();
			sminus[x].clear();
			splus[x].insert(INF);
			sminus[x].insert(INF);

			minus[x] = INF;
			plus[x] = INF;
			return;
		}

		int mid = (l + d) / 2;
		build(2 * x, l, mid);
		build(2 * x + 1, mid + 1, d);

		minus[x] = min(minus[2 * x], minus[2 * x + 1]);
		plus[x] = min(plus[2 * x], plus[2 * x + 1]);
	}

	void add(ll x, ll l, ll d, ll i, ll type, ll a, ll b){	// type: 1 - add, 2 - del
		if(l > d || d < i || l > i)
			return;

		if(l == d && l == i){
			if(type == 1){
				splus[x].insert(a + b);
				sminus[x].insert(a - b);
			}

			if(type == 2){
				splus[x].erase(splus[x].find(a + b));
				sminus[x].erase(sminus[x].find(a - b));
			}

			minus[x] = *sminus[x].begin();
			plus[x] = *splus[x].begin();
			return;
		}

		ll mid = (l + d) / 2;
		add(2 * x, l, mid, i, type, a, b);
		add(2 * x + 1, mid + 1, d, i, type, a, b);

		minus[x] = min(minus[2 * x], minus[2 * x + 1]);
		plus[x] = min(plus[2 * x], plus[2 * x + 1]);
	}

	ll query(ll x, ll l, ll d, ll i, ll j, ll type){	// type: 1 - plus, 2 - minus
		if(l > d || d < i || l > j)
			return INF;

		if(i <= l && d <= j){
			if(type == 1)
				return plus[x];
			
			if(type == 2)
				return minus[x];
		}

		ll mid = (l + d) / 2;
		ll ret = query(2 * x, l, mid, i, j, type);
		ret = min(ret, query(2 * x + 1, mid + 1, d, i, j, type));
	}
} leva, desna;

bool comp(vector<ll> a, vector<ll> b){
	return a[1] < b[1];
}

int main(){
	bool debug = 1;

	if(!debug){
		freopen("slingshot.in", "r", stdin);
		freopen("slingshot.out", "w", stdout);
	}
	




	ll n, m;
	scanf("%lld%lld", &n, &m);

	v[0].pb({-1000, -1000, -1});
	v[1].pb({-1000, -1000, -1});

	for(ll i = 1; i <= n; i++){
		ll a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		if(a <= b)
			v[0].pb({a, b, c});

		if(a > b)
			v[1].pb({b, a, c});
	}

	for(ll i = 0; i < m; i++){
		ll a, b;
		scanf("%lld%lld", &a, &b);
		if(a <= b)
			q[0].pb({a, b, i});

		if(a > b)
			q[1].pb({b, a, i});
	}

	for(ll z = 0; z < 2; z++){
		sort(q[z].begin(), q[z].end());
		sort(v[z].begin(), v[z].end());

		vector<vector<ll> > &query = q[z];
		vector<vector<ll> > &sl = v[z];
		n = sl.size() - 1;
		m = query.size();

		vector<ll> poy;
		for(ll i = 0; i <= n; i++)
			poy.pb(sl[i][1]);

		sort(poy.begin(), poy.end());
		poy.resize(distance(poy.begin(), unique(poy.begin(), poy.end())));

		for(ll i = 1; i <= n; i++){
			ll y = sl[i][1];	
			id[y] = lower_bound(poy.begin(), poy.end(), y) - poy.begin();
		}

		leva.build(1, 1, n);
		desna.build(1, 1, n);
		for(ll i = 1; i <= n; i++){
			ll pos = id[sl[i][1]];
			desna.add(1, 1, n, pos, 1, sl[i][2] + sl[i][0], sl[i][1]); 		// (t[i] + x[i], y[i]);
		}


		ll ind = 1;
		for(ll i = 0; i < m; i++){
			ll a = query[i][0];
			ll b = query[i][1];
			ll c = query[i][2];

			ll best = b - a;

			while(ind <= n && sl[ind][0] <= a){
				ll pos = id[sl[ind][1]];
				desna.add(1, 1, n, pos, 2, sl[ind][2] + sl[ind][0], sl[ind][1]);	// (t[i] + x[i], y[i]);
				leva.add(1, 1, n, pos, 1, sl[ind][2] - sl[ind][0], sl[ind][1]);		// (t[i] - x[i], y[i]);
				ind++;
			}

//			cout << "ok 1" << endl;

			ll pos = upper_bound(poy.begin(), poy.end(), b) - poy.begin() - 1;		// y[j] <= b
			if(pos >= 1){
				ll cost = a + b + leva.query(1, 1, n, 1, pos, 2);					// x[j] <= a
		//		cout << "leva manj" << cost << endl;
				best = min(best, cost);

				cost = -a + b + desna.query(1, 1, n, 1, pos, 2);					// x[j] > a
		//		cout << "desna manj" << cost << endl;
				best = min(best, cost);
			}


			pos = lower_bound(poy.begin(), poy.end(), b) - poy.begin();				// y[j] >= b
			if(pos <= n){
				ll cost = a - b + leva.query(1, 1, n, pos, n, 1);					// x[j] <= a
				best = min(best, cost);
		//		cout << "leva vec" << cost << endl;

				cost = -a - b + desna.query(1, 1, n, pos, n, 1);					// x[j] > a
				best = min(best, cost);
		//		cout << "desna vec" << cost << endl;
			}

			ans[c] = best;
		}
	}

	m = q[0].size() + q[1].size();
	for(ll i = 0; i < m; i++)
		printf("%lld\n", ans[i]);





	if(!debug){
		fclose(stdin);
		fclose(stdout);
	}
	return 0;
}

→ Reply

7 years ago, # ^ |

+10

Disparities between your computer and the grader, perhaps. Try running your code with warnings, checking for uninitialized variables, etc.

→ Reply

FieryPhoenix

7 years ago, # |

+21

I'm just curious, does anyone know how they determine the order to list participants with the same score: by time spent, random, or something else?

→ Reply