### xiaowuc1's blog

By xiaowuc1, 5 weeks ago,

Hi all,

The second contest of the 2020-2021 USACO season will be running from January 22nd to January 25th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! Please do not spoil anything about the contest publicly until the contest is over for everyone, and please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here.

• +154

 » 5 weeks ago, # |   +29 The first contest of the 2020-2021 USACOThere is a typo first -> second.
•  » » 5 weeks ago, # ^ |   -59 Nope 1st contest already happened at "Dec 18-21: First Contest".
•  » » » 5 weeks ago, # ^ |   +22 Yes..that is what DividedByZero is saying...
 » 5 weeks ago, # |   +6 Hoping to make Gold. Do you think someone with my rating graph has a decent chance at making Gold?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -24 f, i didn't expect that
•  » » » 5 weeks ago, # ^ |   0 WHAT?????I'm interested in why you think so...I mean I kinda base my progress on my rating.
•  » » » » 5 weeks ago, # ^ | ← Rev. 5 →   +15 It's just something people say when they feel bad about their rating to make themselves feel better (at least me :clown:). It's not perfect (especially for lower placement OI progress where it corresponds least), but it still is should be the unarguably the best measure of progress relative to others right now, assuming you have decent amount of data points.Most gold are high specialist or low expert I think, so you probably have somewhat decent chance.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   -18 f, i didn't expect that
•  » » » » » » 5 weeks ago, # ^ |   +8 I only said because of the existence of highs is not so proportional to your ability at all.This is why you need decent amount of data points, because highs and lows should average out to a close representation of your skill. But yeah, one large drop in rating, or one large rise, doesn't mean much on it's own.
•  » » » » » » 5 weeks ago, # ^ |   0 I'm a "her" FYI.
•  » » » » » » » 5 weeks ago, # ^ |   0 I didn't know, sorry.
•  » » 5 weeks ago, # ^ |   0 I hope too. Good luck for everyone and especially for you)Yes, it's possible. I think, you can get Gold. I believe in you!
•  » » » 4 weeks ago, # ^ |   +6 yay, Gold! :)
•  » » » » 4 weeks ago, # ^ |   +1 Congrats!
 » 5 weeks ago, # |   0 How do I register and participate? I opened the Contests page but there are only previous contests there.
•  » » 5 weeks ago, # ^ |   +3
•  » » » 5 weeks ago, # ^ |   0 Thank you. Apparently the link to the contest page is located on the top of the Overview page.
 » 5 weeks ago, # |   +16 Is there a way to see the standings? I am completely new to the USACO platform. Thank you.
•  » » 5 weeks ago, # ^ |   +3 No, you can't see live standings. That's because it's an IOI-like contest.
•  » » 5 weeks ago, # ^ |   +2 After the contest ends, you can see your standing.
•  » » 5 weeks ago, # ^ |   +14 Why are people downvoting me? Did I ask something wrong? I already said that I am new to that platform :(
•  » » » 5 weeks ago, # ^ |   +4 From post: please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here
•  » » » » 5 weeks ago, # ^ |   +18 Sorry for that. Will keep in mind from next time.
 » 5 weeks ago, # |   -98 Solve all the silver using 3hours and 56 minutes.....Think the problem for a lot of time, good problem!
•  » » 5 weeks ago, # ^ |   +46 Please don't discuss anything about the contest right now; I mean discuss literally NOTHING.
 » 4 weeks ago, # |   +5 When can we discuss?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +12 It's best to wait until the USACO website states that the contest is over (though I don't know when that will be).
