PurpleThinker's blog

How LEGENDARY programmers solve the A + B problem
By PurpleThinker, 4 years 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.

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

Comments Comments (20)
| Write comment?
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

as a legendary programmer, I agree that Brainfuck is the best programming language in the world

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

If you don't wanna learn a new programming language like brainfuck and already know some javascript, but still wanna use a minimalistic programming style, then you must definitely try JSFuck. For example, this is a "Hello World!" program.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

LoL, I thought he was joking about Brainfuck.

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For the first time in history,a programming language's name actually makes sense.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, i remember once trying to figure out the number of numbers between L,R in brainfuck as part of a contest. I struggled for an hour for the edge case when L was equal to R.

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In search of Gold : C++ , Java, Python

We found a Diamond : Brainfuck!!

→ Reply
»
4 years ago, # |
  Vote: I like it +173 Vote: I do not like it

I tried a novel solution. First, sleep for A milliseconds, then sleep for B milliseconds, then measure how much time passed since the start. Unfortunately, there a few problems with this approach. Firstly, in the worst case of A = B = 1000, this will take 2 seconds and TLE. Secondly, A and B can be negative, so it only works on programming languages with built-in support for time travel. Another issue is that there isn't a good enough way to measure time without serious precision error. I wish competitive programming was friendlier to clock-based algorithms.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Indeed, clock-based algorithms are really underrated. Fortunately, rumours say that the future C++23 standard will fully support time travel and have predefined functions that solve all the time travelling paradoxes in linear time

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      I'm looking forward to solving watermelon with Hitler.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Real programmers wait for the contest to end, read the editorial and then write a code which time travels back to submit itself.

    And of course there's a Haskell technique to do that.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This blog made me click on the upvote button multiple times hoping it would work

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

That’s awesome

→ Reply
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it 
global main
extern printf
extern scanf

section .text
main:
    push rsp
    mov rdi, inp
    mov rsi, a
    mov rdx, b
    call scanf
    pop rsp

    xor rsi, rsi
    add rsi, [a]
    add rsi, [b]

    push rsp
    mov rdi, outp
    call printf
    pop rsp

    mov rax, 1
    mov rbx, 0
    int 80h
section .data
    outp: db "%d", 10, 0
    a: dq 0
    b: dq 0
    inp: db "%d %d", 0
→ Reply