Welcome to Shanshan Blog!

Leetcode (78, 90) Subsets I, II

2017-03-17

Leetcode

Leetcode DFS

Leetcode 78. Subsets
Leetcode 90. Subsets II

Leetcode 78. Subsets

Leetcode 78. Subsets

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> curr;
        helper(res, curr, nums, 0);
        return res;
    }
    
    void helper(vector<vector<int>> &res, vector<int> &curr, vector<int> &nums, int pos) {
        res.push_back(curr);
        for (int i=pos; i<nums.size(); i++) {
            curr.push_back(nums[i]);
            helper(res, curr, nums, i+1);
            curr.pop_back();
        }
    }
};

Leetcode 90. Subsets II

Leetcode 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,

If nums = [1,2,2], a solution is:

[ [2], [1], [1,2,2], [2,2], [1,2], [] ]

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> curr;
        sort(nums.begin(), nums.end());
        helper(res, curr, nums, 0);
        return res;
    }
    
    void helper(vector<vector<int>> &res, vector<int> &curr, vector<int> &nums, int pos) {
        res.push_back(curr);
        for (int i=pos; i<nums.size(); i++) {
            curr.push_back(nums[i]);
            helper(res, curr, nums, i+1);
            while (nums[i]==nums[i+1])  i++;
            curr.pop_back();
        }
    }
};

Read All

500 Lines or Less Chapter 9: A Flow Shop Scheduler 翻译

2017-03-08

Translation

Python Translation
Christian Muise博士是麻省理工学院CSAIL的MERS集团研究员。他对AI，数据驱动项目，绘图，图形理论和数据可视化以及凯尔特音乐，雕刻，足球和咖啡等各种主题都很感兴趣。

流程调度程序

流程车间调度是运营研究中最具挑战性和研究性最强的问题之一。像许多具有挑战性的优化问题一样，找到实际问题的最佳解决方案是不可能的。在本章中，我们考虑使用本地搜索的技术实现流程车间调度结算。本地搜索可以让我们找到一个“不错的”解决方案，找不到最好的解决方案。在给定的时间内尝试找到新的解决方案，并通过返回找到的最佳解决方案来结束程序。

局部搜索背后的思想是通过考虑类似的解决方案来改进现有的解决方案。求解器使用各种策略（1）尝试找到类似的解决方案，（2）选择有可能的探索的解决方案。实现是用Python编写的，没有外部要求。通过利用一些Python不太知名的功能，解决者在解决过程中动态地改变其搜索策略，基于哪些策略运行良好。

首先，我们为流程车间调度问题和局部索技术提供一些背景资料。然后，我们将详细介绍一般的求解器代码以及我们使用的各种启发式和邻域选择策略。接下来，我们考虑解算器用于将所有内容结合在一起的动态策略选择。最后，我们总结一下该项目以及实施过程中获得的经验教训。

背景

流程调度

流程车间调度问题是一个优化问题，其中我们必须确定作业中各种任务的处理时间，以便安排任务以最小化完成作业所需的总时间。例如，一个汽车制造商有一个装配线，其中汽车的每个部分依次在不同的机器上完成。不同的订单可能有自定义的要求，完成制作整体的任务，例如，从一个车到另一个车。在我们的例子中，每辆车都是一项新工作，汽车的每一部分都被称为任务。每个工作都要完成相同的任务顺序。

流程车间调度的目标是最小化处理从每个工作到完成的所有任务所需的总时间。（通常，这个总时间被称为制造时间）。这个问题有很多应用，但最重要的是优化生产设备。

每个流程车间问题由n个机器和m个作业组成。在我们的汽车示例中，将有n个车站在车上和m车上工作。每个作业都由完整的n任务组成，我们可以假定作业的i任务必须使用机器i，并且需要预定量的处理时间：p(j,i)是作业j的i任务的处理时间。此外，任何给定作业的任务顺序应遵循机器顺序;对于给定的作业，任务i必须在任务i+1开始之前完成。在我们的汽车示例中，我们不想在框架组装之前开始绘画汽车。最后的限制是在机器上不能同时处理两个任务。

因为作业中的任务的顺序是预先确定的，所以可以将流程车间调度问题的解决方案表示为作业的排列。每个机器处理的作业顺序是相同的，并且给定排列，作业j中的机器i的任务计划是以下两种可能性中的最新的：
1. 在作业j-1（即同一机器上的最新任务）中完成机器i的任务，或
2. 在作业j（即同一作业中最近的任务）中完成机器i-1的任务，
因为我们选择这两个值的最大值，所以将创建任一机器i或作业j的空闲时间。正是这个空闲时间，我们最终希望最小化，因为它会使总体制造商的规模更大。