•  » » » 4 weeks ago, # ^ |   +3 I believe it's okay to discuss now. Can anyone confirm?
•  » » » » 4 weeks ago, # ^ |   +12 Yes.
 » 4 weeks ago, # | ← Rev. 3 →   +49 Here are my solutions to all of the gold problems: Problem 1: Uddered But Not HerdThe goal is to partition the array into subarrays s.t. there is a minimum # of subarrays, and the partition is valid. Note that there are only 20 distinct characters in the string. Consider a graph where the nodes are those distinct characters. For every pair of adjacent characters, add an edge from the left one to the right one. A partition can be represented by removing some of these edges. It can be shown that this graph is only valid iff there are no cycles (because if there is a cycle there is no topsort and therefore no alphabet). Thus this problem can be reduced to the problem “minimum feedback arc set”, a well known problem that has a $n^2 2^n$ bitmask dp solution on the topsort. Problem 2: TelephoneThe obvious dijkstra approach is too slow, because there can be $n^2$ edges. The way you can fix this is by changing your state. Let $dist[i][j]$ be the minimum total distance cows need to walk s.t. a cow with color $j$ is at position $i$. Your answer is $dist[n][color[n]]$. The transitions are: The current cow can move one to the left (cost 1) The current cow can move one to the right (cost 1) The current cow can pass the message to the cow at that location if they are compatible (cost 0) You can solve this shortest path problem with 0-1 BFS. Another implementation detail is that the last edge taken must be of type 3. You can encode another dimension in your state, which represents a boolean value that is true if the last edge was of type 3 and false otherwise. This solution runs in $O(n*k)$ time. Problem 3: Dance MoovesLet $locs[i]$ represent the set of unique positions that cow $i$ would go to in the first $k$ moves. The sum of the sizes of $locs[i]$ is $\leq 2*k$, so you can store and compute it naively. Consider the inverse of the final permutation formed. You can solve for each cycle in that permutation independently. Let's call "hitting" a node $i$ visiting everything $locs[i]$. Each node in the cycle hits some (constant sized) range of other elements in the cycle. It also goes to some prefix of $locs[i]$ for some node $i$. You can do a sliding window on $locs$ to calculate the answer for every node in the cycle in amortized linear time. The final complexity is $O(n+k)$.Side Note: Was it intentional to make it hard to notice that there are $\leq 20$ distinct characters in the string in problem 1?Also: Does anyone know the solution for Plat Problem 3? I implemented Offline Dynamic Connectivity, but it had a complexity of $q*n*log(q)*log^2(n)$ with a bad constant, so it was too slow.
