monopoly's blog

Hard to notice graph problems
By monopoly, 7 weeks 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.

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

Comments Comments (27)
»
7 weeks ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

problem 1, problem 2

→ Reply
»
7 weeks 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...

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

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

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    True

    → Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 weeks 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.

      → Reply
      • »
        »
        »
        »
        7 weeks 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.

        → Reply
        • »
          »
          »
          »
          »
          7 weeks 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???

          → Reply
          • »
            »
            »
            »
            »
            »
            7 weeks 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 weeks 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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks 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."

                → Reply
    • »
      »
      »
      6 weeks 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.

      → Reply
      • »
        »
        »
        »
        6 weeks 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.

        → Reply
        • »
          »
          »
          »
          »
          6 weeks 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.

          → Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://open.kattis.com/problems/dontfencemein

https://acm.timus.ru/problem.aspx?space=1&num=1035

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Couple of nice problems in a recent Atcoder contest.

https://atcoder.jp/contests/arc111/tasks/arc111_b

https://atcoder.jp/contests/arc111/tasks/arc111_c

→ Reply
»
7 weeks 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.

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay, I've added spoiler tag, you can ignore them if you want. And knowing problems can help you in another way such that you can get used to different problem types and determine similar problems when you see them again.

    → Reply
  • »
    »
    6 weeks 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).

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

From last ABC — https://atcoder.jp/contests/abc188/tasks/abc188_f

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/arc111/tasks/arc111_b

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

this one

→ Reply
»
6 weeks 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).

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Search USACO guide

should help : )

→ Reply
»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

POI Sums

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

1467C - Three Bags This problem doesn't use any graph algorithm but can be solved only after modeling problem as a graph.

→ Reply