Test results - Codility

Tasks Details

hard

1. TheaterTickets

Given an array A, count the number of different triplets (a, b, c) in which a occurs before b and b occurs before c.

100%

Kate was given a birthday gift of three theater tickets. Now she is browsing the theater program for the next N days. On the program, performances are named by integers. Every day, one performance is staged. Kate wants to choose three days (not necessarily consecutive) to go to the theater.

In how many ways can she use her tickets? Two ways are different if the sequences of watched performances are different. Kate likes the theater, so she may watch one performance more than once. For example, if N = 4 and theater program looks as following: [1, 2, 1, 1], Kate has four possibilities to choose the dates: [1, 2, 1, 1], [1, 2, 1, 1], [1, 2, 1, 1], and [1, 2, 1, 1], but they create only three different sequences: (1, 2, 1), (1, 1, 1) and (2, 1, 1). The correct answer for this example is 3. Notice that the order of performances matters, so the first and the last sequences are considered different.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, denoting names of performances for the next N days, returns the number of possible ways to spend the tickets. Since the answer can be very large, provide it modulo 10⁹ + 7 (1,000,000,007).

For example, given A = [1, 2, 1, 1], the function should return 3 as exmplained above.

Given A = [1, 2, 3, 4], the function should return 4. There are four ways to spend tickets: (1, 2, 3), (1, 2, 4), (1, 3, 4) and (2, 3, 4).

Given A = [2, 2, 2, 2], the function should return 1. There is only one way to spend tickets: (2, 2, 2).

Given A = [2, 2, 1, 2, 2], the function should return 4. There are four ways to spend tickets: (1, 2, 2), (2, 1, 2), (2, 2, 1) and (2, 2, 2).

Given A = [1, 2], the function should return 0. Kate cannot use all three tickets in only two days.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [1..N].

Solution

Programming language used C#

Total time used 1 minutes

Effective time used 1 minutes

Notes

not defined yet

Task timeline

Code: 13:35:02 UTC, cs, autosave

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    private const ulong ModuloValue = 1000000007;
    private ulong GetModuloValue(ulong u)
    {
        return u % ModuloValue;
    }
    public class NumberCombo
    {
        public ulong ComboOfTwo { get; set; }
        public ulong ComboOfThree { get; set; }
    }
    public int solution(int[] A) {
            // total of combinations of two
            ulong totalTwo = 0;
            // total of combinations of three
            ulong totalThree = 0;
            // total of different numbers in the array
            ulong totalDifferentNumbers = 0;
            var numberCombos = new NumberCombo[100001];
            for(var i = 0; i<A.Length; i++)
            {
                var currentNumber = A[i];
                if(i == 0)
                {
                    numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    totalDifferentNumbers++;
                }
                else if(i == 1)
                {
                    if(numberCombos[currentNumber] == null)
                    {
                        totalDifferentNumbers++;
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }

                    numberCombos[currentNumber].ComboOfTwo = 1;
                    totalTwo = 1;
                }
                else // make calculations for combos of three
                {
                    var isNewNumber = numberCombos[currentNumber] == null;
                    if(isNewNumber)
                    {
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }
                    // make calculations about combo of three
                    var currentNumberThreeCombo = GetModuloValue(totalTwo);
                    var deltaThree = GetModuloValue(totalTwo - numberCombos[currentNumber].ComboOfThree);
                    numberCombos[currentNumber].ComboOfThree = currentNumberThreeCombo;
                    totalThree += deltaThree;
                    // make calculations about combo of two
                    var currentNumberTwoCombo = GetModuloValue(totalDifferentNumbers);
                    var deltaTwo = GetModuloValue(totalDifferentNumbers - numberCombos[currentNumber].ComboOfTwo);
                    numberCombos[currentNumber].ComboOfTwo = currentNumberTwoCombo;
                    totalTwo += deltaTwo;
                    // update total different numbers 
                    if(isNewNumber)
                    {
                        GetModuloValue(totalDifferentNumbers++);
                    }
                }    
            }
            return Convert.ToInt32(totalThree);
    }
}

