brdy's blog

Good ad-hoc problems
By brdy, history, 6 years ago, In English

Hello guys, if you analyze a lot of past codeforces problems in div2 you can notice knowledge of standard algorithms/ds is useful but not necessity. That segment tree solution can be done with set, or with prefix sum style sweeping.

Actually the most important "algorithm" in these problems is using your brain as someone said here.

That is why I want to ask the community for some great ad-hoc problems that have made you think/taught you important concepts or observations. (For example, you can add X to a set of numbers in O(1) by keeping global variable) I think these skills of making observations/simplifying the problem/looking at the problem from different angles is something me and many other coders are lacking, and it would especially help someone like me who is good at standard stuff but quite lacking in problem-solving skill.

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

Comments Comments (20)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really enjoyed solving 279C. It taught me how the cumulative sum technique (which is very common in ad-hoc from my experience so far) can be used to solve problems which may otherwise TLE with bruteforce methods. There is no editorial either, so that was an incentive for me to try it.

→ Reply
»
6 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Finally! A sensible question.

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

    Disappointing to see a normal comment from you. Was expecting you to fight and make an issue.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

      Loooolloooloool. People who get demoted back to pupil again after so many contests and so much "upsolving" have a tendency not to use their brains. Lol.

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

        Lmao. Now this is more like you.

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

          I know that Lance sometime trolls/roasts people, but is it necessary to provoke him? I just want some good adhoc problems (and I'm sure other people too) but if the first thing commentators see is this bullshit, how do you expect people to even take this post even semi-seriously?

          I ask that both of you cut it out, it's not worth either of your time.

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

I have found many of these kinds of questions on AtCoder.

I shall provide a few samples.

Modulo Summation

Insertion

Takahashi's Information

Five Five Everywhere

A CF question —

Petya and Friends

This list isn't intended to be exhaustive. Most C-D level problems fall under this category. Very rarely they require knowledge of advanced data structures or algorithms. Most of the problems I sent above need quick observations.

I have also provided posts for all the above problems which you can find via this index. :)

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

Upvoted for tags

→ Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Start solving the most solved questions in the problem set by applying the filter. I solved about 100 of them and now I'm a little bit confident about solving div2B questions. You could see from my graph that earlier I struggled so much even to reach 1200. Now I'm somewhat confident of staying in green at least.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    As someone who started gray (not on this account, my embarrassing past account :c ) because they barely know how to code and now is stable blue (hoping to be purple soon) I can say that I have done something similar (solved dozens of usaco problems, then past codeforces problems on my weakness) and it has made a big difference, but this sort of systematic preparation (at least for me) only marginally increased my ad hoc abilities. This is especially because I grouped my weaknesses "topic-wise" (standard topics) and because many USACO problems lend themselves to the same topics (graphs/tree, data structures, dp) again and again.

    But what about problem-solving skill? What about making observations, or being creative? I know people who make div1 when they knew far less about standard algorithm + data structure from me. Some people say well "they are smarter" or "brain structure" but it's not too difficult to realize brain structure is a result and not just a cause.

    So god damn it I need some good ad hoc problem, not just this advice of "solve more problem" which I am already doing.

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

      ¯_(ツ)_/¯

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

        lol

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it -15 Vote: I do not like it

          Lol these guys are so funny. At least be mature guys. These down votes means literally nothing to me lol lol. Down vote this too hahaha lol

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

            From what I understand from your comments you completely ignored who the poster was, what the poster was asking (all you had to do was read the title), and now say something like "I don't give a flying f__ about you" when you receive even slightest criticism. I don't really think you can be telling others to be mature.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it -13 Vote: I do not like it

              From what I understood from your comment you completely take care to show off saying that you solved many data structures graphs trees dp blah blah blah and you are good at not knowing how to even respond to a comment without the slightest feeling of how the other person would react and finally you are very good at using GOD DAMN IT. So yeah I won't give a flying f___ about you again

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

                Actually I was explaining that I had already done something you mentioned (solve a lot of problem systematically). And no I wasn't intentionally bragging (who even brags about being blue anyways) I think flexing your rating is pathetic waste of time; we do contest to learn not to look "mentally buff" So stop trying to make your act look justified. I'm going to end this conversation here because I value my time.

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

https://codeforces.net/contest/91/problem/B

This is one I solved very recently while climbing the A2OJ D ladder. I reflexively went for the segment tree solution, having a gut feeling that there was a simpler solution but not taking the time to think of it. There's a much more elegant solution involving one of the most simple algorithms.

Another problem: find the number of inversions of an array (not necessarily a permutation). The classic way I hear about people doing this (and the way I would do it myself) was value compression + fenwick tree. I recently came across a much more elegant solution in a Quora answer that (again) appeals to a very simple algorithm: https://www.quora.com/Why-should-competitive-programmers-know-about-sort-algorithms-when-in-contests-we-use-std-sort/answer/Jonathan-Paulson

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

    Thank you for sharing!

    I've always liked the idea that you can solve inversions (basically a problem asking how "sorted" the array is) by sorting itself. For inversions, it was because I was told I could use mergesort that I was able to figure it out that you can count the inversions between merges (and by viewing the mergesort as a mergesort tree you can see for a position i it considers all inversions < i).

    But what about non-standard "sort" problems.

    For example, this: http://usaco.org/index.php?page=viewproblem2&cpid=837

    The model solution is BIT, but can this also be solved by modifying/analyzing some nlogn sorting method?

    Just a food for thought.

    → Reply