•  » » 4 weeks ago, # ^ |   +47 I agree, spent about 30 minutes thinking that there are <=26 characters instead and tried to find a polynomial solution because I thought <= 20 was a subtask. I wish they had stated that clearly in the problem statement, not just in the subtask list...
•  » » » 4 weeks ago, # ^ |   +27 Same here! Except in my case I spent a lot more than 30 minutes :(. The fact that they mentioned 26 in the statement made it even more confusing.
•  » » 4 weeks ago, # ^ |   -16 Hii!!!! Was it intentional to make it hard to notice that there are ≤20 distinct characters in the string in problem 1? Are you sure ??????????... Because i solved it for 2 hours with this very obvious $n^{2}*2^{n}$ solution which is a kind of repeat to this problem https://codeforces.com/problemset/problem/1238/E
•  » » 4 weeks ago, # ^ |   -11 Wait a minute!! I just went through the question and read it 10 times then i noticed the scoring portion. Are you talking about M i l d r e d ?? If yes, then its insane.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 For Problem 2, my friends qwerty190 osmium Freaksus got AC by doing Dijkstra, even there were n^2 edges. I am so confused why those solutions got passed.
•  » » » 4 weeks ago, # ^ |   +8 Would they be comfortable sharing their code? Sometimes brute force approaches with things like pragmas and heuristics pass, which is unfortunate.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 As far as I know, they don't use this kinda stuffs. I am contacting them, as soon as they reach me, they would reply to you in this comment!Edit: They didn't save their codes, so they can't get access to them right now. After this session's USACO problem page opens, they would get the codes. Moreover sorry for the misinformation, one of my friends got all ac by doing Dijkstra, but the other two got 12 test-cases out of 13.
•  » » » 4 weeks ago, # ^ |   +14 Yeah, I also know some friends that passed with just a brute force (without any pragmas or the sort.) I hope USACO adds some tests and rejudges, because a naive N^2 dijkstra should not get 12 or 13 cases.
•  » » 4 weeks ago, # ^ |   +28 You can solve plat problem 3 in $O(NM + Q(N+M))$; essentially, you approximate the answer by counting how many CC's have their upper left corner inside the query rectangle using prefix sums, and then you walk around the perimeter of the query rectangle to fix your approximation. There are various strategies to handle the details of the counting/overcounting; the cleanest strategy I know is to consider the (planar) graph of lattice points and use the Euler characteristic formula V-E+F = # cc's + 1.
•  » » » 4 weeks ago, # ^ |   0 How do you count the number of faces efficiently in this graph?
•  » » » » 4 weeks ago, # ^ |   +10 Note that each face/cycle of the original graph is either fully contained within the query rectangle, or it merges with the "outside" face (that extends to infinity) and doesn't contribute to the count. Thus, we just need to count the number of original faces fully contained within the query rectangle. From now on, "faces" will refer to faces of the original, whole graph.First, number the faces, and for each lattice point (corner between 4 tiles), precompute which face it belongs to using flood-fill. Now, for each face, pick one lattice point in it as the "representative", and compute rectangular prefix sums for the number of representatives in a region. This is our approximation/overcount for the number of faces fully contained; it may include some extra faces whose representative point is inside the query, but are not fully contained. Fortunately, these faces must intersect the boundary of the query rectangle. Thus, walk along perimeter of the query region, and subtract off the number of faces which intersect the perimeter at least once and whose representative is inside the query region; we can count these in linear time with a boolean array or a hashset. Then, we will be left with exactly those faces which are fully included, so V-E+F will work.
•  » » 4 weeks ago, # ^ |   +5 As ecnerwala said: the graph is planar, so we want to know the value of $V - E + C$, where $V$ stands for the number of vertices, $E$ for the number of edges and $C$ for the number of cycles. $V$ and $E$ can easy be calculated in constant time per query with prefix sums. To calculate general cycles we can just run DSU on the dual graph. Then for each connected component in dual graph we calculate its bounding box.So, we are given a list of rectangles (at most $n \cdot m$) and for each query we have to count how many of them are inside query's rectangle. It's easy to see that at this point complexity $O(q \cdot n \cdot m)$ is enough, as it's a very simple check.
•  » » » 4 weeks ago, # ^ |   +15 Making strong tests is hard :(I think my original proposal had $Q \leq 5000$ and $N, M \leq 2000$ without the increased TL — do you think the $O(QNM)$ solution still would've passed with those constraints?
•  » » » » 4 weeks ago, # ^ |   +15 Don't forget that you can count number of small bounding boxes (e.g. 1x1) insde of query in linear time, so this solution would have very small constant.
•  » » » » » 4 weeks ago, # ^ |   +20 I think if you use prefix sums for all bounding boxes with max side length at most $n^{1/3}$, you can get $O(1000^{8/3})$ runtime.
•  » » » » » » 4 weeks ago, # ^ |   +5 In case of generalization, we can try squeezing using different constants(for higher constraints) because I assume creating test with evenly distributed boxes is probably impossible.
•  » » » » 4 weeks ago, # ^ |   +5 Don't worry, it's not about the tests, just the limitations. As Andrew wrote it can be squeezed even more. I think that for all rectangles (assume there are $c$ of them and assume $n=m$) with fixed height and width limited by some $x$ we can solve the problem in $O(n^2 + c \cdot x + q)$, so we can solve rectangles with height and width small smaller than $\sqrt{n}$ in $O((n+q) \cdot n \cdot \sqrt{n})$. Then, there are at most $n \cdot \sqrt{n}$ rectangles, so the whole complexity would be like $O((n+q)^{5/3})$.Btw. there are always at most $20-30$ tests. Are they tests or are they really groups of tests?
•  » » » » » 4 weeks ago, # ^ |   +11 USACO doesn't use grouped tests, so they're just single tests. I think it's because their servers aren't powerful enough to handle so many tests for so many people. (The camp contests have grouped tests though)
•  » » » » 4 weeks ago, # ^ |   +5 Uhoh... I wrote some weird bitset shit that gives $O(\frac{NMQ}{B} + Q 2^B)$ time complexity. I thought I got the intended solution and thought the problem was weird, but the model solution is actually nice.If you had $Q \le 5000$ then I might try to use the brain :) It doesn't look like tight limit at all.
•  » » » » 4 weeks ago, # ^ |   0 I think tests are actually a bit weak. I managed to AC dynamic connectivity (written in part by 12tqian) solution with $N^2 log^2{N} + N^3/64$ in about 2.7/3 seconds. It's worth noting because it's in essence the "trivial" dynamic connectivity solution with relatively few constant optimizations.
•  » » » » » 4 weeks ago, # ^ |   0 Here's my implementation: link. I have no idea why changing the types of g, h, v from int to short makes it AC, but apparently it does.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 gold P2 can be solved with djikstra,you can reduce the number of edges to $O(nk)$ with the following observation :given node $v$ and the set of groups that is compatible with $v$,you only need to connect $v$ to two nodes in each such groups namely the node closest to $v$ from the right and closest to $v$ from the leftthe proof is as follows:assume you have a optimal path $A$ $\to$ $B$ $\to$ $C$ and that $B$ is neither the closest node to the right or left of $A$ (within the same group as $B$),then you can modify $B$ accordingly to be one of the two nodes described above with some caseworkthe final step is to connect edges to $n$ whenever possible,each node atmost have $2k+1$ edges so there are atmost $2nk + n-1$ edges
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Could you share the "minimum feedback arc set" dp solution on the topsort pls?
•  » » » 4 weeks ago, # ^ |   0 See 46:06 of this Algorithm's Live! video by tehqin. The problem Order of the Hats mentioned in the video is the minimum feedback arc set problem, and this gold problem can be reduced to it as I mentioned in my comment above. Also my solution ended up being pretty much the same as the editorial, so reading that will definitely help.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Could you share video link or code pls?
•  » » » » » 4 weeks ago, # ^ |   0 Oh I'm sorry, I forgot to link the video. Here
•  » » » » » » 4 weeks ago, # ^ |   0 many thank!
 » 4 weeks ago, # |   +66 There were problems initially with the output files of Gold P1. Spent 2 hours before rage quitting wondering why my '3' is not their '3'.Really appreciate though that the issue was recognised and quickly resolved after I sent an email.
