# Homework6 (HW6)
###### tags: `2020pdsa`

Due: 12/31 21:00
Judge Open: 12/?

[toc]

## Version
Python: 3.8.5 (Note: no numpy)
Java: openjdk14 (https://openjdk.java.net/projects/jdk/14/)
Platform: Debian

## Our Judge
https://c4lab.bime.ntu.edu.tw:13000

Grading Status:
* AC: ACcepted
* TLE: Time Limit Excess
* WA: Wrong Answer
* RE: Runtime Error (Mostly your program raise some error unexpectly)

Memory: 2G

Handin the file with utf-8 encoding if there are 中文 words inside your code (including comments).

### Template Download
https://cool.ntu.edu.tw/courses/3501/files/folder/Homework_Template

# HW6-1 Teams
You are the manager that runs an idol group similar to AKB48. One day, you want to hold a sport competition.

The competition separates idols into two groups, the red team and the white team. The only constraint is that there is no tee-tee (てぇてぇ) pair in the same team.

Tee-tee means two idols have better relationship and always cooperate with each other.

To make this question easier, each idol has her ID and
I will give you a list of tee-tees pair and ask you if you can separate the idols into two groups or not.

## Hint
* Bipartite Graph
* BFS and DFS both works, but dfs has recursion overhead(Especially for Python user).
* create your graph with Adjacency List
* For java users, Linked-list is the best suitable structure for graph
* To avoid stackoverflow in Java, we can specific your stack memory when execution https://docs.oracle.com/cd/E13150_01/jrockit_jvm/jrockit/jrdocs/refman/optionX.html e.g. `java -Xss10M -cp algs4.jar:. Teams`

## Template

from typing import List

class Teams:
    def teams(self, idols: int, teetee: List[List[int]]) -> bool:
        return False


if __name__ == "__main__":
    # example 1: True
    print(Teams().teams(4, [[0,1],[0,3],[2,1],[3,2]]))
    # example 1: False
    print(Teams().teams(4, [[0,1],[0,3],[0,2],[2,1],[3,2]]))

java template

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.lang.Math;

class Teams {
    public Teams() {}; 

    public boolean teams(int idols, List<int[]> teetee) {
        return true;
    }   

    public static void main(String[] args) {
        Teams team = new Teams();
        // example1: True
        System.out.println(team.teams(4, new ArrayList<int[]>(){{
            add(new int[]{0,1});
            add(new int[]{0,3});
            add(new int[]{2,1});
            add(new int[]{3,2});
        }}));
        // example2: False
        System.out.println(team.teams(4, new ArrayList<int[]>(){{
            add(new int[]{0,1});
            add(new int[]{0,3});
            add(new int[]{2,1});
            add(new int[]{3,2});
            add(new int[]{0,2});
        }}));
    }   
}

example1:
Red teams: 0, 2
White teams: 1, 3

example2:
Red teams: 0, 2 -> violate the rule, (0,2) are teetee pair.
White teams: 1, 3
Actually no combination can be found, so return False.

## TestCase
* `N` is number of idols
* Idol's ID is bounded by `0 <= id < N`
* `M` is the number of teetee pair
* We guarantee teetee pair are not duplicated, and cannot teetee herself.

Cases
* case1: 20 points: N <= 4, M <= N\*N
* case2: 20 points: N <= 10000, M <= 15000(Special case)
* case3: 20 points: N <= 1000, M <= 1000
* case4: 20 points: N <= 10000, M <= 10000
* case5: 20 points: N <= 100000, M <= 400000

## Time Limit
(We can extend it if needed)
Python: 4s
Java: 1s

## Modified from

# HW6-2 Railway
Watson Industry(W.I.) has built lots of landmark buildings, such as tennis-racket home, welcome statue, PPP farm and Atlantis.

One day, the president, Watson, wants to give a tour for very important person came from Australia. The guest would like to visit all the landmarks on the minecart rather than walking. What is the minimum railway does Watson must to build?(Minecart can run on the railway in both direction)

To simplify the question, we have N landmarks with ID from `0` to `N-1`, and M distances with the form `[a, b, distance]` which indicates the distance from a to b in both direction.

You should return the minimum total distance of railway that connected all the landmarks.

## Hint
* Minimum spanning tree
* 1. Kruskal's Algorithm
* 2. Prim's Algorithm
* Disjoint Set, priority-queue

Change the recursion limit in Python.

import sys 
sys.setrecursionlimit(100001)

## Template

from typing import List


class Railway():
    def __init__(self):
        pass
    
    def railway(self, landmarks:int, distance: List[List[int]]) -> int:
        return 0


if __name__ == "__main__":
    print(
    Railway().railway(4,[[0,1,2],
                         [0,2,4], 
                         [1,3,5], 
                         [2,1,1]])
    )
    # Answer: 8 (2 + 5 + 1)

    print(
    Railway().railway(4,[[0,1,0],
                         [0,2,4], 
                         [0,3,4], 
                         [1,2,1], 
                         [1,3,4], 
                         [2,3,2]])
    )
    # Answer: 3(0 + 1 + 2)

java template

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.lang.Math;


class Railway {
    public Railway() {};

    public int railway(int landmarks, List<int[]> distance) {
        return 10000;
    }

    public static void main(String[] args) {
        Railway team = new Railway();
        System.out.println(team.railway(4, new ArrayList<int[]>(){{
            add(new int[]{0,1,2});
            add(new int[]{0,2,4});
            add(new int[]{1,3,5});
            add(new int[]{2,1,1});
        }}));
        System.out.println(team.railway(4, new ArrayList<int[]>(){{
            add(new int[]{0,1,0});
            add(new int[]{0,2,4});
            add(new int[]{0,3,4});
            add(new int[]{1,2,1});
            add(new int[]{1,3,4});
            add(new int[]{2,3,2});
        }}));
    }
}

example1:
Minimum path: (0,1,2) (1,2,1) (1,3,5) -> 2 + 1 + 5 = 8

example2:
Minimum path: (0,1,0) (1,2,1) (2,3,2) -> 0 + 1 + 2 = 3

## TestCase
* `N` is number of landmarks
* Landmark's ID is bounded by `0 <= id < N`
* `M` is the number of path
* 0 <= distance <= 10000
* We **do not** guarantee there is only path from a to b.
* There may be a path from a to a (self-loop).
* We guarantee you can go to all the landmarks if you connect all the paths.

Cases
* case1: 20 points: N <= 4, M <= 10
* case2: 20 points: N <= 10001, M <= 20000(Special case)
* case3: 20 points: N <= 10, M <= 100
* case4: 20 points: N <= 1000, M <= 100000
* case5: 20 points: N <= 10000, M <= 1000000

## Time Limit
(We can extend it if needed)
Python: 4s
Java: 0.8s