Hi, I am struggling to get past silver in recent contests. Not that I don’t know the silver topics, in fact I know they pretty well (did all silver modules on the guide and most historical problems 2015+). I feel 2020-21 silver is much harder to problem solve compared to all historical silver contests (before 2020-21). Therefore, do you think I should study ahead by learning gold concepts and doing gold problems? Because in theory, it would help me to get better at problem solving harder problems. Is this a good idea?
Definitely. It basically gives you more tools to use. The same goes for bronze to silver. Topics like prefix sums which is a silver topic was incredibly useful in the latest bronze contest.
Ok, so here’s why learning gold techniques and problems would be a good idea:
-
Let’s take prefix sums, for example. Prefix sums are a simpler form of dynamic programming, so don’t you think learning harder DP would solidify your prefix sums knowledge?
-
Another example is graph theory. The first problem of this past contest involved floodfill. On USACO Discord, people were mentioning how they were able to use BFS (a gold topic) for that problem.
Aside from practicing gold problems, I recommend you to solve CF problems. These problems primarily help improve your problem-solving skills, so it’d be very useful to you, according to your description.
Are you referring to clockwise fence (check whether a sequence of NSEWs forms a clockwise or counterclockwise curve)? If you’re computing every vertex of the polygon that FJ traverses and then finding its area, I guess you’re taking prefix sums in some sense. But I don’t see how knowing the content of the corresponding silver module would help in the slightest.
I don’t think this is true at all. Some dynamic programming problems involve prefix sums, but that doesn’t imply that prefix sums are a form of dynamic programming.
It’s true that using a queue as BFS does rather than DFS is probably an easier way to think about it. Though there exists a solution purely based on DFS. Perhaps the flood fill module should specify that the recursive approach is only one way of doing flood fill.
You shouldn’t expect concepts listed under the Gold section in USACO guide to be helpful for Silver (though perhaps you can use BFS or DSU as alternative solutions for some problems). But solving (reasonably) harder problems might help.
Well, to be more specific, here is why prefix sums is a form of DP:
-
Since you are storing a sum that can be computed recursively as f(n) = arr[n] + f(n-1), the recursion in this problem is calling upon f(n-1).
-
The prefix sum array stores each sum and calculates it using dp[n] = arr[n] + dp[n-1], which stores the previous recursive value.
In both contexts [dynamic programming] refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.
Well, I guess I can’t argue that prefix sums don’t satisfy this (very general) definition. Though I don’t see how thinking of it as DP would aid in understanding it at all.
I personally believes that prefix sum is rather a data structure, not really dynamic programming.
Yeah, that’s probably a more fitting category for psums. However, we can still argue that psums are the most basic form of DP; therefore, not really needing understanding of dp to solve them.
I think studying ahead might be a good decision. I feel like the difficulty of USACO Gold and Silver contest is increasing. More practices might be required to be able to score well on them.
Here are my thoughts with what might help (not included in the silver syllabus), I can recall problems that can be solved easier use these techniques.
-
Dynamic Programming
example: [USACO21JAN] No Time to Paint, but can also be solved by prefix sum. -
Lowest Common Ancestor
example: [USACO19DEC]Milk Visits S, but can also be solved by DSU. -
Segment Tree/Fenwick’s Tree
Not appeared yet, but I think these data structures are very helpful while solving O(n\lg n) kind problems.