### karthiksing05's blog

By karthiksing05, history, 2 months ago,

Been looking for some more functional graph problems to practice implementation after the USACO Jan 2023 Silver P1 problem (which I horribly failed btw)! Rating should be roughly around 1600-1900, but as long as the implementation is good practice i don't really mind!

• 0

 » 2 months ago, # | ← Rev. 2 →   0 USACO Jan 2023 Silver P1 was not related any way to a functional graph. The graph problem this month was problem 2.Let me explain why. What is the definition of a functional graph? Quoting the Usaco Guide, "in a functional graph, each node has exactly one out-edge. This is also commonly referred to as a successor graph."So if string A was "ABC" and string B was "DEF" then our graph would look like:A -> DB -> EC -> Fwhich is not a functional graph because nodes D, E, and F, do not have one out-edge.I also tanked the USACO silver contest, hopefully we can improve together!
•  » » 2 months ago, # ^ |   0 I thought of it as a pseudo-functional/successor graph, where each character has an outdegree of 0 or 1. I think knowledge of functional graphs would help with this problem. Also P1 was 100% the graph problem of the month. P2 can also be seen as a graph prob, but many people (including me) viewed it as a prefix sum problem.
•  » » » 2 months ago, # ^ |   0 Here's why I thought P2 was a graph problem. If I reversed the edges (signs), then I could use DFS from every vat of food to calculate the initial cost. But anyways.I also thought P1 was a graph problem, but someone told me it wasn't (and I, unfortunately, believed them). Of course, I just don't know what to do with it :(
•  » » » » 2 months ago, # ^ |   0 Yeah P2 can be done with a dfs since it has the structure of a DAG. Also for P1, this happened after the contest window closed, right?
•  » » » » » 2 months ago, # ^ |   0 Of course, it was after the contest window closed.
•  » » » » » » 2 months ago, # ^ |   0 Oh that's fine. But not sure how you can do P1 without graphs, it seems fairly graphy just by looking at it right? Like it's obvious that a greedy approach ain't gonna cut it.
•  » » » » » » » 2 months ago, # ^ |   0 Yeah, pretty sure my friend wasn't thinking straight when they said it was straight-forward implementation. I'm guessing there might be a binary search way to do it too.
•  » » » » » » » » 2 months ago, # ^ |   0 Yes, to my knowledge the solution for P1 could be solved well with the Turtle and Hare approach for finding cycles and solving each component individually: I got the logic right but didn't finish implementing in time, hence, the ask for more implementation-hard DFS (and functional graph especially) problems!