Hello Codeforces!
Recently i observed that i am too bad with problems that require -:
1. Tricky observations or lots of observation
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.
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.
I'm shame to say that I didn't solve magic grid in contest even if I was orange :/
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.
Just a little correction, the XOR of any 4 consecutive numbers starting from an even number is 0
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.
Do you know some other problems like "magic grid", that will be good to practice.
If you want another problem where 'using the condition' is really important, try IOI 18 combo maybe?
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.
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.
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.
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 }:-)
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.
In simple words, it means increase your IQ??
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.
Few problems that change the way you see those kinds of problems is better than a lot of nonsense problems.
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 :)
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.
Does this mean harder problems are usually key problems?
The other way around, key problems are usually harder problems. You won't learn much from solving problems you can solve in 20 minutes.
It means Solving '5' harder problem is equal to solving '100' easy problems? :)
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?
git gud
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?
Later I solve this problem as partition problem by making a, b, c < 100 and distribute remaining equally in both set.
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
That is I must say, REALLY NICE! This approach is actually, really helpful to think differently.