•  » » 4 weeks ago, # ^ |   +72 ^ why you never take USACO at the start of the contest window
 » 4 weeks ago, # | ← Rev. 2 →   0 How to solve Silver P1 ? Does it involve bitsets ?
•  » » 4 weeks ago, # ^ |   0 It was the classic swapping graph-theory problem! See my code below if you're curious.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 Consider the cycles in the final permutation produced after doing the $k$ moves. Each cycle is independent, and it can be shown that every node in the cycle has the same answer. The answer for some node in the cycle is the size of the union of the sets of all distinct locations each node in the cycle visited in the first $k$ moves (this is because each node in the cycle visits the locations of every node in the cycle). This value can be calculated in amortized linear time, as the sum of sizes of the sets is $\leq 2k$. The final complexity is $O(n+k)$.
•  » » » 4 weeks ago, # ^ |   0 Very Nice Solution. Thanks for the explanation!
 » 4 weeks ago, # | ← Rev. 2 →   +2 My USACO Silver solutions (finished with 15 minutes to spare, only) Problem 1/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //Created by Maria Chrysafis #include #include /** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //Created by Maria Chrysafis #include #include #include #include #include #include #include #include #include #include using namespace std; class Problem1DanceMooves { public: vector> adj; vector hasVisited; int N, K; vector vis; void dfs(int src){ hasVisited[src] = true; vis.push_back(src); for(int j: adj[src]){ if(!hasVisited[j]){ dfs(j); } } } void solve(std::istream& in, std::ostream& out) { ios_base::sync_with_stdio(false); cin.tie(NULL); in >> N >> K; hasVisited.resize(N); adj.resize(N); //first perform the swaps vector arr(N); vector> myMap(N); for(int i = 0; i < N; i++){ arr[i] = i; myMap[i].insert(i); } vector> swaps(K); for(int i = 0; i < K; i++){ int a,b; in >> a >> b; a--; b--; myMap[arr[a]].insert(b); myMap[arr[b]].insert(a); swap(arr[a], arr[b]); } for(int i = 0; i < N; i++){ adj[i].push_back(arr[i]); } vector> cc; for(int i = 0; i < N; i++){ if(!hasVisited[i]){ dfs(i); cc.push_back(vis); vis.clear(); } } vector ans; int pr[N]; for(int i = 0; i < cc.size(); i++){ set s; for(int j: cc[i]){ s.insert(myMap[j].begin(),myMap[j].end()); } for(int j: cc[i]){ pr[j] = s.size(); } } for(int j: pr){ out << j << endl; } } }; int main() { Problem1DanceMooves solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }  Problem 2/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //Created by Maria Chrysafis #include #include #include #include #include #include #include #include #include #include using namespace std; class Problem2NoTimeToPaint { public: vector pref(string s){ vector v; v.resize(s.length()); map used; int counter = 0; for(int i = 0; i < s.length(); i++){ if(!used[s[i]]){ used[s[i]] = true; counter++; } for(char c = s[i]; c <= 'Z'; c++){ if(c == s[i]) continue; if(used[c]){ used[c] = false; } } v[i] = counter; } return v; } void solve(std::istream& in, std::ostream& out) { ios_base::sync_with_stdio(false); cin.tie(NULL); int N,Q; in >> N >> Q; string s; in >> s; vector Pref = pref(s); reverse(s.begin(),s.end()); vector Suf = pref(s); reverse(Suf.begin(),Suf.end()); while(Q--){ int l,r; in >> l >> r; l--; r--; if(l == 0 && r == s.length()){ out << 0 << endl; }else if(l == 0){ out << Suf[r + 1] << endl; }else if(r == s.length()){ out << Pref[l - 1] << endl; }else{ out << Pref[l - 1] + Suf[r + 1] << endl; } } } }; int main() { Problem2NoTimeToPaint solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }  Problem 3/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //Created by Maria Chrysafis #include #include #include #include #include #include #include #include #include #include using namespace std; class Problem3SpacedOut { public: vector> mat; int N; int MAX(){ int counter = 0; for(int i = 0; i < N; i++){ int cur = 0; int pos = 0; for(int j = 0; j < N; j++){ if((abs(i - j)) % 2 == 0){ cur += mat[i][j]; } pos += mat[i][j]; } cur = max(cur, pos - cur); counter += cur; } return counter; } int MAX1(){ int counter = 0; for(int i = 0; i < N; i++){ int cur = 0; int pos = 0; for(int j = 0; j < N; j++){ if((i + j) % 2 == 0){ cur += mat[i][j]; } pos += mat[i][j]; } cur = max(cur, pos - cur); counter += cur; } return counter; } void solve(std::istream& in, std::ostream& out) { ios_base::sync_with_stdio(false); cin.tie(NULL); in >> N; mat.resize(N); for(int i = 0; i < N; i++){ mat[i].resize(N); for(int j = 0; j < N; j++){ in >> mat[i][j]; } } int ANS = max(MAX(),MAX1()); vector> new_mat = mat; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ new_mat[j][i] = mat[i][j]; } } mat = new_mat; ANS = max(MAX(),max(ANS,MAX1())); out << ANS << endl; } }; int main() { Problem3SpacedOut solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; } Full Disclaimer: My solutions are somewhat messily written due to the time pressure.