由于问题的简单形式，作业的任何置换都是有效的解决方案，最优解将对应一些置换。因此，我们通过改变作业的排列和测量相应的制作时间来寻找改进的解决方案。在下文中，我们将作业的排列称为候选人。

让我们考虑一个简单的例子，有两个工作和两个机器。第一个工作有任务mathbf{A}和mathbf{B}，分别需要1到2分钟才能完成。第二个任务有任务mathbf{C}和`mathbf{D}，需要2和1分钟才能完成相应的

请注意，之前没有多余的空间给任务。良好的排列指导原则是尽可能减少任何机器的运行时间，而无需处理任务。

局部搜索

当最佳解决方案太难计算时，局部搜索是解决优化问题的策略。直观地，它从一个看起来不错的解决方案转向另一种更好的解决方案。我们将所有可能的解决方案都考虑在下一个点之上，而不是将所有可能的解决方案都考虑在内，我们定义了所谓的邻域：被认为与当前解决方案类似的一组解决方案。因为作业的任何排列是一个有效的解决方案，我们可以查看任何将作业当作局部搜索过程进行洗牌的机制。

要使用局部搜索之前，我们必须回答几个问题：
1. 如何开始？
2. 基于给出的解决方案，我们应该考虑什么邻近的解决方案？
3. 基于候选邻居的集合，考虑哪一个作为下一个？
以下三个部分依次讨论这些问题。

一般解决方案

在本节中，我们提供了流程车间调度程序的一般框架。首先，我们有必要的Python导入和解算器的设置：
```
import sys, os, time, random

from functools import partial
from collections import namedtuple
from itertools import product

import neighbourhood as neigh
import heuristics as heur

##############
## Settings ##
##############
TIME_LIMIT = 300.0 # Time (in seconds) to run the solver
TIME_INCREMENT = 13.0 # Time (in seconds) in between heuristic measurements
DEBUG_SWITCH = False # Displays intermediate heuristic info when True
MAX_LNS_NEIGHBOURHOODS = 1000 # Maximum number of neighbours to explore in LNS
```
有两个设置应该进一步解释下。TIME_INCREMENT设置作动态策略选择，MAX_LNS_NEIGHBOURHOODS设置邻域选择策略。两者在下面更详细地描述。

这些设置可以作为命令行参数暴露给用户，但在此阶段，我们将输入数据作为参数提供给程序。输入问题 - 来自Taillard基准集的问题被假定为用于流程车间调度的标准格式。以下代码用作求解器文件的__main__方法，并根据输入到程序的参数数调用相应的函数：
```
if __name__ == '__main__':

    if len(sys.argv) == 2:
        data = parse_problem(sys.argv[1], 0)
    elif len(sys.argv) == 3:
        data = parse_problem(sys.argv[1], int(sys.argv[2]))
    else:
        print "\nUsage: python flow.py <Taillard problem file> [<instance number>]\n"
        sys.exit(0)

    (perm, ms) = solve(data)
    print_solution(data, perm)
