2:41 PM
Simulated this contest today - here are my notes and solutions!
I'm experimenting with this writeup style as my previous massive-header-comment-bash was admittedly pretty messy, and this should hopefully be both cleaner and more easily visible.
P1: Sum Game
Literally just textbook prefix sums:
#include <iostream>
int a[100000], b[100000];
int main(){ int n; std::cin >> n;
for(int i=0; i<n; ++i) std::cin >> a[i]; for(int i=0; i<n; ++i) std::cin >> b[i];
// accumulate twin psums int best = 0, as = 0, bs = 0;
for(int i=0; i<n; ++i){ as += a[i], bs += b[i]; if(as == bs) best = i+1; }
std::cout << best << '\n'; }
P2: High Tide, Low Tide
Notice that the low tides and high tides can be separated: all of the low tides live in the lower half of our data, if sorted, and opposite for high tide. Then because of the extremes, we can determine the order of tides, too.
Sorted the array normally and "virtually split it" by starting two pointers at the first low and high tides, respectively.
#include <algorithm> #include <iostream>
int m[100];
int main(){ int n; std::cin >> n;
for(int i=0; i<n; ++i) std::cin >> m[i];
std::sort(m, m+n);
// low tide and high tide markers int l = (n-1)/2, r = l+1, par = 1;
// push to extremes while(l+1 || r < n){ if(par) std::cout << m[l--] << ' '; else std::cout << m[r++] << ' '; par ^= 1; }
std::cout << '\n'; }
P3: Nailed It!
This question was very fun. I looked at the constraints and thought 'wow, 1e6? probably requires nlogn, or something', which I couldn't think of a trivial approach for. Instead I decided to troll some partials with an n^2 approach, selecting all possible pairs of wood and combining into boards, then counting how many board existed at each height, and etc.
#include <iostream> #include <map>
int h[1000000];
int main(){ int n; std::cin >> n; for(int i=0; i<n; ++i) std::cin >> h[i];
std::map<int, int> freq;
for(int i=0; i<n; ++i) for(int j=i+1; j<n; ++j) ++freq[h[i]+h[j]];
int best = 0, count = 0;
for(const auto &[height, number] : freq) if(number > best) best = number, count = 1; else if(number == best) ++count;
std::cout << best << ' ' << count << '\n'; }
The result: TLE on batches 4 and 5, which were expected.. but WA on 2+3? These were the subtasks with n <= 1e3!
A realized after a minute or two that my algorithm was outputting 3 1 for the case 2 2 2, where 1 1 was correct. What I had failed to consider was that you couldn't select two boards to make a fence if they shared a piece of wood :clown:
Anyway, this was quite easy to fix: use another map to compress the pieces of wood into pairs of (height, occurance) and then consider the following two cases:
- create a board with two different-height pieces
- create one with two same-height pieces
Pretty easy to write up.
#include <iostream> #include <array> #include <map>
// heights of each piece, compressed count of each height int h[1000000]; std::array<int, 2> comp[2001];
int main(){ int n; std::cin >> n; for(int i=0; i<n; ++i) std::cin >> h[i];
// coordinate compress with map std::map<int, int> freq; for(int i=0; i<n; ++i) ++freq[h[i]];
auto p = comp; for(const auto &[num, count] : freq) *(p++) = {num, count}; n = p - comp;
// determine all possible sizes of boards, and how // many different ones can be built std::map<int, int> board;
for(int i=0; i<n; ++i){ // with n planks of size x, floor(n/2) boards of // size x*2 can be made board[comp[i][0]*2] += comp[i][1]/2;
// with n planks of size x and m planks of size y, // min(n+m) boards of size x+y can construct for(int j=i+1; j<n; ++j) board[comp[i][0]+comp[j][0]] += std::min(comp[i][1], comp[j][1]); }
// best length of fence, # of different heights of this best length int len = 0, count = 0;
for(const auto &[height, num] : board) if(num > len) len = num, count = 1; else if(num == len) ++count;
std::cout << len << ' ' << count << '\n'; }
As expected, AC on 2+3. But also.. AC on 4+5??
Turns out that I got trolled by constraints: While n was bounded by 1e6, the possible heights of each piece was bounded by 1e3, and so my compression step effectively reduced the n bound.. and then quadratic time was fully doable. Definitely watch out for this in the future :clown:
P4: Minimum Cost FLow
Just like P5 from yesterday's contest, I saw MST immediately. Actually, it was almost entirely standard MST - only 2 extra constraints:
- We want to not only find the minimum cost to operate, but also the minimum # of days to obtain such an optimal configuration.
- We can reduce exactly one edge by a specific value, and the affected edge can't be reduced to negative weight.
First const was easy to work around: If we ignore the enhancer, which should get us the first three subtasks, we can almost just use standard MST.
Here's why: All MSTs can be found by performing Kruskal's on an ordered list of edges such that weight/cost is non-decreasing. This means that we can swap any number of edges as long as they have identical cost, and still obtain an optimal spanning tree. So, to find the MST with highest similarity to initial configuration, prioritize pipes that are initially on. We can actually just do this in our sorting function, by defining a custom comparator, or something like that:
#include <algorithm> #include <iostream> #include <array>
std::array<int, 4> pipe[200000];
int root[100000];
int find(int i){ if(root[i] < 0) return i; return root[i] = find(root[i]); }
int main(){ int n, m, d; std::cin >> n >> m >> d;
for(int i=0; i<m; ++i) std::cin >> pipe[i][2] >> pipe[i][3] >> pipe[i][0], --pipe[i][2], --pipe[i][3], pipe[i][1] = i >= n-1;
std::sort(pipe, pipe+m);
int res = 0;
for(int i=0; i<n; ++i) root[i] = -1;
for(int i=0; i<m; ++i){ int a = find(pipe[i][2]), b = find(pipe[i][3]); if(a == b) continue;
if(a < b) root[a] += root[b], root[b] = a; else root[b] += root[a], root[a] = b;
res += pipe[i][1]; }
std::cout << res << '\n'; }
This gets nearly full credit - wow!
Seeing that I couldn't think of a good way to modify for const 2, I moved on to P5. Eventually I gave up on getting more than 2 partials on P5 and came back :P
So, how can we account for the enhanced pipe? What makes this so difficult to adapt into is that only one pipe can be enhanced, and different pipes can be enhanced by different values, essentially. (If cost of pipe i is less than d, there is less "benefit" in enhancing that pipe.)
After bricking on this for a while (still seemed more doable than p5) I decided to use the OP strat of taking a walk around my house until I got ideas. Walked around room-where-bad-ideas-happen (long story. a little bit of an inside joke.) in circles for a few minutes, and ironically came up with this idea:
First use the old approach to find an optimal MST. Then, iterate over all pipes, and consider the effect on a) cost and b) time to configure.
How do we compute delta of cost? It's obvious that if the edge isn't already in the MST then its delta will be its own cost (minus whatever the enhancer could d) combined with whatever edge in the tree it can replace.
That's the neat part: The optimal edge to remove is the maximally weighted edge in the path between the newly added edge's endpoints.
We can compute this with binlifting!!!
Additionally, this approach also computes for us the time to configure, as we just have to consider whether or not a) the new edge and b) the replaced edge were initially active.
Code was really messy, though.
#include <algorithm> #include <iostream> #include <vector> #include <array>
// all pipes in sorted order. To avoid using a custom comparator, // the structure of each pipe is: // // 0: cost of pipe (this ensures that pipes are sorted in strictly // increasing cost first, then other attrib) // // 1: whether or not pipe is already active (0 if so, 1 if not) // // 2, 3: endpoints of pipe (essentially doesn't matter
std::array<int, 4> pipe[200000];
// unite-by-size dsu; mostly standard int root[100000]; int find(int i){ if(root[i] < 0) return i; return root[i] = find(root[i]); }
// binlifting and associated memory for retraversal. // edges store three properties: // // 0: other endpoint // // 1: cost of this edge // // 2: reduction (whether or not this pipe was active initially)
std::vector<std::array<int, 3>> adj[200000];
// jump structure stores essentially the same properties as // do edges, but store the *maximum* cost of all edges over path // and maximum reduction associated with such a maximum cost std::array<int, 3> jump[200000], par[200000]; int depth[200000];
// helper function to handle merging of reductions std::array<int, 3> merge(std::array<int, 3> a, std::array<int, 3> b){ if(a[1] > b[1]) return a; if(b[1] > a[1]) return b; if(a[2] > b[2]) return a; return b; }
// re-traversal recursor which also builds binlift jumps void dfs(int i, int p){ for(const auto &[x, cost, red] : adj[i]) if(x != p){ depth[x] = depth[i] + 1;
// so messy.. if(depth[i] + depth[jump[jump[i][0]][0]] == depth[jump[i][0]]*2) jump[x][0] = jump[jump[i][0]][0], jump[x][1] = std::max(cost, std::max(jump[i][1], jump[jump[i][0]][1])), jump[x][2] = merge({0, cost, red}, merge(jump[i], jump[jump[i][0]]))[2]; else jump[x][0] = i, jump[x][1] = cost, jump[x][2] = red;
par[x][0] = i, par[x][1] = cost, par[x][2] = red;
dfs(x, i); } }
int main(){ int n, m, d; std::cin >> n >> m >> d;
// input and sort pipes for(int i=0; i<m; ++i) std::cin >> pipe[i][2] >> pipe[i][3] >> pipe[i][0], --pipe[i][2], --pipe[i][3], pipe[i][1] = i >= n-1;
std::sort(pipe, pipe+m);
// find MST and record # of days necessary to build this tree in 'first'. // we don't consider enhancer at all here. int first = 0;
// init dsu etc. very standard for(int i=0; i<n; ++i) root[i] = -1; for(int i=0; i<m; ++i){ int a = find(pipe[i][2]), b = find(pipe[i][3]); if(a == b) continue;
if(a < b) root[a] += root[b], root[b] = a; else root[b] += root[a], root[a] = b;
first += pipe[i][1];
adj[pipe[i][2]].push_back({pipe[i][3], pipe[i][0], pipe[i][1]}); adj[pipe[i][3]].push_back({pipe[i][2], pipe[i][0], pipe[i][1]}); }
// re-process tree to build binlifts; we can now efficiently determine // the result of adding back one edge to the tree and removing the // previously largest edge in the path dfs(0, -1);
// best reduction, best # of days for such reduction int best = 0, days = first;
// consider all possible edges, even ones that are in MST for(int i=0; i<m; ++i){ // LCA-like algorithm int a = pipe[i][2], b = pipe[i][3]; if(depth[a] < depth[b]) std::swap(a, b);
// current maximal edge, as well as best reduction on all // edges of that maximal weight int curr = 0, red = 0; while(depth[a] > depth[b]){ if(depth[jump[a][0]] < depth[b]) red = merge({0, curr, red}, par[a])[2], curr = std::max(curr, par[a][1]), a = par[a][0]; else red = merge({0, curr, red}, jump[a])[2], curr = std::max(curr, jump[a][1]), a = jump[a][0]; }
while(a != b){ if(jump[a][0] == jump[b][0]) red = merge({0, curr, red}, merge(par[a], par[b]))[2], curr = std::max(curr, std::max(par[a][1], par[b][1])), a = par[a][0], b = par[b][0]; else red = merge({0, curr, red}, merge(jump[a], jump[b]))[2], curr = std::max(curr, std::max(jump[a][1], jump[b][1])), a = jump[a][0], b = jump[b][0]; }
// proposed cost reduction + days necessary to complete int prop = curr - std::max(0, pipe[i][0] - d), dy = first + pipe[i][1] - red;
// update running bests if(prop > best) best = prop, days = dy; else if(prop == best && dy < days) days = dy; }
std::cout << days << '\n'; }
AC :P
P5: RMT
Seemed hard to segtree cheese, so I was immediately at a disadvantage.
Wrote up a really simple bruteforce but couldn't find a good way to group regions or anything. Tried some prefix/postfix stuff, but those just got really complicated to implement, and I kinda wanted to work more on the MST problem.
#include <iostream>
// stupid bruteforce
using LL = long long;
int group[150000], at[150000];
int main(){ int n, m, q; std::cin >> n >> m >> q; for(int i=0; i<n; ++i) std::cin >> group[i]; for(int i=0; i<n; ++i) std::cin >> at[i];
while(q--){ int t; std::cin >> t;
if(t&1){ int l, r; std::cin >> l >> r, --l, --r;
LL res = 0;
for(int i=l; i<=r; ++i) res += at[i];
std::cout << res << '\n';
}else{ int x; std::cin >> x;
int first = -1, carry = 0;
for(int i=0; i<n; ++i) if(group[i] == x){ if(first == -1) first = i; std::swap(carry, at[i]); }
at[first] = carry; } } }
2 partials, but could be worse.
tags: programming ccc contest-logs