•  » » 4 weeks ago, # ^ |   +13 Can you share your code for problem 2? I want to try to break it, but I don't fully understand the solution. I can also stress test it (I have a generator and a correct solution already), and I'll tell you if I can find a counter test.As for the promotion cutoff, I would guess either a 700 or a 750. I'm probably biased here because I solved all of the problems (and I'm good at graph problems), but this contest didn't feel absurdly hard (unlike the last one). For reference, last contest I got a 200 on gold, but in this one I ICP'd and got a 450 on platinum. I think a 700 or a 750 cutoff would be reasonable, but we'll have to wait and see.
•  » » » 4 weeks ago, # ^ |   +5 Code on PastebinIt's terrible, don't judge it, please.
•  » » » » 4 weeks ago, # ^ |   +13 I found a counter test, your lemma is wrong. Counter Test9 5 1 2 4 2 3 2 4 2 5 00010 00100 00001 01000 00000 The only possible path will have these transfers (based on color): $1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 5$. In this case, checking only the first and last occurrences of each character is not sufficient.
•  » » » » » 4 weeks ago, # ^ |   0 Thank you! I guess I got lucky with the tests. I will now try to solve it properly.
•  » » » 4 weeks ago, # ^ |   +34 i have 749 points (full + 11/13 + 8/20) and I'm praying for 700... Missing plat by 1 point will be super sad...
 » 4 weeks ago, # |   0 What does everyone expected the gold cutoff to be? I'm thinking 750-800.
 » 4 weeks ago, # |   0 I'm pretty curious about the silver-->gold cutoff. I made it with a 1000, but since last contest I got only 350, I was thinking maybe I got lucky and it was just an easy contest. Did you guys think it was an abnormally easy silver contest?
