AmanGupta_'s blog

By AmanGupta_, history, 4 weeks ago, In English,

Hello Codeforces!

Recently i observed that i am too bad with problems that require -:

1. Tricky observations or lots of observation

2. Brainstorming or finding patterns.
3. Lots of if-else condition and Corner Cases.

Failed to Solve easy problems like Knights , Two Groups hurt a lot.

No matter, whether these problems rated less than my current rating in difficulty, i rarely solve them completely by own.

So here, i request you to suggest your effective strategy to tackle such problems.
Also, Suggest me more problems of these Kind to practice.

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

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Yes, I feel these problems depends on bit of luck or state of mind during contest. But anyway there is some effective strategy, that makes lot's of participant quite good with these problems.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm shame to say that I didn't solve magic grid in contest even if I was orange :/

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Magic grid was a very easy problem for me, but I must admit it was a bit of luck. Basically for such problems it helps to know a lot of facts, for example for this problem I used the following: the XOR of 4 consecutive numbers is always 0. Once you see that N is divisible by 4 (which immediately reminds of the said fact), then it isn't very hard to come up with a solution.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +19 Vote: I do not like it

      Just a little correction, the XOR of any 4 consecutive numbers starting from an even number is 0

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I didn't find it 'easy' but it's I think the fact that 4|n immediately makes you think of how to do the n=4 case and then decompose larger grids into 4x4 grids.

    There was an Um_nik blog post a while back about how problem statements don't have random things thrown in and the 4|n condition certainly isn't random.

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

      Do you know some other problems like "magic grid", that will be good to practice.

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

        If you want another problem where 'using the condition' is really important, try IOI 18 combo maybe?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

As the wise man once said, just solve more of those. Actually, a mathematical background helps a lot, so you can focus on solving math problems/puzzles/reading books/etc. It's not about programming, like at all. GL HF.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Reduction Game, the deciding problem in ICPC online round last year. Makes me cry whenever I think about it.

Observation + The optimal solution is hard to be sure of unless proved = Makes it difficult for people like me

Most people solved it by trying out different test cases and figured out a pattern, that should be the approach since no time to prove in a short contest.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I can totally relate to you. I am really bad with these kinds of problems, not that those are the only ones. I really want to know the strategy to tackle them, more so as they have started appearing frequently in contests.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Some problems, you can add:

Minute to Win It

Circular Walk

Superior Characters

Array Triplets

These problems don't require some advanced technique, yet will challenge you to your limits.

Too much fun }:-)

»
4 weeks ago, # |
Rev. 4   Vote: I like it +19 Vote: I do not like it

I would say that problems like these require more creativity than actual programming. These are the competitive programming problems that you need the famous "think out of the box" skill. There are many ways to acquire that.

Usually, you need to solve more puzzles to improve your way of thinking. It can be by playing strategy games, reading books, talking with friends. But don't only solve something and then go on.

The key here is to understand as many possible ways to do something as you can. Be curious, try to change the problem until you struggle to find a solution. Sometimes you can not solve the original problem, so create an easier version that you can prove it works. Now try to apply it in the original problem.

For example, in the Magic Grid problem, I have tried something like a brute force for small sized squares, it worked, but how to apply it in the bigger square? Well, these giant squares can be splitted into smaller ones. Now the problem is to just apply the same idea in many small squares.

When you are playing something, there is usually a straight path. Also, there also people playing VERY different from the supposed standard path. These people are usually the ones who find bugs and crack the game.

You need to find something that you are interested in and see every possible way to do that. Soon you will find strange ways to do by yourself. This is when you start developing your "think out of the box" skill.

I would say that no one just create something from nowhere. One probably have seen something similar to it. Maybe you were thinking about an algorithm related to the traffic while commuting, but did not give it much attention. Then a random problem during a contest seems similar to your previous thoughts, so you connect some insight points and reach the "a-ha" moment.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In order to have an effective mindset in solving such problems, your brain needs to actually be used to processing such problems.In other words do a lot of such problems.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Few problems that change the way you see those kinds of problems is better than a lot of nonsense problems.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Nobody is going to show you them few problems unless you get a good teacher/instructor, and you gotta find it yourself by solving manyyy problems :)

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

        I did it by myself from trying to solve harder problems when I was cyan/blue, had to spend hours thinking/looking at the editorial/reading through solutions per problem but it was worth it.

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

          Does this mean harder problems are usually key problems?

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

            The other way around, key problems are usually harder problems. You won't learn much from solving problems you can solve in 20 minutes.

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

            It means Solving '5' harder problem is equal to solving '100' easy problems? :)

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

              His words actually make much sense to me I would say. I definitely try to solve harder problems from now on.

              By the way why try to solve 5 when you can try to solve 100 harder problems?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In some contests, these are only the game-changer question and mostly depends on the luck. So just practising more of it will help.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

git gud

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I also struggled a lot while finding different cases for the problem "Two Groups". But my friend Arya Das wrote a very beautiful solution using just some iteration tricks very quickly. aryadas98 can you share it?

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

    Later I solve this problem as partition problem by making a, b, c < 100 and distribute remaining equally in both set.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Thanks intruder_p for mentioning me. First I thought about observing any pattern if present. I observed that most $$$(a,b,c)$$$ tuples could be divided into two groups. Notice that if $$$sum=a+2b+3c$$$ is odd then it is not divisible. Else it may be divisible. If $$$sum=a+2b+3c$$$ then we have to find numbers $$$m,n,o$$$ such that $$$m+2n+3o=\frac{sum}{2}$$$. If $$$m,n,o$$$ were floating point numbers then one solution would be $$$\frac{a}{2},\frac{b}{2},\frac{c}{2}$$$. From this I deduced that the real solution will be close to the floating point solution. Indeed, if you take the floor of everything then the sum you get will differ from the required sum by atmost $$$6$$$. So what I did is, I iterated in between $$$\frac{a}{2}\pm10,\frac{b}{2}\pm10,\frac{c}{2}\pm10$$$ and checked whether anyone summed up to $$$\frac{sum}{2}$$$. Here is the solution: https://www.codechef.com/viewsolution/26731229

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

      That is I must say, REALLY NICE! This approach is actually, really helpful to think differently.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont know but i find codechef long challenge que only to search for a apattern nd optimisisng thm whole day that sucks