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?

Read more »

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

By ReaLNero, 4 years ago, In English

The recurrence

f(i, i) = 0

f(i, j) = g(f(i, j - 1), f(i + 1, j)) + cost(i, j)

for any function g and cost (minimum and (i + j), respectively, for example) generates a family of graphs that (informally) look like a complete binary tree that cuts into itself.

Has this family of graphs been named? Does it have properties that could be useful in competitive programming?

Notable things:

  • The graphs have no Euler path nor circuit for depths larger than 2.

  • Maximal independent set is taking the last depth, third last depth, etc.

  • Seems like Hamiltonian paths don't exist for larger depths.

  • Hamiltonian circuits definitely don't exist, since there are vertices with degree 1.

  • Odd cycles don't seem to exist, which means the graphs are bipartite

Screenshot courtesy of VisuAlgo

Read more »

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