brdy's blog

By brdy, history, 15 months 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

»
15 months 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.

»
15 months ago, # |
  Vote: I like it -34 Vote: I do not like it

Finally! A sensible question.

  • »
    »
    15 months 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.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      LMAO. LOOOLOOLLOLLL. ROFL. You really don't get it do you? I only rebuke people who ask stupid questions/make redundant posts.

    • »
      »
      »
      15 months 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.

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lmao. Now this is more like you.

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

          Lol. Lmao. Rofl. So what? That doesn't change the fact that you are still a lowly pupil after so long. What have you been doing seriously? Asking stupid questions or making redundant comments?

        • »
          »
          »
          »
          »
          15 months 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.

»
15 months 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. :)

»
15 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Upvoted for tags

»
15 months 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.

  • »
    »
    15 months 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.

    • »
      »
      »
      15 months ago, # ^ |
      Rev. 2   Vote: I like it -38 Vote: I do not like it
      1. I haven't seen that you are a blue coder. I thought someone might have been in my situation and so I told to solve as many problems as possible. I'm sorry as I don't mean to say this to you. Still, it would be helpful for at least some people.
      2. You just said you solved many usaco problems from dp graphs trees data structures blah blah blah. Are they called as ad-hoc problems ?? GOD DAMN IT don't you even know that ?? GOD DAMN IT how did you even reach blue color ??
      3. GOD DAMN IT did I ask you to solve these dp graphs trees data structures blah blah blah problems again ?? GOD DAMN IT NO. I said to apply the filter and solve them. GOD DAMN IT don't you even know that these filtered problems are ad-hoc problems ?? How did you even reach blue color ??
      4. If you think these filtered problems are GOD DAMN easy for you then move to the third page or fourth page and still they are also ad-hoc. GOD DAMN IT don't you even know that ??
      5. GOD DAMN IT how do these people who ask stupid questions even reach blue..

      Finally I don't give a flying fuck of what you are whether you are a blue coder or planning to move to purple or what ever.

      GOD DAMN IT

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        lol

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

          He deserves that.

        • »
          »
          »
          »
          »
          15 months 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

          • »
            »
            »
            »
            »
            »
            15 months 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.

            • »
              »
              »
              »
              »
              »
              »
              15 months 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

              • »
                »
                »
                »
                »
                »
                »
                »
                15 months 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.

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

                  Lololol I can understand how much you value your time from your comment itself. And again read my 3rd point in the first reply very carefully to find the answer for your above reply. Clearly you ignored what I commented(all you had to do was read the comment) and now saying the same. Damn what a waste of time with you

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

                  we do contest to learn not to look "mentally buff"

                  LanceTheDragonTrainer would like to have a word with you

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

https://codeforces.com/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

  • »
    »
    15 months 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.