ReaLNero's blog

By ReaLNero, 22 months ago, In English

Constructive algorithms are common in both olympiads and online programming contests. If you’re looking for some examples, filter for "constructive algorithms" in CodeForces's problemset.

Definition

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

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). In almost all constructive algorithm problems, there are many different approaches that all work, and usually any output which satisfies the conditions is accepted.

Usually working out small examples on pen and paper is easy, but it's hard to imagine how solutions can be arrived at programmaticaly for arbitrary $$$N, K$$$.

Furthermore, these problems are usually ad-hoc, so knowledge of data structures and algorithms isn't likely to be of much use. So essentially to solve this problem you need a strong mathematical intuition. The normal strategy for these problems is to manually solve a few small 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$$$, since we just want to find a good programmatical approach to use for our full solution.

After writing a function which validates whether an answer satisfies the condition, we can create another function which generates all possible answers. The combination of both functions makes a slow brute-force.

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. It's instructive to try out other value of $$$N$$$, like $$$17, 24, 1$$$, etc.

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 use the script: run the brute-force and "smart" approach on as many inputs as you can, and see if they differ. You probably won't be able to test all parameter values, but you'll probably cover enough of the input possibilities that you're pretty likely to get it correct. Even if it does turn out incorrect -- you've gotten a bit of penalty time, but can get right on to testing another approach.

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 the script, and learn that there is no easy to figure out pattern. So use your best judgement -- it might be better to switch to another problem.

Hope this helped y'all!

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

»
22 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.

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

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

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

      Ok, seems he intended a joke.

    • »
      »
      »
      15 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)?

      • »
        »
        »
        »
        15 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:)

      • »
        »
        »
        »
        15 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.

»
22 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.

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

great work man!!