Project Euler 116 & 117

I solved both problems during my vacations and my stay in Rome.

I tried to look up the code for these, but it seems that the terminal emulator file system on my phone is broken (yes, I can code on the phone). However, I was able to find some hand notes on my thoughts for these problems.

Problem 116

Red, green or blue tiles

So, this is a simple DP problem. Just think a bit about the possible cases:

1. What about if I wanna leave the last element empty?

$ DP[n] = DP[n-1] $

1. What about if I wanna take the last element and colored it?

$ DP[n] = 1 + DP[n-2] $

$ DP[n] = DP[n-1] + DP[n-2] + 1 $

It’s easy to extend it to the other colors.

#include <iostream>
using namespace std;
typedef long long ll;

ll dp[55][5];

void fill(){
    for(int i=0; i<55; i++){
        for(int j=0; j<5; j++) dp[i][j] = -1;
    }
}

ll solve(int p, int color){
    if(p < color) return 0;
    if(p == color) return 1;
    if(dp[p][color] != -1) return dp[p][color];

    ll ans = solve(p-1, color) + solve(p-color, color) + 1;
    dp[p][color] = ans;
    return ans;
}

int main(){
    fill();
    ll ans = 0;
    for(int i=2; i<5; i++)
        ans += solve(50, i);
    cout << ans << '\n';
    return 0;
}

Problem 117

Red, green and blue tiles

The next problem it’s really similar, in this case we have the possibility to use different colors.

The idea is the same. Take a look to the cases:

What about if I wanna leave the last element empty?

$ DP[n] = DP[n-1] $

What about if I wanna color the last element with the first color?

$ DP[n] = DP[n-2] $

What about if I wanna color the last element with the second color?

$ DP[n] = DP[n-3] $

What about if I wanna color the last element with the third color? $ DP[n] = DP[n-4] $

$DP[n] = DP[n-1] + DP[n-2] + DP[n-3] + DP[n-4]$

#include <iostream>
using namespace std;
typedef long long ll;

ll dp[55];

void fill(){
    for(int i=0; i<55; i++)
        dp[i] = -1;
}

ll solve(int p){
    if(p < 0) return 0;
    if(p == 0) return 1;
    if(dp[p] != -1) return dp[p];

    ll ans = solve(p-1) + solve(p-2) + solve(p-3) + solve(p-4);
    dp[p] = ans;
    return ans;
}

int main(){
    fill();
    ll ans = solve(50);
    cout << ans << '\n';
    return 0;
}