[FWD] Solving the 2x2x2 Rubik's Cube

Document: http://lghttp.38568.nexcesscdn.net/8013252/pdf/uploads/general_content/Rubiks_Cube_2x2x2_solving_guide.pdf


Comments:

• Step 1: Solving the first layer (white) as 3x3x3.
• Step 2: Orienting the yellow face.
• There are only seven possible cases.
• Left Soon algorithm: L' U' L U' L' U2 L
• Right Soon algorithm: R U R' U R U2 R'
• Step 3: Permuting the second layer.
• x R' U R' D2 R U' R' D2 R2 x'

[HackerRank] Practice Interview Preparation Kit: Dynamic Programming

Link: https://www.hackerrank.com/interview/interview-preparation-kit/dynamic-programming/challenges

---

1. Max Array Sum: https://www.hackerrank.com/challenges/max-array-sum/problem

Solution: Naive dynamic programming. Time = O(n), Space = O(1).

• Define 
• f(i): max subarray sum from 1 to i which contains the last element.
• g(i): max subarray sum from 1 to i which does not contain the last element.
• Answer = max(f(n), g(n)).
• Recursive formula:
• f(i) = g(i - 1) + a[i]
• g(i) = max(f(i - 1), g(i - 1)).

#!/bin/python3

import math
import os
import sys

# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
    best_w_last, best_wo_last = 0, 0
    for a in arr:
        best_w_last, best_wo_last = best_wo_last + a, max(best_w_last, best_wo_last)
    return max(best_w_last, best_wo_last)
        
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = list(map(int, input().rstrip().split()))
    res = maxSubsetSum(arr)
    fptr.write(str(res) + '\n')
    fptr.close()

---

2. Candies: https://www.hackerrank.com/challenges/candies/problem

Solution: Two pass greedy algorithm. Time = O(n), Space = O(n).

#!/bin/python3

import math
import os
import sys

# Complete the candies function below.
def candies(n, r):
    c = [1 for i in range(n)]
    for i in range(1, n):
        if r[i] > r[i - 1]:
            c[i] += c[i - 1];
    for i in range(n - 2, -1, -1):
        if r[i] > r[i + 1]:
            c[i] = max(c[i + 1] + 1, c[i])
    return sum(c)    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    arr = []
    for _ in range(n):
        arr_item = int(input())
        arr.append(arr_item)
    result = candies(n, arr)
    fptr.write(str(result) + '\n')
    fptr.close()

---

3. Abbreviation: https://www.hackerrank.com/challenges/abbr/problem

---

4. Decibinary Numbers: https://www.hackerrank.com/challenges/decibinary-numbers/problem

[ProjectEuler][Problem 215] Crack-free Walls

Problem statement:

• Origin: https://projecteuler.net/problem=215
• HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler215
• Solution: DP: https://github.com/Meng-Gen/ProjectEuler/blob/master/215.cc

Similar Problem (but not the same):

• Statement: https://www.hackerrank.com/challenges/lego-blocks/problem
• Solution: https://yuting-zhang.github.io/hackerrank/2017/10/18/Hackerrank-lego-blocks.html

[2012 Chicago Invitational] Covered Walkway

Category: DP + Convex Hull Trick

Problem statement: https://open.kattis.com/problems/coveredwalkway

[IOI 2002] Batch Scheduling

Category: DP + Convex Hull Trick

• Categorized by https://codeforces.com/blog/entry/8219

Problem statement: https://ioinformatics.org/files/ioi2002problem4.pdf

• IOI 2002: https://ioinformatics.org/page/ioi-2002/28

Convex Hull Trick:

• https://jeffreyxiao.me/blog/convex-hull-trick/

[IOI 2014 Practice Contest 2] Guardians of the Lunatics

Category:

• DP + Divide and Conquer Optimization
• DP + Knuth Optimization

Problem statement: https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14


Solution: https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14/editorial


Knuth Optimization:

• Paper: http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p429-yao.pdf
• DP formulation:
• c[i, i] = 0
• c[i, j] = w(i, j) + min_{i
• Quadrangle Inequalities (QI): w(i, j) + w(i', j') ≤ w(i, j') + w(i', j) for all i ≤ i' ≤ j ≤ j'.
• Monotone on the lattice of intervals: w(i, j') ≤ w(i', j) for all i ≤ i' ≤ j ≤ j'.
• Theorem: QI + Monotone => Time = O(n^2).
• Lemma 1: w(i, j) is QI + Monotone => c[i, j] is QI.
• Lemma 2: 
• Define c_k(i, j) = w(i, j) + c[i, k-1] + c[k, j].
• Define K_c(i, j) = max{ k : c_k(i, j) = c[i, j] }.
• c[i, j] is QI => K_c(i, j) ≤ K_c(i, j + 1) ≤ K_c(i + 1, j + 1).

[Dynamic Programming] Optimal binary search trees

Quote from Section 15.5 from CLRS, Introduction to Algorithms, 3rd.

Definitions:

• \sum p_i + \sum q_j = 1.
• E[search cost in T] = 1 + \sum depth(k_i) p_i + \sum depth(d_j) q_j.
• e[i, j] = the expected cost of searching an optimal BST containing the keys k_i, ..., k_j.
• When j = i - 1, e[i, j] = q_{i - 1} by definition. (When j = i - 1, there are no actual keys; we have just the dummy key d_{i - 1}.)
• i from 1 to n + 1.
• j from 0 to n.
• w(i, j) = \sum_{l from i to j} p_l + \sum_{w from i - 1 to j} q_l.
• i from 1 to n + 1.
• j from 0 to n.
• w[i, j] = w[i, j - 1] + p_j + q_j.
• If k_r is the root of an optimal BST, we have
• e[i, j] = p_r + (e[i, r - 1] + w(i, r - 1)) + (e[r + 1, j] + w(r + 1, j)).
• e[i, j] = e[i, r - 1] + e[r +1, j] + w(i, j) 
• since w(i, j) = w(i, r - 1) + p_r + w(r + 1, j).
• e[i, j] =
• q_{i - 1} if j = i - 1.
• min_{r from i to j}{ e[i, r - 1] + e[r + 1, j] + w(i, j) }.
• Define root[i, j] be the index r for which k_r is the root of an optimal BST containing key k_i, ..., k_j.

Naive algorithm, Time = O(n^3)

• let e[1 .. n + 1, 0 .. n], w[1 .. n + 1, 0 .. n], and root[1 .. n, 1 .. n] be new tables
• for i = 1 to n + 1
• e[i, i - 1] = q_{i - 1}
• w[i, i - 1] = q_{i - 1}
• for l = 1 to n
• for i = 1 to n - l + 1
• j = i + l - 1
• e[i, j] = infinity
• w[i, j] = w[i, j - 1] + p_j + q_j
• for r = i to j
• t = e[i, r - 1] + e[r + 1, j] + w[i, j]
• if t < e[i, j]
• e[i, j] = t
• root[i, j] = r
• return e and root

Knuth Optimization, Time = O(n^2)

• Fact: root[i, j - 1] ≤ root[i, j] ≤ root[i + 1, j].
• Change the innermost for loop to for r = root[i, j - 1] to root[i + 1, j].