```
我们将尽快描述Taillard问题文件的解析。（这些文件可以在线获得）

解决方案期望数据变量是包含每个作业的活动持续时间的整数列表。从初始化一组全局策略开始。关键是我们使用strat_ *变量来维护每个策略的统计信息。这有助于在解决过程中动态选择策略。
Read All
Google Code Jam Round 1C 2016 B. Slides!

2017-03-06

Google

Google
- Problem
- Input and Output
- Limits
- Sample
- Codes
Problem

Gooli is a huge company that owns B buildings in a hilly area. The buildings are numbered from 1 to B.

The CEO wants to build a set of slides between buildings that she can use to travel from her office in building 1 to her favorite cafe in building B. Slides, of course, are one-way only, but the buildings are tall and have elevators, so a slide can start in any building and end in any other building, and can go in either direction. Specifically, for any two buildings x and y, you can build either zero or one slides from x to y, and you can build either zero or one slides from y to x. The exception is that no slides are allowed to originate in building B, since once the CEO reaches that building, there is no need for her to do any more sliding.

In honor of Gooli becoming exactly M milliseconds old, the design must ensure that the CEO has exactly M different ways to travel from building 1 to building B using the new slides. A way is a sequence of buildings that starts with building 1, ends with building B, and has the property that for each pair of consecutive buildings x and y in the sequence, a slide exists from x to y. Note that the CEO is not requiring that any building be reachable from any other building via slides.

Can you come up with any set of one or more slides that satisfies the CEO’s requirements, or determine that it is impossible?

Input and Output

Input

The first line of the input gives the number of test cases, T. T lines follow; each consists of one line with two integers B and M, as described above.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the word POSSIBLE or IMPOSSIBLE, depending on whether the CEO’s requirements can be fulfilled or not. If it is possible, output an additional B lines containing B characters each, representing a matrix describing a valid way to build slides according to the requirements. The j-th character of the i-th of these lines (with both i and j counting starting from 1) should be 1 if a slide should be built going from building i to building j, and 0 otherwise. The i-th character of the i-th line should always be 0, and every character of the last line should be 0.

If multiple solutions are possible, you may output any of them.

Limits

1 ≤ T ≤ 100.

Small dataset

2 ≤ B ≤ 6.

1 ≤ M ≤ 20.

Large dataset

2 ≤ B ≤ 50.

1 ≤ M ≤ 1018.

Sample
```
Input 
 	
    3
    5 4
    2 1
    4 20

Output 

    Case #1: POSSIBLE
    01001
    00110
    00001
    00101
    00000
    Case #2: POSSIBLE
    01
    00
    Case #3: IMPOSSIBLE
```
The sample outputs show one possible way to fulfill the specifications for each case. Other valid answers may exist.

Here is an illustration of the sample answer for Case #1:

The four ways to get from building 1 to building 5 are:
```
1 to 5

1 to 2 to 3 to 5

1 to 2 to 4 to 5

1 to 2 to 4 to 3 to 5
```
In Case #3, building slides from 1 to 2, 2 to 3, 3 to 1, and 1 to 4 would create infinitely many ways for the CEO to reach building 4 (she could go directly to 4, or go around the loop once and then go to 4, or go around the loop twice…), but the CEO requested exactly 20 ways.

Codes
```
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    freopen("C:\\Users\\Administrator\\Downloads\\B-small-practice.in","r",stdin);
    freopen("C:\\Users\\Administrator\\Downloads\\B-small-attempt0.out","w",stdout);
    int num, B;
    long long M;
    cin >> num;
    for (int i = 0; i < num; i++) {
        cout << "Case #" << i + 1 << ": ";
        cin >> B >> M;
        if (M > (1LL << (B - 2)))   cout << "IMPOSSIBLE" << endl;
        else {
            cout << "POSSIBLE" << endl;
            for (int i = 0; i< B; i++) {
                for (int j = 0; j < B; j++) {
                    if (i < j && j < B - 1)     cout << "1";
                    else if (j == B - 1 && (i == 0 || (M - 1) & 1LL<<(i - 1)))   cout << "1";
                    else    cout << "0";
                }
                cout << endl;
            }
        }
    }
    return 0;
}
```
Read All
Google Code Jam Round 1C 2016 A. Senate Evacuation

2017-03-06

Google

Google
- Problem
- Input and Output
- Limits
- Sample
- Codes
Problem

A small fire started in the senate room, and it needs to be evacuated!

There are some senators in the senate room, each of whom belongs to of one of N political parties. Those parties are named after the first N (uppercase) letters of the English alphabet.

The emergency door is wide enough for up to two senators, so in each step of the evacuation, you may choose to remove either one or two senators from the room.

The senate rules indicate the senators in the room may vote on any bill at any time, even in the middle of an evacuation! So, the senators must be evacuated in a way that ensures that no party ever has an absolute majority. That is, it can never be the case after any evacuation step that more than half of the senators in the senate room belong to the same party.

Can you construct an evacuation plan? The senate is counting on you!

Input and Output

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines. The first line contains a single integer N, the number of parties. The second line contains N integers, P1, P2, …, PN, where Pi represents the number of senators of the party named after the i-th letter of the alphabet.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the evacuation plan. The plan must be a space-separated list of instructions, in the order in which they are to be carried out, where each instruction is either one or two characters, representing the parties of the senators to evacuate in each step.

It is guaranteed that at least one valid evacuation plan will exist. If multiple evacuation plans are valid, you may output any of them.

Limits

1 ≤ T ≤ 50.

No party will have an absolute majority before the start of the evacuation. 1 ≤ Pi ≤ 1000, for all i.

Small dataset

2 ≤ N ≤ 3.

sum of all Pi ≤ 9.

Large dataset

2 ≤ N ≤ 26.

sum of all Pi ≤ 1000.

Sample
```
Input 
 	
    4
    2
    2 2
    3
    3 2 2
    3
    1 1 2
    3
    2 3 1

