ReaLNero's blog

By ReaLNero, 15 months ago, In English

Constructive algorithms are a common sight in both olympiads and online programming contests. If you’re looking for some examples, check out the CodeForces problemset, filtering for “constructive algorithms”.

Definition

What’s a constructive algorithm, exactly? I think it’s most helpful to give an example problem:

Let $$$1 \leq N \leq 10^5$$$ and $$$1 \leq K \leq log_2(N)$$$ be fixed. Imagine performing a binary search on the values $$$1...N$$$. Give a value X, $$$1 \leq X \leq N$$$ which would be found in exactly K steps using binary search.

There's a bunch of variations on binary search, so assume I chose a particular one in this example.

We’re supposed to generate an example number which satisfies the above condition (found in exactly K steps of a binary search). Of course, contests add parameters to these conditions, so that multiple test cases can be given. In almost all constructive algorithm problems, there are a lot of possible solutions, and usually any example which satisfies the conditions is accepted.

Since there are multiple solutions, you have to find a pattern that can be generated programmatically, and implement it. These problems are usually ad-hoc, with little knowledge of data structures and algorithms needed. People with strong mathematical creativity especially shine in this category of problems. The normal strategy for these problems is to manually solve a few example inputs, and try to generalize your thinking process.

If you don’t come from a mathematical background, I can offer some hacky strategies on solving these problems without requiring much creativity on your side...

Strategy

Notice that the conditions in this problem can be tested with a simple script. You shouldn’t worry about complexity on your script, since we’ll only care about small values of $$$N$$$, as larger answers will be difficult to inspect manually.

Now that we have an algorithm which checks if an answer is correct, we can create another function which generates all possible answers, and use both functions to generate a (slow!) solution.

This is very valuable -- instead of having to solve examples yourself, you can just use this solution to see what correct answers look like for different parameter values. So time to put on your detective hat, and try to find a pattern in the outputs you see!

Let's say we're testing $$$N=16, 1 \leq K \leq 4$$$ in the problem above

$$$N=16, K=1$$$: only X=8 works.

$$$N=16, K=2$$$: both X=4 and X=12 work.

$$$N=16, K=3$$$: X=2, X=6, X=10, X=14 work.

$$$N=16, K=4$$$: X=1, X=3, ...

Focus on the very first input we get for each $$$K$$$: it's 8, 4, 2, 1! It seems like there’s a pattern that we can use: we start with N and divide by 2 (rounding down) K times.

Now that we have a pattern, we ought to prove it… In case you are time constrained or have difficulty proving it in the first place, you can just go ahead and use the script: write out your proposed solution, and test as many parameter values as you can with your two solutions. You are probably going to miss most parameter values, but that’s okay: patterns rarely break for N >= 4030, and it’s worth the penalty to see if you’re right.

If a problem of this type has a well-hidden pattern, this strategy shines: you can test patterns as fast as you can write them up. If you didn't have this script ready, you would have to execute the algorithm on paper, which is both slower and more error-prone.

A drawback of this approach is that you might spend time writing scripts without getting any further insight. So consider the risk before attempting this approach -- try the other problems first perhaps?

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

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

Can you explain the reason for saying patterns rarely break for N >= 4030.

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

    Read it as patterns rarely break for N >= a lot

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

      Ok, seems he intended a joke.

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

      I understand what the phrase means(if its working for most small answers it most probably is right) but I wanted to ask is 4030 a special number for any reason? okwedook ReaLNero

      Also on a side note, is there a question in which you applied a heuristic and it failed for a large case(not due to overflow, MLE, TLE but because the logic failed on a much larger case)?

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

        My comment says the opposite:/

        I don't think my solutions ever failed working correctly for n <= 4030. But there are still tasks, where you need to combine different solutions and this opens an opportunity to make bugs:)

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

        Hi! 4030 isn't a special number.

        It's easy to come up with a bunch of problems that have a solution that fails for $$$n geq 4030$$$. But people creating tasks first think of challenging but fun problems first, and don't really focus on messing with approaches like this.

        And even if this approach fails, for all the other contests, you'd be sure to save a lot of penalty time. So it's a net + in the end.

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

I'm an asian and if I take patterns rarely break for N >= 4030 as an axiom, my mother will kill me.

»
9 months ago, # |
  Vote: I like it -11 Vote: I do not like it

great work man!!