TL;DR -> Recently while solving 2211B - Mickey Mouse Constructive in contest, i could not solve it.
Since it was problem B , i thought of solving it quickly to move to C.
I could not get any lead in the problem. Whatever i thought was giving no output overall. For any idea that i thought there were two scenario in how i devote my time:
1. Try to prove why it is correct solution and then write code and submit. 2. Assume it is correct and write code and submit.
Generally i try to go with first approach but for constructives it is generally an opaque wall for me. On the other hand i could write code for my solution in no time.
All approaches gave WA one after another. Any attempt to relate it with problem i have done so far seemed futile.
Contest which i most of the time enjoy, turned into a torture. For the next 90 minutes i would write code , submit and get WA and try again.
Brain got Cooked for 90 minutes, it seemed.
Can someone help me(Reading Consructive Problems' editorial seems like setter got the problem and solution in sleep the previous night and still decided to keep the problems for Sadistic purposes).
I have not tried any Problem after that and for the first time in 2 years , i have thought of trying something else in my free time.
If you want to learn to solve constructive, then you need to try really hard to solve them, at a lower rating, then you usually solve, then a bit higher, then a bit higher, it shouldn't take too much time, to get to the level, where you can solve them, if you can do harder problems. For example, I felt I was bad at combinatorics, but then I put effort into solving a few 1500 rated problems, and I feel it's better now, then it was, thought I mostly practice 1700-1800.
Thanks for the reply. But i feel like they are untrainable.
You can solve any other topic and get a flow of how generally problems work out in the end.
BUt for these, there is no element of practise makes perfect. I have also seen some high rated have the same opinion.
You have different ways to get solution:
Solve problem for $$$y = 0$$$. Its easy to see that answer is number of divisors of $$$x$$$. After that just generalize solution.
Lets look at one partition of array. Let's say $$$S$$$ is sum of each subarray. Then its easy to see that $$$S \cdot k = x - y$$$. where k is number of subarrays. So $$$S$$$ is divisor of $$$x - y$$$. And for every $$$S$$$ that divides $$$x - y$$$ we can provide at least one partition with sum $$$S$$$. So lowerbound for problem is number of divisors of $$$x - y$$$. After that just try to find answer for example with consecutive 1's and -1's(first thought). Answer for it matches with lowerbound.
You can see that the problem is not that hard. It requires math thinking and experience with number theory problems. There is no hard guessing in 2nd way of solving. I think you should focus on solving math problems.
When you solve so called 'constructive' problems often you don't need guessing. Your goal is to find upper/lower bound for answer. After that think how final example should look like to reach that upper/lower bound. In this case it's just consecutive 1's and -1's.
bro, you just need a copybook and a pen, draw a lot of tests and think for them, then try to divide them and you will find a pattern. That's how i solve most of the constructive alghorithms.
thanks , will keep that in mind :)
Heyy, I had the exact same experience with the same problem couple days ago (played after contest).
My mistake: didn't read the problem well. I assumed it was talking about subsets when I read "by deleting elements" in the statement without finishing the sentence. So I ignored ordering and I was solving it as a huge combinatorics problem and that was an absolute pain.
Reading the editorial after hours of being stuck looked like it said a whole bunch of nothing (because I still misunderstand the statement). after hours of misery, I realized that the arrays we'll be taking are contiguous subarrays, ordering makes sense, minimizing f(a) is a thing.
After getting that part, the problem made total sense, if we're incrementing the sum by only 1 and -1, that means from 0 to x+y we're passing through all the numbers at least once, minimizing the number of passes by a number is minimizing fluctuations and sorting the array, that's all I needed, and I hope this is the observation that you needed too.
Oh, don't just let 1 hard problem stop you from doing CP!
LEAVE FASTER!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
you can only ragebait yourself and grow!