online advertising

Monday, May 1, 2017

LeetCode OJ - Student Attendance Record II

Problem:

Please find the problem here.

Analysis:

The fun part of doing this problem is the analysis. Here is how I thought about the problem.

Let $ a[n] $ be the number of strings of length $ n $ with 0 absence and ends with 0 late records.
Let $ b[n] $ be the number of strings of length $ n $ with 0 absence and ends with 1 late records.
Let $ c[n] $ be the number of strings of length $ n $ with 0 absence and ends with 2 late records.
Let $ d[n] $ be the number of strings of length $ n $ with 1 absence and ends with 0 late records.
Let $ e[n] $ be the number of strings of length $ n $ with 1 absence and ends with 1 late records.
Let $ f[n] $ be the number of strings of length $ n $ with 1 absence and ends with 2 late records.

It is easy to see these are all possibilities for any string that can be rewarded. Now let's take a look on how to compute the value of these for arbitrary $ n $.

It is also pretty obvious that the initial conditions works:

$ a[1] = 1 $, this is the string 'P'.
$ b[1] = 1 $, this is the string 'L'.
$ c[1] = 0 $, there cannot be any.
$ d[1] = 1 $, this is the string 'A'.
$ e[1] = 0 $, there cannot be any.
$ f[1] = 0 $, there cannot be any.

And here are the recurrence relations:

$ a[n + 1] = a[n] + b[n] + c[n] $.
$ b[n + 1] = a[n] $.
$ c[n + 1] = b[n] $.
$ d[n + 1] = a[n] + b[n] + c[n] + d[n] + e[n] + f[n] $.
$ e[n + 1] = d[n] $.
$ f[n + 1] = e[n] $.

Solution:

Given the recurrence it is pretty easy to write the code. Care is taken to make sure we never overflow by making sure we do the mod operation for every addition.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/student-attendance-record-ii

#include "LEET_STUDENT_ATTENDANCE_RECORD_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_STUDENT_ATTENDANCE_RECORD_II
{
    class Solution {
    public:
        int add(int x, int y)
        {
            return (x + y) % 1000000007;
        }

        int checkRecord(int n) {
            if (n == 0)
            {
                return 0;
            }

            int a = 1, b = 1, c = 0, d = 1, e = 0, f = 0;

            for (int i = 1; i < n; i++)
            {
                int ta = add(add(a, b), c);
                int tb = a;
                int tc = b;
                int td = add(add(add(add(add(a, b), c), d), e), f);
                int te = d;
                int tf = e;

                a = ta;
                b = tb;
                c = tc;
                d = td;
                e = te;
                f = tf;
            }

            return add(a, add(b, add(c, add(d, add(e, f)))));
        }
    };
};

using namespace _LEET_STUDENT_ATTENDANCE_RECORD_II;

int LEET_STUDENT_ATTENDANCE_RECORD_II()
{
    Solution solution;
    for (int i = 1; i <= 50; i++)
    {
        cout << solution.checkRecord(i) << endl;
    }
    return 0;
}

No comments :

Post a Comment