Survival Train

package SurvivalTrain;

// Doãn Thanh Tùng
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

class UserSolution {
	// mảng lưu các phần tử đối tượng Passengers
	Passenger[] passengers;
	// mảng các TreeSet
	TreeSet<Passenger> sections[];
	// mảng các List, mỗi jobs[i] là một List ID các hành khách 
	List<Integer> jobs[];

	// nghiên cứu kỹ phần khởi tạo này
	void init(int N, int M, int J, int mPoint[], int mJobID[]) {
		sections = new TreeSet[N / M];
		jobs = new ArrayList[J]; // lưu id của các hành khách cùng job
		for (int i = 0; i < J; i++)
			jobs[i] = new ArrayList<>();
		passengers = new Passenger[N];
		for (int i = 0; i < N; i++) {
			if (sections[i / M] == null)
				// sắp xếp giảm dần theo điểm, tăng dần theo id
				sections[i / M] = new TreeSet<>(
						(a, b) -> a.point == b.point ? a.id - b.id : b.point
								- a.point);
			passengers[i] = new Passenger(i, mPoint[i], mJobID[i]);
			sections[i / M].add(passengers[i]);
			jobs[mJobID[i]].add(i);
		}
	}

	void destroy() {
	}

	// cập nhật điểm của passenger có mID
	// kéo theo cập nhật sections[] --> cần tìm sections mà mID thuộc về
	int update(int mID, int mPoint) {
		Passenger p = passengers[mID];
		for (int i = 0; i < sections.length; i++) {
			if (sections[i].remove(p)) {
				p.point += mPoint;
				sections[i].add(p);
				break;
			}
		}
		return p.point;
	}

	int updateByJob(int mJobID, int mPoint) {
		int sum = 0;
		for (int i = 0; i < sections.length; i++) {
			for (int pID : jobs[mJobID]) {
				if (sections[i].remove(passengers[pID])) {
					passengers[pID].point += mPoint;
					sum += passengers[pID].point;
					sections[i].add(passengers[pID]);
				}
			}
		}
		return sum;
	}

	// section có kiểu dữ liệu treeSet đã đã được định nghĩa với comparator sắp xếp --> nên khi add dữ liệu sẽ tự động sắp xếp
	// --> cần một List lưu các đối tượng cần dịch chuyển
	// chưa đủ, List này còn cần chia mảng như section để biết những hành khách sẽ dịch chuyển vào section nào
	// mNum là số lượng min, max cần đảo chỗ ở mỗi section
	int move(int mNum) {
		int sum = 0;
		List<Passenger> moved[] = new ArrayList[sections.length - 1];
		for (int i = 0; i <= sections.length - 2; i++) {
			moved[i] = new ArrayList<>();
			// find and remove min from section 0 to length-2
			// store in moved[], chưa thêm lại vào sections[] tương ứng luôn
			for (int j = 0; j < mNum; j++) {
				Passenger minScore = sections[i].pollLast(); // xóa nhỏ nhất
				moved[i].add(minScore);
				sum += minScore.point;
			}
			// find and remove max from section 1 to length-1
			// readd max to sections before
			for (int j = 0; j < mNum; j++) {
				Passenger maxScore = sections[i + 1].pollFirst();
				sections[i].add(maxScore);
				sum += maxScore.point;
			}
		}
		// readd min to sections after
		// moved.length = sections.length - 1
		for (int i = 0; i < moved.length; i++)
			sections[i + 1].addAll(moved[i]);
		return sum;
	}

	class Passenger {
		int id, point, jobID;

		Passenger(int mID, int mPoint, int mJobID) {
			id = mID;
			point = mPoint;
			jobID = mJobID;
		}
	}
}


package SurvivalTrain;

//cải tiến UserSolution1 bằng cách truy xuất section nhanh hơn thay vì dùng vòng for trong 2 phương thức update và updateByJob
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

class UserSolution2 {
	// mảng lưu các phần tử đối tượng Passengers
	Passenger[] passengers;
	// mảng các TreeSet
	TreeSet<Passenger> sections[];
	// mảng các List, mỗi jobs[i] là một List ID các hành khách 
	List<Integer> jobs[];
	int numS;

	// nghiên cứu kỹ phần khởi tạo này
	void init(int N, int M, int J, int mPoint[], int mJobID[]) {
		numS = N / M;
		sections = new TreeSet[numS];
		jobs = new ArrayList[J]; // lưu id của các hành khách cùng job
		for (int i = 0; i < J; i++)
			jobs[i] = new ArrayList<>();
		passengers = new Passenger[N];
		for (int i = 0; i < N; i++) {
			if (sections[i / M] == null)
				// sắp xếp giảm dần theo điểm, tăng dần theo id
				sections[i / M] = new TreeSet<>(
						(a, b) -> a.point == b.point ? a.id - b.id : b.point
								- a.point);
			passengers[i] = new Passenger(i, mPoint[i], mJobID[i], i / M);
			sections[i / M].add(passengers[i]);
			jobs[mJobID[i]].add(i);
		}
	}

	void destroy() {
	}

	// cập nhật điểm của passenger có mID
	// kéo theo cập nhật sections[] --> cần tìm sections mà mID thuộc về
	int update(int mID, int mPoint) {
		Passenger p = passengers[mID];
		sections[p.sectionID].remove(p);
		p.point += mPoint;
		sections[p.sectionID].add(p);
		return p.point;
	}

	int updateByJob(int mJobID, int mPoint) {
		int sum = 0;
		for (int pID : jobs[mJobID]) {
			Passenger p = passengers[pID];
			sections[p.sectionID].remove(p);
			p.point += mPoint;
			sum += p.point;
			sections[p.sectionID].add(p);
		}
		return sum;
	}

	// section có kiểu dữ liệu treeSet đã đã được định nghĩa với comparator sắp xếp --> nên khi add dữ liệu sẽ tự động sắp xếp
	// --> cần một List lưu các đối tượng cần dịch chuyển
	// chưa đủ, List này còn cần chia mảng như section để biết những hành khách sẽ dịch chuyển vào section nào
	// mNum là số lượng min, max cần đảo chỗ ở mỗi section
	int move(int mNum) {
		int sum = 0;
		List<Passenger> moved[] = new ArrayList[numS - 1];
		for (int i = 0; i <= numS - 2; i++) {
			moved[i] = new ArrayList<>();
			// find and remove min from section 0 to length-2
			// store in moved[], chưa thêm lại vào sections[] tương ứng luôn
			for (int j = 0; j < mNum; j++) {
				Passenger minP = sections[i].pollLast(); // xóa nhỏ nhất
				minP.sectionID++;
				moved[i].add(minP);
				sum += minP.point;
			}
			// find and remove max from section 1 to length-1
			// readd max to sections before
			for (int j = 0; j < mNum; j++) {
				Passenger maxP = sections[i + 1].pollFirst();
				maxP.sectionID--;
				sections[i].add(maxP);
				sum += maxP.point;
			}
		}
		// readd min to sections after
		// moved.length = sections.length - 1
		for (int i = 0; i < moved.length; i++)
			sections[i + 1].addAll(moved[i]);
		return sum;
	}

	class Passenger {
		int id, point, jobID, sectionID;

		Passenger(int mID, int mPoint, int mJobID, int mSectionID) {
			id = mID;
			point = mPoint;
			jobID = mJobID;
			sectionID = mSectionID;
		}
	}
}