Output

    Case #1: AB BA
    Case #2: AA BC C BA
    Case #3: C C AB
    Case #4: BA BB CA
```
The sample output displays one set of answers to the sample cases. Other answers may be possible.

In Case #1, there are two senators from each of the parties A and B. If we remove one from each party every time, the perfect balance is maintained until evacuation is complete.

Case #2 proceeds as follows:

Initially in the room: 3 A, 2 B, 2 C.

Evacuate AA. Still in the room: 1 A, 2 B, 2 C.

Evacuate BC. Still in the room: 1 A, 1 B, 1 C.

Evacuate C. Still in the room: 1 A, 1 B.

Evacuate AB. Evacuation complete!

Note that it would not be valid to begin the evacuation with BC, which would leave 3 A, 1 B, and 1 C in the room; party A would have an absolute majority (3 out of 5 = 60%).

For Case #3, note that CC AB would also be a valid answer, and C C AB is also valid even though it requires three evacuation steps instead of two.

Codes

``cpp #include #include using namespace std;

int main() { freopen(“C:\Users\Administrator\Downloads\A-large-practice.in”,”r”,stdin); freopen(“C:\Users\Administrator\Downloads\A-large-attempt0.out”,”w”,stdout); int num, N; cin » num; for (int i = 0; i < num; i++) { cout « “Case #” « i + 1 « ”: “; cin » N; int a[26]; for (int i = 0; i < N; i++) cin » a[i]; while (1) { vector all; int maxh = *max_element(a, a+N); if (maxh == 0) break; for (int i = 0; i < N; i++) if (a[i] == maxh) all.push_back(i); if (all.size() == 2) { printf("%c%c ", 'A' + all[0], 'A' + all[1]); a[all[0]]--; a[all[1]]--; } else { printf("%c ", 'A' + all[0]); a[all[0]]--; } } cout << endl; } return 0; } ```
Read All
Google Code Jam Round 1B 2016 A. Getting the Digits

2017-03-05

Google

Google
Problem

You just made a new friend at an international puzzle conference, and you asked for a way to keep in touch. You found the following note slipped under your hotel room door the next day:

“Salutations, new friend! I have replaced every digit of my phone number with its spelled-out uppercase English representation (“ZERO”, “ONE”, “TWO”, “THREE”, “FOUR”, “FIVE”, “SIX”, “SEVEN”, “EIGHT”, “NINE” for the digits 0 through 9, in that order), and then reordered all of those letters in some way to produce a string S. It’s up to you to use S to figure out how many digits are in my phone number and what those digits are, but I will tell you that my phone number consists of those digits in nondecreasing order. Give me a call… if you can!”

You would to like to call your friend to tell him that this is an obnoxious way to give someone a phone number, but you need the phone number to do that! What is it?

Input and Output

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S of uppercase English letters.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string of digits: the phone number.

Limits

1 ≤ T ≤ 100.

A unique answer is guaranteed to exist.

Small dataset

3 ≤ length of S ≤ 20.

Large dataset

3 ≤ length of S ≤ 2000.

Sample
```
Input 

    4
    OZONETOWER
    WEIGHFOXTOURIST
    OURNEONFOE
    ETHER

Output 

    Case #1: 012
    Case #2: 2468
    Case #3: 114
    Case #4: 3
`

## Codes

```cpp
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    freopen("C:\\Users\\Administrator\\Downloads\\A-small-practice.in","r",stdin);
    freopen("C:\\Users\\Administrator\\Downloads\\A-small-attempt0.out","w",stdout);
    string a[] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
    string ordered[] = {"0", "2", "4", "6", "8", "3", "5", "1", "7", "9"};
    string t = "ZWUXGHFOVI";
    int num;
    cin >> num;
    string str;
    for (int i = 0; i < num; i++) {
        string res = "";
        cout << "Case #" << i + 1 << ": ";
        cin >> str;
        int map[26] = {0};
        for (int i = 0; i<str.size(); i++)
            map[(int)(str[i]-'A')]++;
        for (int i = 0; i < 10; i++) {
            while (map[(int)(t[i]-'A')]) {
                res += ordered[i];
                int temp = stoi(ordered[i]);
                for (int j = 0; j < a[temp].size(); j++)
                    map[(int)a[temp][j]-'A']--;
            }
        }
        sort(res.begin(), res.end());
        cout << res << endl;
    }
    return 0;
}
```
Read All
Google Code Jam Round 1A 2016 C. BFFs

