karthiksing05's blog

Good functional graph problems...
By karthiksing05, history, 21 month(s) ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 -> D

B -> E

C -> F

which 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!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :(

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Of course, it was after the contest window closed.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply