Alex12H's blog

By Alex12H, 7 months ago, In English

Hello, Codeforces! For many of us, the A + B problem was the first one we've solved and we think of it as just a really easy problem. But what if I told you there is a way to flex your programming skills by solving this problem with style? On this wonderful day of March 32nd, I will present a few ways to solve this interesting problem. I will only consider a and b strictly larger than 0.

Noob approach

std::cout << a + b;

Almost-noob approach

Notice that we can interpret a + b as a incrementing a number a times, then b times. We get:

int ans = 0;
for (int i = 1; i <= a; i++) ans++;
for (int i = 1; i <= b; i++) ans++;
std::cout << ans;

Slightly clever approach

Of course, we cannot stop there. A wise man once said: "every competitive programming problem is a dynamic programming problem if you try hard enough". So... let's be a little bit more imaginative! We define dp[i][j] as the result you get if you increment a number i times, then j times. So the final result will be dp[a][b] and the recurrence relation is:

dp[i][j] = 1 + max(dp[i-1][j], dp[i][j-1]), for all i <= a and j <= b.

(the max function is, of course, for aesthetic purposes)

Good programmer approach

Some competitive programming problems require you to transform the task given in the statement into something more manageable and perhaps easier to visualise... what better way to visualise a problem than use graphs! We construct a graph and relabel its nodes like this:

We can see that a + b is in fact equal to the distance between the node labeled a in the upper part and the node labeled b in the lower part. You can now use your favourite graph-traversal algorithm to solve this problem.

What separates good programmers from LEGENDARY programmers

A programming challenge isn't just about algorithms; it can also be about the programming language you use! Of course, if you want to do it the boring way, sure, use C++, Java or Python... However, if you want something more interesting, I will present to you the best programming language in the world: Brainfuck!

Yep, that really exists. Brainfuck is a very minimalist and easy to learn language. In fact, it only has 8 commands: ><+-.,[]. Who needs user-defined functions and comparators and classes that always create bugs, when you've got Brainfuck! For example, this is a "Hello World!" program in this wonderful language:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

That's really it: no clunky and buggy functions and IO stuff. Considering the modern trend of simplifying everything (for example, logos and UIs), sooner or later, the world will throw away C++, Python and Java and use a simplist language, like Brainfuck. Legendary programmers already use this language of the future and solve all competitive programming problems in Brainfuck.

As I just said, Brainfuck is a very easy to learn language. In fact, the implementation of the graph approach to the A + B problem is so elementary, that it is left as an exercise for the reader.

Read more »

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