Have just solved problem A to E, loved them so far. Haven't tried
EDIT: just found out that the official tutorial has been released, and it looks really good!
Problem A
Problem Statement:
500A - New Year Transportation
Solution:
Wow, a pretty intimidating problem A!
The idea is very straight forward, since \(a_i\) is actually a representation of a directed edge connecting vertex \(i\) with \(i+a_i\). Simply run a DFS from node 1 and return YES if we reached the destination node.
Implementation:
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; int a[50000]; int vis[50000]; int N, T; bool ok; void dfs(int u){ if(ok) return; if(u == T) { ok = true; return; } vis[u] = 1; if(vis[a[u]+u])return; dfs(a[u]+u); } int main(){ scanf("%d%d", &N, &T); for(int i=1;i<=N;++i){ scanf("%d", &a[i]); } ok = false; dfs(1); if(ok) printf("YES\n"); else printf("NO\n"); return 0; }
Problem B
Problem Statement:
500B - New Year Permutation
Solution:
A nice problem! We can represent the swapping rules as a graph, where we connect node i and j iff \(A_{i,j} = 1\). Then the most important observation to make here is that: if there exist a path between node i and j on the graph, then we can swap \(p_i\) and \(p_j\) using a sequence of swapping operations. Therefore for a set of nodes in a connected component, we can in effect place swap them freely with each other. Furthermore, we can also conclude that elements in a connected component cannot leave that component.
Hence to come up with the prettiest permutation, for each connected components on the graph, we can simply sort the elements belonging to that particular component in increasing order and place them together accordingly.
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; int N; int p[303]; int a[303]; int vis[303]; vector<vector<int> > adj; vector<int> val; vector<int> pos; void dfs(int u){ vis[u] = 1; pos.push_back(u); val.push_back(p[u]); for(int i=0;i<adj[u].size();++i){ int v = adj[u][i]; if(vis[v])continue; dfs(v); } } int main(){ int u; scanf("%d", &N); for(int i=0;i<N;++i){ scanf("%d", &p[i]); } adj = vector<vector<int> > (N+3); for(int i=0;i<N;++i){ for(int j=0;j<N;++j){ scanf("%1d", &u); if(u) adj[i].push_back(j); } } for(int i=0;i<N;++i){ if(vis[i])continue; val.clear(); pos.clear(); dfs(i); sort(val.begin(), val.end()); sort(pos.begin(), pos.end()); for(int i=0;i<val.size();++i){ a[pos[i]] = val[i]; } } for(int i=0;i<N;++i){ if(i!=0)printf(" "); printf("%d", a[i]); } printf("\n"); return 0; }
Problem C
500C - New Year Book Reading
Solution:
At first I thought we need to come up with some DP idea to solve this problem, but as it turns out there actually a way to solve this problem greedily:
1. If we don't need to read the book, then we just push the book to the bottom of the stack. So only books that appears on the reading list will ever be considered in our algorithm.
2. If we are to read a book that has never been read before, then it must appear at the highest possible position.
With that we have the following implementation:
#include <iostream> #include <cstdio> #include <algorithm> #include <deque> using namespace std; deque<int> st; int w[503]; int N, M; int main(){ scanf("%d %d", &N, &M); for(int i=1;i<=N;++i){ scanf("%d", &w[i]); } int b; int ans = 0; for(int i=0;i<M;++i){ scanf("%d", &b); bool found = false; int val = 0; for(int j=0;j<st.size();++j){ if(b == st[j]){ found = true; st.erase(st.begin() + j); break; } val += w[st[j]]; } ans += val; st.push_front(b); } printf("%d\n", ans); return 0; }
Proof... I will think of a proof for the correctness when I have the courage :)
Problem D
500D - New Year Santa Network
Solution:
I like this problem :D
Firstly, notice that the roads connecting the cities can be represented as a weighted tree. To solve this problem, we need to make use the linearity of expectation:
The expectation of the length of Santa's path = sum of \(2l_i p_i\), where \(l_i\) is the length of a path, and \(p_i\) is the probability of the path being on the Santa's path. Why times two? Because on each of Santa network, if we visit \(c1, c2,c3\) and back to \(c1\), that i-th path will be crossed twice. So the problem now boils down to finding the probability that i-th path will be on Santa's network.
Here notice that each endpoints (u,v) of that path forms a tree. So if \(c1,c2,c3\) are chosen such that one of them are on different tree, then path i will be on the network. To calculate all such probabilities in \(O(N)\), run DFS from one of the leaves of the tree and maintain the information about the sizes of the sub trees. Then once we have the information about the sizes of the subtrees rooted at the endpoints u and v, we can calculate the probability in \(O(1)\).
For each queries, we just update the expectation accordingly, since the probabilities are not affected.
Implementation:
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cassert> #include <cstring> #include <utility> using namespace std; /* LINEARITY OF EXPECTATION */ vector<vector<int> > adj; pair<int,int> edge[100005]; int vis[100005]; int len[100005]; int sz[100005]; double prob[100005]; int N, M; void dfs(int u){ vis[u] = 1; sz[u] = 1; for(int i=0;i<adj[u].size();++i){ int v = adj[u][i]; if(vis[v]) continue; dfs(v); sz[u] += sz[v]; } } int main(){ int u, v, w; scanf("%d", &N); adj = vector<vector<int> >(N+3); for(int i=1;i<N;++i){ scanf("%d%d%d", &u,&v,&w); edge[i] = make_pair(u,v); len[i] = w; adj[u].push_back(v); adj[v].push_back(u); } for(int i=1;i<=N;++i){ if(adj[i].size()==1){ dfs(i); break; } } double E = 0; double q = 1.00 * N * (N-1) * (N-2); for(int i=1;i<N;++i){ int k = min(sz[edge[i].first], sz[edge[i].second]); int _k = N-k; if(k >= 3){ prob[i] += 1.00 * k * (k-1) * (k-2); } if(_k >= 3){ prob[i] += 1.00 * _k * (_k-1) * (_k-2); } prob[i] = 1.0 - prob[i]/q; E += prob[i] * len[i]; } scanf("%d", &M); for(int i=0;i<M;++i){ scanf("%d%d", &u,&w); E -= prob[u] * (len[u] - w); printf("%.12lf\n", 2.0 * E); len[u] = w; } return 0; }
Problem E
500E - New Year Domino
Solution:
A very nice problem but very challenging implementation-wise. The problem suggests clearly that we have to implement either Fenwick Tree or Segment Tree to answer the range queries. I was quite happy to come up with the following, but I had to do something like 50 submissions just to get it accepted :P
The idea is as follows:
1. Let's for all pairs of (L,R) on a segment tree, we maintain holes[L,R] and offset[L,R], where holes[L,R] represents the number of unit segments that are not covered by any dominoes in [L,R] when all of them are laid down (i.e. has completely fallen down). This means that, if we know holes[L,R], then that is exactly how much we need to extend our dominoes. Meanwhile, offset[L,R] is the rightmost value that the dominoes in [L,R] can reach when they are fully laid down.
2. Then, Let's say we know both holes and offset of segment (L,M) and (M+1,R), where M is the mid-point of L and R (usually simply (L+R)/2). We need to find a way to efficiently derive holes[L,R] and offset[L,R] from those two segments. It is straight-forward for offset:
offset[L,R] = max(offset[L,M], offset[M+1,R])
But it is not as obvious for holes[L,R].
3. Firstly, if a segment was a hole in [L,M], it will remain a hole in [L,R], since we have no way to cover the segments with dominoes from [M+1,R]. So what can change is if a segment is a hole in [M+1,R], but is somehow covered by a domino in [L,M]. Now here is where offset[L,M] is useful: To find holes[L,R], we add up holes[L,M] + holes[M+1,R], and subtract with the number of segments that are in [M+1,R] but is reachable (and hence coverable) by offset[L,M].
4. We can use binary search to find the relative position of offset[L,M] in [M+1,R], and build the segment tree accordingly. Here we have several cases that need to be taken care separately depending on the relative position of offset[L,M].
Implementation:
#include <iostream> #include <algorithm> #include <utility> #include <cstdio> #include <cassert> using namespace std; int N, M; pair<long long,long long> edge[200003]; pair<long long,long long> segtree[1000003]; int lowerbound(long long val){ int lo=0,hi=N-1,mid; while(lo<=hi){ mid=(lo+hi)/2; if(edge[mid].first < val){ lo=mid+1; } else { hi=mid-1; } } return lo; } pair<long long,long long> rmq(int p,int L,int R,int S,int T){ if(R<S||T<L)return make_pair(-1,-1); if(S<=L&&R<=T){ return segtree[p]; } int M=(L+R)/2; pair<long long,long long> left=rmq(2*p,L,M,S,T); pair<long long,long long> right=rmq(2*p+1,M+1,R,S,T); if(left.first==-1)return right; if(right.first==-1)return left; pair<long long,long long> ret = make_pair(0,max(left.second,right.second)); int idx = lowerbound(left.second+1); if(idx>min(R,T)){ ret.first = left.first; }else if(idx == M+1){ ret.first = left.first + right.first + edge[M+1].first - left.second - 1; } else { pair<long long,long long> tmp = rmq(2*p+1,M+1,R,M+1,idx-1); if(left.second > tmp.second){ tmp.first += left.second - tmp.second; } ret.first = left.first + right.first - tmp.first; assert(ret.first >= left.first); } assert(ret.first>=0); return ret; } void build(int p,int L,int R){ if(L==R){ segtree[p] = make_pair(0,edge[L].second); return; } int M=(L+R)/2; build(2*p,L,M); build(2*p+1,M+1,R); segtree[p].second = max(segtree[2*p].second, segtree[2*p+1].second); int idx = lowerbound(segtree[2*p].second+1); if(idx>R) { segtree[p].first = segtree[2*p].first; }else if(idx == M+1){ segtree[p].first = segtree[2*p].first + segtree[2*p+1].first + edge[M+1].first - segtree[2*p].second - 1; } else { pair<long long,long long> ret = rmq(2*p+1,M+1,R,M+1,idx-1); if(segtree[2*p].second > ret.second){ ret.first += segtree[2*p].second - ret.second; } segtree[p].first = segtree[2*p].first + segtree[2*p+1].first - ret.first; } assert(segtree[p].first>=0); } int main(){ int u,v; scanf("%d", &N); for(int i=0;i<N;++i){ scanf("%d%d",&u,&v); edge[i] = make_pair(u,(long long)u+v-1LL); } build(1,0,N-1); scanf("%d", &M); for(int i=0;i<M;++i){ scanf("%d%d", &u,&v); printf("%I64d\n",rmq(1,0,N-1,u-1,v-1).first); } return 0; }
UPD: Just solved problem F, here is the discussion.
No comments:
Post a Comment