•  » » 4 weeks ago, # ^ |   +1 A friend and I both found this silver contest much harder than the December contest, but maybe that's just because our skill set is different than yours. I'm interested in checking out the official solutions and cutoff scores after they come out though.
•  » » » 4 weeks ago, # ^ |   0 Admittedly, I still don't get the intuition behind the second December silver problem. I get the solution, but I still don't get how to come up with the solution, I guess.
•  » » 4 weeks ago, # ^ |   0 I definitely thought it was easier — Q3 in the December contest felt way harder than Jan Q3
•  » » » 4 weeks ago, # ^ |   0 Interestingly enough, Q3 took me the least amount of time. My times:Q1--2 hours (bugs :)Q2--1 hour Q3--45 minutes
 » 4 weeks ago, # |   +10 Is it intended to make P1 < P2 < P3 or is it rather random?
•  » » 4 weeks ago, # ^ |   +5 From the USACO Guide: Problem difficulties can be out of order, so keep that in mind before focusing down 3 hours on problem 1 and not getting anywhere. Do a good amount of thinking on each problem before deciding which ones to focus on and which to put aside. Historically, the first platinum problem has never been the hardest (though you shouldn't count on this).
•  » » 4 weeks ago, # ^ |   0 I actually found P1 the hardest, any hints on its solution?
•  » » » 4 weeks ago, # ^ |   0 Try to think about the shortest odd and even paths in every graph.
•  » » » 4 weeks ago, # ^ |   0 Waiting for hint/editorial for P1 platinum also.
•  » » » » 4 weeks ago, # ^ |   +5 Solution for Plat P1First, let's try to figure out how to actually find the shortest path to some tuple efficiently. Consider each separate node in the tuple (call it $c$). Let $dist[c][0]$ be the min distance to get to $c$ within it's own graph s.t. it's at an even distance away from node 1, and $dist[c][1]$ be the min distance to get to $c$ s.t. it's at an odd distance away from node 1. Both of these quantities can be calculated easy using a bfs. The answer for some tuple is $min(max(dist[c][0]), max(dist[c][1]))$. This is because if everything has the same parity, every node that get's there before the node with the max distance can just move back and forth along an edge. Fix the node and the parity that contributes the answer. You can sweep from least to greatest for the corresponding parity and maintain the number of tuples efficiently using a segment tree. The final complexity is $O(n*log(n))$ where $n$ is the sum of the individual graph sizes.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +20 There is no need for a segment tree. Using the fact that $min(max(d[x][0]), max(d[x][1])) = max(d[x][0]) + max(d[x][1]) - max(max(d[x][0], d[x][1]))$helps a lot. Infinity contributes 0 to the answer.
 » 4 weeks ago, # |   0 How to solve Platinum P2 and P3?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 Solution to Plat P2Consider the process in reverse. Now it can be shown that for a certain column, you will move up to a certain row before moving to the left. For a column $i$ call that row $opt[i]$. $opt[1]$ is obviously $1$. For every other $i$, ternary search on $opt[i]$. Let's focus on calculating the min cost for the query $(n, i)$ and a fixed $opt[i]$, assuming you calculated $opt[j]$ for all $j < i$. You are going to go up until you hit $opt[i]$ then move to the left, and then move down until $opt[i-1]$. From there, you can use a pre-calculated answer to find out the answer. Now, you can ternary search to find the $opt$ values. About the pre-calculated values I mentioned earlier, call $pre[i]$ the answer for the prefix of $i$ columns, given that the query position is $opt[i]$. You can calculate this using the same calculation as before (and $pre[1] = 0$). Now you can use this same calculation to answer the queries as well.One more implementation detail: what happens when the column in the query is $< opt[i]$? You would keep moving left until you hit column with a greater $opt$. To calculate what this would be efficiently, you can use something similar to binary lifting.Here is my code.For P3, ecnerwala described a solution in a comment above.
