I just finished Codeforces Round 1065 (Div. 3), and it was a wake-up call. I couldn't solve either of the two constructive problems (E, F).
When I see a constructive problem, my mind goes blank. I start guessing patterns randomly, which never leads to a solution. It feels like I'm just supposed to magically "see" the answer, and I always fail to find a solid starting point. Before I know it, the time is gone.
How to improve my constructive skill? Any advice would be greatly appreciated. Feeling stuck.
Weirdly, constructive problems are my strongest.
Whenever I read that “there always exists a solution and it’s provable,” most of the time—especially for easier problems—I first build a partial construction, even if it breaks some constraints. Then I try to optimize it and prove that a valid construction is possible within the constraints.
For Div 3 E: I actually read the problem wrong during the contest (I was confused for 45 minutes :(). But after reading the problem again, it turned out to be very easy.
You can clearly see that we want to use even numbers for padding (the more we have, the better, but we only get n/2). The rest is just figuring how to place the odd numbers (just use primes and their odd multiples).
Thanks.
The solution can be literally anything, that's why I never know where to start.
The best way to improve at constructive problems is to solve more constructive problems.
Yeah, maybe. It's just what everyone tells me.
I am new here can you give me some tips?
solve problems and you'll improve yourself.
I start with writing greedy solutions that just construct the answer directly, then if it gets a TLE I start to optimize it. After getting it down to a reasonable time complexity, the rest is proof by AC. I'm rather weak at constructive problems too.
Almost the same.
Personally, I try to approach constructive problems by looking at extreme or simple cases first. For example, I check whether edge cases satisfy the conditions, and if not, I try fixing part of the construction using very simple values like 0 or 1, then adjust the rest accordingly.
This often helps me find a direction. But ultimately, the biggest improvement comes from building intuition — the more you solve, the faster those key observations appear.
Hope this helps! It’s just the method that works for me so far.
PRACTICE
I got stuck on E before I could even look at F; but in hindsight looking at these two problems, here's my $0.02:
• Start small:
Can you find a solution to small problems, better yet, optimal ones? Take E, for example. If n = 6, you know that 2, 4 and 6 have common denominator 2, so if you have any two of these values in a given contiguous triplet, that triplet is considered good. What's the longest array you can generate that guarantees each triplet is good? Now, do n = 8. This gives you a general idea of what to look for.
•Work through the test cases, and formulate some of your own:
This one applies more to F. Draw out what a test problem looks like. Take the following problem, for example: [2 4 6 1 3 5]. Make 2 a root. 4 and 6 clearly link to 2. 1 cannot link to anything, so it becomes a second, disjoint root. 3 can clearly link to both 2 and 1. Can you find a way to path both roots using 3?
A slightly varied example: [2 4 6 3 1 5]. 2 through 6 is same as before. 3 is less than 4 and 6, but is greater than the root 2. 1 is once again disjoint, and 5 can join them both.
Once you've worked through the specific problems by hand, you develop a high level understanding of what it is you plan to do, now it's just a matter of formalising it with an algorithm, and putting it to code.