monopoly's blog

By monopoly, 3 years ago, In English

Please recommend some graph problems that are hard to determine. I mean there are no vertices or edges in problem statement but you can create(or not) them yourself and apply graph algorithms. I'll add them to this blog.

  • Vote: I like it
  • +12
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

you aren't improving your skills for graph finding if you already know from the start it's a graph problem...

»
3 years ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

?????????????????????

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    True

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    What are the basics? I consider basic graph theory the basics...

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it -38 Vote: I do not like it

      He/She could not solve a single problem in Educational Codeforces Round 102...graph theory is basics, but I suppose when one can't solve an 800 problem, it's this whole new level of basic.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +69 Vote: I do not like it

        It has nothing to with you if I can't solve these problems. I simply asked for problems politely but you humiliate me.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it -23 Vote: I do not like it

          You can always just look for codeforces problems tagged graph theory???

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            I didn't ask for problems from codeforces specifically and there are other OJ's with no problem categories.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it -19 Vote: I do not like it

              Use Google & well-known Morass blog then??? (LeetCode problems tend to be on the easier side, but whatever)

              LeetCode LeetCode LeetCode

              Codeforces Stuff

              CF CF

              And that should be more than enough lmao...stop asking and start DOING

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it +2 Vote: I do not like it

                I didn't know about the Morass blog and probably neither did the author. Try to be more polite, as simple as linking the resources and saying "here you go, hopefully you find them interesting."

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      In my opinion, constructive and mathematical thinking are more 'basic' skills when it comes to CP, along with 'techniques' (using it very vaguely here) such as prefix sums and binary search.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it +5 Vote: I do not like it

        Ig things like basic stl knowledge and basic math like prefix sums is before it, but I would but making an adjacency list to dfs at the same level as binary search (ie I learned them at basically the same time). If I was teaching a class, graph problems would be one of, if not the first topics I introduce since I think it is best way to show both the programming style and mindset of cp (in my cp ideals).

        Anyway I mostly just don't like people telling less experienced they shouldn't be touching "advanced topics" yet.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          That's fair. I learned simple stuff like graph traversal with DFS pretty late compared to other stuff at the same level, so I think I probably have a slightly skewed sense of difficulty for these topics.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

Why the hell you want to spoil the problems? Kind of problems you are asking for are special(rare and difficult) because you don't know graphs are to be used in them. By revealing that graphs are being used, you made the problem a lot easier to solve.

Edit: Others also don't list problems here in which it is difficult to deduce that graphs are needed.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I practice around 50% of my time knowing the category beforehand. If you've had a lot of contests and you know that "hey, I always seem to mess up on graph problems" it's definitely worth it practicing on graph problems (in other words there's nothing wrong with practicing a specific category).

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Hey!

Here's one of my favourite problems (it's the first 'implicit' graph problem I did).

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it