2017-03-05

Google

Google
- Problem
- Input and Output
- Limits
- Sample
- Codes
Problem

You are a teacher at the brand new Little Coders kindergarten. You have N kids in your class, and each one has a different student ID number from 1 through N. Every kid in your class has a single best friend forever (BFF), and you know who that BFF is for each kid. BFFs are not necessarily reciprocal – that is, B being A’s BFF does not imply that A is B’s BFF.

Your lesson plan for tomorrow includes an activity in which the participants must sit in a circle. You want to make the activity as successful as possible by building the largest possible circle of kids such that each kid in the circle is sitting directly next to their BFF, either to the left or to the right. Any kids not in the circle will watch the activity without participating.

What is the greatest number of kids that can be in the circle?

Input and Output

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines. The first line of a test case contains a single integer N, the total number of kids in the class. The second line of a test case contains N integers F1, F2, …, FN, where Fi is the student ID number of the BFF of the kid with student ID i.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum number of kids in the group that can be arranged in a circle such that each kid in the circle is sitting next to his or her BFF.

Limits

1 ≤ T ≤ 100.

1 ≤ Fi ≤ N, for all i.

Fi ≠ i, for all i. (No kid is their own BFF.)

Small dataset

3 ≤ N ≤ 10.

Large dataset

3 ≤ N ≤ 1000.

Sample
```
Input 
 	
	4
	4
	2 3 4 1
	4
	3 3 4 1
	4
	3 3 4 3
	10
	7 8 10 10 9 2 9 6 3 3

Output 

	Case #1: 4
	Case #2: 3
	Case #3: 3
	Case #4: 6
```
In sample case #4, the largest possible circle seats the following kids in the following order: 7 9 3 10 4 1. (Any reflection or rotation of this circle would also work.) Note that the kid with student ID 1 is next to the kid with student ID 7, as required, because the list represents a circle.

Codes
```
#include <iostream>
#define MAXN 1005
using namespace std;
int a[MAXN];

int main() {
    freopen("C:\\Users\\Administrator\\Downloads\\C-small-practice.in","r",stdin);
    freopen("C:\\Users\\Administrator\\Downloads\\C-small-attempt0.out","w",stdout);
    int num, N;
    cin >> num;
    string s1, s2;
    for (int i = 0; i < num; i++) {
        cout << "Case #" << i + 1 << ": ";
        cin >> N;
        for (int i = 1; i<= N; i++)     cin >> a[i];
        int cnt[MAXN] = {0}, d[MAXN] = {0};
        int ans = 0, res = 0;
        for (int i = 1; i<= N; i++) {
            bool map[N] = {false};
            int x = i;
            map[x] = true;
            while (1) {
                x = a[x];
                if (map[x])  break;
                map[x] = true;
                ++cnt[i];
            }
            if (x==i)   ans = max(ans, cnt[i]+1);
        }
        for (int j = 1; j <= N; j++)
            for (int i = 1; i <= N; i++)
                if (a[a[i]] != i)
                    d[a[i]] = max(d[a[i]], d[i] + 1);

        for (int i = 1; i <= N; i++)
            if (a[a[i]] == i)
                res += d[i] + d[a[i]] + 2;
        res >>= 1;
        cout << max(ans, res) << endl;
    }
    return 0;
}
```
Read All

7/38

Welcome to Shanshan Blog!

Leetcode (78, 90) Subsets I, II

Leetcode 78. Subsets

Leetcode 90. Subsets II

500 Lines or Less Chapter 9: A Flow Shop Scheduler 翻译

流程调度程序

背景

一般解决方案

Google Code Jam Round 1C 2016 B. Slides!

Problem

Input and Output

Limits

Sample

Codes

Google Code Jam Round 1C 2016 A. Senate Evacuation

Problem

Input and Output

Limits

Sample

Codes

Google Code Jam Round 1B 2016 A. Getting the Digits

Problem

Input and Output

Limits

Sample

Google Code Jam Round 1A 2016 C. BFFs

Problem

Input and Output

Limits

Sample

Codes