Code: 13:35:13 UTC, cs, autosave

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    private const ulong ModuloValue = 1000000007;
    private ulong GetModuloValue(ulong u)
    {
        return u % ModuloValue;
    }
    public class NumberCombo
    {
        public ulong ComboOfTwo { get; set; }
        public ulong ComboOfThree { get; set; }
    }
    public int solution(int[] A) {
            // total of combinations of two
            ulong totalTwo = 0;
            // total of combinations of three
            ulong totalThree = 0;
            // total of different numbers in the array
            ulong totalDifferentNumbers = 0;
            var numberCombos = new NumberCombo[100001];
            for(var i = 0; i<A.Length; i++)
            {
                var currentNumber = A[i];
                if(i == 0)
                {
                    numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    totalDifferentNumbers++;
                }
                else if(i == 1)
                {
                    if(numberCombos[currentNumber] == null)
                    {
                        totalDifferentNumbers++;
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }

                    numberCombos[currentNumber].ComboOfTwo = 1;
                    totalTwo = 1;
                }
                else // make calculations for combos of three
                {
                    var isNewNumber = numberCombos[currentNumber] == null;
                    if(isNewNumber)
                    {
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }
                    // make calculations about combo of three
                    var currentNumberThreeCombo = GetModuloValue(totalTwo);
                    var deltaThree = GetModuloValue(totalTwo - numberCombos[currentNumber].ComboOfThree);
                    numberCombos[currentNumber].ComboOfThree = currentNumberThreeCombo;
                    totalThree += deltaThree;
                    // make calculations about combo of two
                    var currentNumberTwoCombo = GetModuloValue(totalDifferentNumbers);
                    var deltaTwo = GetModuloValue(totalDifferentNumbers - numberCombos[currentNumber].ComboOfTwo);
                    numberCombos[currentNumber].ComboOfTwo = currentNumberTwoCombo;
                    totalTwo += deltaTwo;
                    // update total different numbers 
                    if(isNewNumber)
                    {
                        GetModuloValue(totalDifferentNumbers++);
                    }
                }    
            }
            return Convert.ToInt32(GetModuloValue(totalThree));
    }
}

Code: 13:35:25 UTC, cs, verify, result: Passed

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    private const ulong ModuloValue = 1000000007;
    private ulong GetModuloValue(ulong u)
    {
        return u % ModuloValue;
    }
    public class NumberCombo
    {
        public ulong ComboOfTwo { get; set; }
        public ulong ComboOfThree { get; set; }
    }
    public int solution(int[] A) {
            // total of combinations of two
            ulong totalTwo = 0;
            // total of combinations of three
            ulong totalThree = 0;
            // total of different numbers in the array
            ulong totalDifferentNumbers = 0;
            var numberCombos = new NumberCombo[100001];
            for(var i = 0; i<A.Length; i++)
            {
                var currentNumber = A[i];
                if(i == 0)
                {
                    numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    totalDifferentNumbers++;
                }
                else if(i == 1)
                {
                    if(numberCombos[currentNumber] == null)
                    {
                        totalDifferentNumbers++;
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }

                    numberCombos[currentNumber].ComboOfTwo = 1;
                    totalTwo = 1;
                }
                else // make calculations for combos of three
                {
                    var isNewNumber = numberCombos[currentNumber] == null;
                    if(isNewNumber)
                    {
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }
                    // make calculations about combo of three
                    var currentNumberThreeCombo = GetModuloValue(totalTwo);
                    var deltaThree = GetModuloValue(totalTwo - numberCombos[currentNumber].ComboOfThree);
                    numberCombos[currentNumber].ComboOfThree = currentNumberThreeCombo;
                    totalThree += deltaThree;
                    // make calculations about combo of two
                    var currentNumberTwoCombo = GetModuloValue(totalDifferentNumbers);
                    var deltaTwo = GetModuloValue(totalDifferentNumbers - numberCombos[currentNumber].ComboOfTwo);
                    numberCombos[currentNumber].ComboOfTwo = currentNumberTwoCombo;
                    totalTwo += deltaTwo;
                    // update total different numbers 
                    if(isNewNumber)
                    {
                        GetModuloValue(totalDifferentNumbers++);
                    }
                }    
            }
            return Convert.ToInt32(GetModuloValue(totalThree));
    }
}

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

example4
Fourth example test.

✔

▶

example5
Fifth example test.

✔