•  » » » 4 weeks ago, # ^ |   0 What do you mean by not being sure? Do you mean that the tests might be not strong enough to detect an incorrect solution or that you haven't submitted during the contest?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I finished this right after the contest, so I couldn't submit. I stress-tested it after against the obvious $O(n*m)$ dp.Edit: Submitted it after the contest and it passed.
•  » » 4 weeks ago, # ^ |   +33 I wrote about P3 above. P2 is a history exam about problem "Icy Roads" from Gennady Korotkevich contest 1 from 2013.
•  » » » 4 weeks ago, # ^ |   0 Where do you find these contests?
•  » » 4 weeks ago, # ^ |   +11 P2 intuitive solution w/o knowing some obscure contest$N<=1e9$ immediately screams solving offline over columns and keeping the answer for each row in graph form. Turns out, this is possible. The answer for the first row is obviously $y=c_1x$. Transitioning to the second row, the graph becomes $y=x^2+c_1x$. Then, transitioning down the row is exactly equivalent to drawing a line of slope $c_j$ at some point of the current graph. If you can visualize this for the second column, it's obvious that the optimal place to transition is ONLY at the tangent line. Generally, the solution becomes: maintain $ax^2+bx+c$ and the interval that it is optimal. When transitioning across a column, the do increment $a$ for all quadratics in the set. To transition down the row, note across the set of quadratics that we're maintaining convexity and differentiability holds everywhere even after transitioning. So simply take the derivative of the quadratic and find when the slope of the tangent line is equal to $c_j$. If it's less than the range of optimality of the current polynomial, pop it out. At the end, add a new polynomial $y=0x^2+c_j(x -x_{tangent}) + y_{tangent}$. Finally, calculating answer for a query can be done by binary search.
•  » » » 4 weeks ago, # ^ |   +5 A general summary of the technique is to consider the values of the "naive DP" as a function in one of the state variables, and try to identify/prove if it's convex; if so, try to maintain it or its derivative as piecewise linear or quadratic. (Depending on the problem, you may want to store inflection points or segments or something else.)
•  » » » » 4 weeks ago, # ^ |   +8 Oh, this strategy seems sort of similar to the slope trick I guess (which is only for linear functions).
 » 4 weeks ago, # | ← Rev. 2 →   +5 sorry to comment something during the contest. (got so many downvotes...)This is my first time to do usaco contest brozon & silver.I spend nearly one hour to figure out the simple dp solution for the 3rd problem, and another one hour to transfrom the second question to a well known question.For the second, get L[i], r[i] be the first smaller position from left and right of i-th number, then answer is about distinct elements in range. This is a well known problem called D-query in spoj.For the third, consider by row, thus two rows will be the same or complete different. We can do it using dp[N][2]. Then swap the element by main diagonal, do the dp again.
•  » » 4 weeks ago, # ^ |   0 DP was actually not needed for the 3rd problem! HintFix the game board to be a checkerboard (ie alternating C and '). See what happens when we change a C to a ' and vice-versa.
 » 4 weeks ago, # |   +37 When will the results post?
 » 4 weeks ago, # |   0 For Gold problem 2, if you're currently at cow A and are looking to travel to a cow of breed B, is it correct that you only have to check the cows in B closest to A in either direction and the rightmost cow of B? Because (I think) the only time it's optimal to go all the way right is if you can get to cow N. Otherwise, let's say that the next cow you want to travel to is cow C, the cow from breed B closest to A on the left L, and the cow from B closest to A on the right R. Since the answer can be represented as (N-1) + 2 * (backwards distance traveled), the goal is to minimize the total backwards distance traveled. If C is left of L, then no matter what you'll have to travel at least A-C distance to get there, so one of your best paths are guaranteed to be A -> L -> C. If C is right of L and left of R, then at least one of the optimal paths are A -> L -> C or A -> R -> C, whichever of the two travels backwards less. Otherwise, if C is right of R, then your one of your best paths are guaranteed to be A -> R -> C.
•  » » 4 weeks ago, # ^ |   0 Welp I implemented and submitted and it got AC so I'll assume for the time being that the idea is valid xd
 » 4 weeks ago, # |   +1 Results are out!
 » 4 weeks ago, # |   0 (int) m%k instead of (int) (m%k)What a great way to miss an icp.