Code: 13:35:30 UTC, cs, verify, result: Passed

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    private const ulong ModuloValue = 1000000007;
    private ulong GetModuloValue(ulong u)
    {
        return u % ModuloValue;
    }
    public class NumberCombo
    {
        public ulong ComboOfTwo { get; set; }
        public ulong ComboOfThree { get; set; }
    }
    public int solution(int[] A) {
            // total of combinations of two
            ulong totalTwo = 0;
            // total of combinations of three
            ulong totalThree = 0;
            // total of different numbers in the array
            ulong totalDifferentNumbers = 0;
            var numberCombos = new NumberCombo[100001];
            for(var i = 0; i<A.Length; i++)
            {
                var currentNumber = A[i];
                if(i == 0)
                {
                    numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    totalDifferentNumbers++;
                }
                else if(i == 1)
                {
                    if(numberCombos[currentNumber] == null)
                    {
                        totalDifferentNumbers++;
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }

                    numberCombos[currentNumber].ComboOfTwo = 1;
                    totalTwo = 1;
                }
                else // make calculations for combos of three
                {
                    var isNewNumber = numberCombos[currentNumber] == null;
                    if(isNewNumber)
                    {
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }
                    // make calculations about combo of three
                    var currentNumberThreeCombo = GetModuloValue(totalTwo);
                    var deltaThree = GetModuloValue(totalTwo - numberCombos[currentNumber].ComboOfThree);
                    numberCombos[currentNumber].ComboOfThree = currentNumberThreeCombo;
                    totalThree += deltaThree;
                    // make calculations about combo of two
                    var currentNumberTwoCombo = GetModuloValue(totalDifferentNumbers);
                    var deltaTwo = GetModuloValue(totalDifferentNumbers - numberCombos[currentNumber].ComboOfTwo);
                    numberCombos[currentNumber].ComboOfTwo = currentNumberTwoCombo;
                    totalTwo += deltaTwo;
                    // update total different numbers 
                    if(isNewNumber)
                    {
                        GetModuloValue(totalDifferentNumbers++);
                    }
                }    
            }
            return Convert.ToInt32(GetModuloValue(totalThree));
    }
}

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

example4
Fourth example test.

✔

▶

example5
Fifth example test.

✔

Code: 13:35:33 UTC, cs, final, score: 100

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    private const ulong ModuloValue = 1000000007;
    private ulong GetModuloValue(ulong u)
    {
        return u % ModuloValue;
    }
    public class NumberCombo
    {
        public ulong ComboOfTwo { get; set; }
        public ulong ComboOfThree { get; set; }
    }
    public int solution(int[] A) {
            // total of combinations of two
            ulong totalTwo = 0;
            // total of combinations of three
            ulong totalThree = 0;
            // total of different numbers in the array
            ulong totalDifferentNumbers = 0;
            var numberCombos = new NumberCombo[100001];
            for(var i = 0; i<A.Length; i++)
            {
                var currentNumber = A[i];
                if(i == 0)
                {
                    numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    totalDifferentNumbers++;
                }
                else if(i == 1)
                {
                    if(numberCombos[currentNumber] == null)
                    {
                        totalDifferentNumbers++;
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }

                    numberCombos[currentNumber].ComboOfTwo = 1;
                    totalTwo = 1;
                }
                else // make calculations for combos of three
                {
                    var isNewNumber = numberCombos[currentNumber] == null;
                    if(isNewNumber)
                    {
                        numberCombos[currentNumber] = new NumberCombo() { ComboOfTwo = 0, ComboOfThree = 0 };
                    }
                    // make calculations about combo of three
                    var currentNumberThreeCombo = GetModuloValue(totalTwo);
                    var deltaThree = GetModuloValue(totalTwo - numberCombos[currentNumber].ComboOfThree);
                    numberCombos[currentNumber].ComboOfThree = currentNumberThreeCombo;
                    totalThree += deltaThree;
                    // make calculations about combo of two
                    var currentNumberTwoCombo = GetModuloValue(totalDifferentNumbers);
                    var deltaTwo = GetModuloValue(totalDifferentNumbers - numberCombos[currentNumber].ComboOfTwo);
                    numberCombos[currentNumber].ComboOfTwo = currentNumberTwoCombo;
                    totalTwo += deltaTwo;
                    // update total different numbers 
                    if(isNewNumber)
                    {
                        GetModuloValue(totalDifferentNumbers++);
                    }
                }    
            }
            return Convert.ToInt32(GetModuloValue(totalThree));
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

example4
Fourth example test.

✔

▶

example5
Fifth example test.

✔

▶

empty
N = 0.

✔

▶

answer_zero
N <= 2, answer is 0.

✔

▶

simple
N <= 4.

✔

0.020 s

▶

the_same_numbers
N = 30, same performance every day.

✔

▶

small_n_small_alphabet
N = 30, at most 4 different performances.

✔

▶

small_n
N = 30.

✔

▶

small_n_permutation
N = 30, all performances are different.

✔

▶

small_n_sorted
N = 30, performances are sorted by name.

✔

▶

large_n_permutation
N = 100,000, all performances are different.

✔

▶

medium_n_small_alphabet
N = 100, at most 10 different performances.

✔

▶

medium_n
N = 100.

✔

▶

medium_n_permutation
N = 300, all performances are different.

✔

▶

medium_n_sorted
N = 300, performances are sorted by name.

✔

▶

large_n_small_alphabet
N = 100,000, at most 10 different performances.

✔

▶

large_n
N = 100,000.

✔

▶

large_n_sorted
N = 100,000, performances are sorted by name.

✔