Untitled

Contact Info DB:
package ContactInfoDB;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class UserSolution {
	// String là value / giá trị dữ liệu chứ không phải tên trường
	// 5 fields -> 5 hashMap
	Map<String, Set<Record>> hashMap[] = new HashMap[5];

	void InitDB() {
		for (int i = 0; i < 5; i++)
			hashMap[i] = new HashMap<>();
	}

	// hashMap[0] đại diện cho NAME Field, nhận vào keyword là một dữ liệu của
	// NAME field và match tới
	// một bản record được lưu trong HashSet
	void Add(String... fields) {
		Record record = new Record(fields);
		for (int i = 0; i < fields.length; i++)
			hashMap[i].computeIfAbsent(fields[i], k -> new HashSet<>()).add(
					record);
	}

	// khi hashMap get, tham số là String và trả về kiểu Set<Record>
	// field được biểu thị là int, nên được dùng làm index cho hashMap[] để xác
	// định kiểu Field
	// lưu ý Set<Record> được lưu dưới dạng HashSet<>()
	// lưu ý phương thức getOrDefault
	// khi không có giá trị ánh xạ nào được trả về, một bản HashSet mới mặc định
	// sẽ được tạo ra
	// size khi đó = 0, rỗng
	int Delete(int field, String str) {
		Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>());
		int size = records.size();
		// xóa record khỏi hashMap
		// không được phép vừa tìm, duyệt vừa xóa trên records
		// nên phải tạo một bản copy new HashSet<>(records) để duyệt trên đó
		for (Record record : new HashSet<>(records))
			for (int i = 0; i < 5; i++)
				hashMap[i].get(record.field[i]).remove(record);
		return size;
	}

	int Change(int field, String str, int changefield, String changestr) {
		Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>());
		int size = records.size();
		for (Record record : new HashSet<>(records)) {
			hashMap[changefield].get(record.field[changefield]).remove(record);
			record.field[changefield] = changestr;
			hashMap[changefield].computeIfAbsent(changestr,
					k -> new HashSet<>()).add(record);
		}
		return size;
	}

	// returnfield là index cần request khi đã tìm được bản record ->
	// record.field[returnfield]
	Solution.Result Search(int field, String str, int returnfield) {
		Solution.Result result = new Solution.Result();
		Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>());
		result.count = records.size();
		if (records.size() == 1) {
			// tùy với loại Collection mà có cách lấy phần tử khác nhau, đây là
			// cách tổng quát
			Record record = (Record) records.toArray()[0];
			result.str = record.field[returnfield];
		}
		return result;
	}
}

class Record {
	String field[];

	// nhận vào value
	Record(String... strings) {
		field = Arrays.copyOf(strings, strings.length);
	}
}


package ElectronicBulletinBoard;

// VŨ HÀ THÀNH
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;

public class UserSolution2 {

	private HashMap<String, User> userMap;
	private HashMap<Integer, Post> postMap;
	private TreeSet<Post> postTree;
	private TreeSet<User> userTree;

	public void init() {
		userMap = new HashMap<>();
		postMap = new HashMap<>();
		postTree = new TreeSet<>();
		userTree = new TreeSet<>();
	}

	public int writeMessage(char[] mUser, int mID, int mPoint) {
		String name = new String(mUser).trim();
		User user = userMap.computeIfAbsent(name, User::new);
		Post post = new Post(mID, mPoint, user, null);
		postMap.put(mID, post);
		postTree.add(post);
		update(user, mPoint);
		return user.point;
	}

	private void update(User user, int point) {
		userTree.remove(user);
		user.point += point;
		userTree.add(user);
	}

	private void update(Post post, int point) {
		postTree.remove(post);
		post.total += point;
		postTree.add(post);
	}

	public int commentTo(char[] mUser, int mID, int mTarget, int mPoint) {
		User user = userMap
				.computeIfAbsent(new String(mUser).trim(), User::new);
		Post target = postMap.get(mTarget);
		Post post = new Post(mID, mPoint, user, target);
		update(user, mPoint);
		postMap.put(mID, post);
		while (post.target != null)
			post = post.target;
		update(post, mPoint);
		return post.total;
	}

	public int erase(int mID) {
		Post post = postMap.get(mID);
		int count = remove(post);
		if (post.target == null) {
			postTree.remove(post);
			return post.user.point;
		}
		Post parent = post;
		while (parent.target != null) {
			parent = parent.target;
			parent.attached.remove(post);
		}
		update(parent, -count);
		return parent.total;
	}

	public int remove(Post post) {
		int count = post.point;
		for (Post child : post.attached)
			count += remove(child);
		postMap.remove(post.id);
		update(post.user, -post.point);
		return count;
	}

	public void getBestMessages(int[] mBestMessageList) {
		int count = 0;
		for (Post post : postTree) {
			mBestMessageList[count] = post.id;
			if (++count == 5) {
				break;
			}
		}
	}

	public void getBestUsers(char[][] mBestUserList) {
		int count = 0;
		for (User user : userTree) {
			for (int i = 0; i < user.name.length(); i++) {
				mBestUserList[count][i] = user.name.charAt(i);
			}
			mBestUserList[count][user.name.length()] = '\0';
			if (++count == 5) {
				break;
			}
		}
	}

	private static class User implements Comparable<User> {

		public int point;
		public String name;

		public User(String name) {
			this.name = name;
		}

		@Override
		public int compareTo(User o) {
			return point != o.point ? o.point - point : name.compareTo(o.name);
		}
	}

	private static class Post implements Comparable<Post> {

		public int id;
		public int point;
		public int total;
		public User user;
		public Post target;
		public HashSet<Post> attached = new HashSet<>();

		public Post(int id, int point, User user, Post target) {
			this.id = id;
			this.point = point;
			this.total = point;
			this.user = user;
			if (target != null) {
				this.target = target;
				target.attached.add(this);
			}
		}

		@Override
		public int compareTo(Post o) {
			return total != o.total ? o.total - total : id - o.id;
		}

	}

}


package ElectronicBulletinBoard;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

class UserSolution {
	// map key name -> object User
	Map<String, User> users = new HashMap<>();
	Map<Integer, Message> messages = new HashMap<>();
	TreeSet<User> topUsers = new TreeSet<>(
			(a, b) -> a.point == b.point ? a.name.compareTo(b.name) : b.point
					- a.point);
	TreeSet<Message> topPosts = new TreeSet<>(
			(a, b) -> a.total == b.total ? a.id - b.id : b.total - a.total);

	// sai, khi khai bao kiểu này, chỉ đúng trong init()
	// TreeSet<User> topUsers = new TreeSet<>(DesSort);

	public void init() {
		users.clear();
		messages.clear();
		topUsers.clear();
		topPosts.clear();
	}

	// được dùng để viết cả post, comment và reply
	public int writeMessage(char[] mUser, int mID, int mPoint) {
		String name = new String(mUser).trim();
		User user = users.computeIfAbsent(name, k -> new User());
		user.name = name;

		// update điểm
		// tuy nhiên khi đối tượng được update dữ liệu thuộc tính
		// treeSet cũng không thay đổi --> với treeSet cần remove và add lại
		// user.point += mPoint;
		topUsers.remove(user);
		user.point += mPoint;
		topUsers.add(user);

		// muốn tạo đối tượng Post, trước đó cần tạo đối tượng User
		Message newPost = new Message(user, mID, mPoint);
		messages.put(mID, newPost);
		topPosts.add(newPost);
		return user.point;
	}

	// người có tên mUser, thêm comment hoặc reply mID, có điểm số mPoint vào
	// post hoặc comment mTarget
	// return tổng điểm của post mà comment hoặc reply được thêm
	public int commentTo(char[] mUser, int mID, int mTarget, int mPoint) {
		writeMessage(mUser, mID, mPoint);
		Message target = messages.get(mTarget);
		Message written = messages.get(mID);
		// nếu target là Post thì target.above == null, khi đó written.above =
		// target (Post)
		// nếu target là Comment thì target.above != null và == Post
		// tóm lại là mục đích ở đây là cắm hết comments và replies vào post
		// vậy làm sao để phân biệt được đâu là comments, đâu là replies để phục
		// vụ cho chức năng Delete
		// sử dụng arrayList bên trong đối tượng
		written.above = target.above != null ? target.above : target;

		// khi sử dụng class Message chung chung cho cả 3 kiểu post, comment,
		// reply
		// nó sẽ add hết vào treeSet topPosts trong khi yêu cầu là thằng này chỉ
		// được chứa Post --> cần khắc phục
		topPosts.remove(written);
		target.children.add(written); // thêm vào danh sách con arraylist của
										// target để quản lý

		// cập nhật điểm cho Post sau khi có thêm comment hoặc reply
		topPosts.remove(written.above); // xóa Post
		written.above.total += mPoint;
		topPosts.add(written.above);

		return written.above.total;
	}

	public int erase(int mID) {
		Message object = messages.get(mID);
		if (object.above != null) { // object là comment hoặc reply
			// cập nhật điểm cho post
			topPosts.remove(object.above);
			remove(object);
			topPosts.add(object.above);
			return object.above.total; // trả về tổng điểm của post
		} else { // object là post
			topPosts.remove(object);
			remove(object);
			return object.user.point; // trả về tổng điểm của user viết post
		}
	}

	void remove(Message object) {
		for (Message m : object.children) {
			if (m.isAlive) {
				remove(m); // gọi đệ quy
			}
		}
		// BASE CASE
		object.isAlive = false;
		// cập nhật điểm cho User
		topUsers.remove(object.user);
		object.user.point -= object.point;
		topUsers.add(object.user);

		// cập nhật điểm cho Post nếu object là comment hoặc reply
		if (object.above != null) {
			object.above.total -= object.point;
		}

		// C2 không cần sử dụng hàm đệ quy vì bài toán chỉ cho 3 tầng
	}

	// lưu kết quả ID của top post vào mBestMessageList[]
	void getBestMessages(int[] mBestMessageList) {
		int i = 0;
		for (Message post : topPosts) {
			mBestMessageList[i] = post.id;
			if (++i == 5) {
				break;
			}
		}
	}

	// mảng char mBestUserList[5][?] lưu tên của top 5 người nhiều điểm nhất
	void getBestUsers(char[][] mBestUserList) {
		int i = 0;
		for (User user : topUsers) {
			int j;
			for (j = 0; j < user.name.length(); j++) {
				mBestUserList[i][j] = user.name.charAt(j);
			}
			mBestUserList[i][j] = '\0'; // yêu cầu đề bài là save ký tự 0 vào
										// cuối
			if (++i == 5) {
				break;
			}
		}
	}

	class User {
		String name;
		int point;
	}

	// Message là đối tượng được dùng để chỉ chung: Post và Comment
	// thuộc tính comments trong nó dùng để chỉ chung comments (thuộc 1 Post)
	// hoặc replies (thuộc 1 comment)
	class Message {
		User user;
		int id, point, total;
		boolean isAlive = true;
		Message above; // ?
		List<Message> children = new ArrayList<>(); // ?

		Message(User mUser, int mID, int mPoint) {
			user = mUser;
			id = mID;
			total = point = mPoint;
		}
	}

	// sắp xếp giảm dần theo điểm, bằng điểm thì xét tên theo thứ tự từ điển
	Comparator<User> DesSort = new Comparator<User>() {
		public int compare(User o1, User o2) {
			if (o1.point == o2.point) {
				return o1.name.compareTo(o2.name);
			}
			return o2.point - o1.point;
		}
	};
}


package ElectronicsMarket;

//  Tham khảo thêm bài làm của CloudyWind và Doãn Thanh Tùng
import java.util.ArrayList;
import java.util.List;

class UserSolution {
	// danh sách mặt hàng được phân theo [warehouse][type]
	// mỗi list[][] sẽ là một ArrayList
	List<Product> list[][] = new ArrayList[2][3];
	int charge; // phí ship

	void init(int mCharge) {
		charge = mCharge;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 3; j++) {
				// danh sách products trong warehouse i, type j
				list[i][j] = new ArrayList<UserSolution.Product>();
			}
		}
	}

	// thêm sản phẩm vào list, có cùng warehouse và type
	int stock(int mType, int mPrice, int mPerformance, int mPosition) {
		list[mPosition][mType].add(new Product(mPrice, mPerformance));
		return list[mPosition][mType].size();
	}

	// binary search
	Solution.Result order(int mBudget) {
		// res lưu giá tiền không vượt quá mBudget và có max performance
		Solution.Result res = new Solution.Result();
		int l = 0;
		int r = 1000000; // max performance
		while (l + 1 < r) {
			int mid = (l + r) / 2;
			// lưu giá trị min của mỗi type trong warehouse 0, 1 và cả hai
			int[][] MinVals = new int[3][3];
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 3; j++) {
					int minPrice = 500000; // max budget
					for (Product p : list[i][j]) {
						if (p.performance >= mid && p.price < minPrice) {
							minPrice = p.price;
							// tìm product có performance đủ lớn và có giá min
							// trong list[i][j]
						}
					}
					MinVals[i][j] = minPrice;
				}
			}
			// tìm min trong min của mỗi warehouse
			MinVals[2][0] = Math.min(MinVals[0][0], MinVals[1][0]);
			MinVals[2][1] = Math.min(MinVals[0][1], MinVals[1][1]);
			MinVals[2][2] = Math.min(MinVals[0][2], MinVals[1][2]);
			// tìm min price của tổng các linh kiện trong các trường hợp min
			// nếu mua từ cùng một warehouse thì không mất phí vận chuyển charge
			int minPrice = Math.min(Math.min(MinVals[0][0] + MinVals[0][1]
					+ MinVals[0][2], MinVals[1][0] + MinVals[1][1]
					+ MinVals[1][2]), MinVals[2][0] + MinVals[2][1]
					+ MinVals[2][2] + charge);
			// đây là giá tiền nhỏ nhất để mua các sản phẩm mà mỗi sản phẩm có
			// performance lớn hơn mid
			// tức là giá tiền nhỏ nhất để có được sản phẩm với performance là
			// mid
			// vì performanc tổng chính là performance nhỏ nhất trong số các sản
			// phẩm

			if (minPrice <= mBudget) {
				res.mPrice = minPrice;
				res.mPerformance = l = mid;
			} else {
				r = mid;
			}
		}
		return res;
	}

	class Product {
		int price, performance;

		public Product(int mPrice, int mPerformance) {
			price = mPrice;
			performance = mPerformance;
		}
	}
}


package HotelTravel;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

class UserSolution {
	Hotel[] hotels;

	void init(int N, int mBrands[]) {
		hotels = new Hotel[N];
		for (int i = 0; i < N; i++) {
			hotels[i] = new Hotel();
			hotels[i].brand = mBrands[i];
		}
	}

	void connect(int mHotelA, int mHotelB, int mDistance) {
		hotels[mHotelA].roads.put(hotels[mHotelB], mDistance);
		hotels[mHotelB].roads.put(hotels[mHotelA], mDistance);
	}

	int merge(int mHotelA, int mHotelB) {
		int a = hotels[mHotelA].brand;
		int b = hotels[mHotelB].brand;
		int count = 0;
		for (Hotel hotel : hotels) {
			if (hotel.brand == b || hotel.brand == a) {
				hotel.brand = a;
				++count;
			}
		}
		return count;
	}

	int move(int mStart, int mBrandA, int mBrandB) {
		for (Hotel hotel : hotels) { // ?
			hotel.distance = Integer.MAX_VALUE;
		}
		Queue<Hotel> queue = new PriorityQueue<>((a, b) -> a.distance
				- b.distance); // sắp xếp tăng dần
		hotels[mStart].distance = 0;
		queue.add(hotels[mStart]);

		int result = 0;
		int count = 0;
		while (true) {
			Hotel hotel = queue.poll(); // lấy hotel có khoảng cách ngắn nhất
										// tới hotel xuất phát
			if (hotel.distance > 0
					&& (hotel.brand == mBrandA || hotel.brand == mBrandB)) {
				if (hotel.brand == mBrandA) {
					mBrandA = -1;
				} else {
					mBrandB = -1;
				}
				result += hotel.distance;
				if (++count == 2) {
					return result;
				}
			}

			// lưu ý cách duyệt key trong map
			// thuật toán dijkstra, từ node start, duyệt tất cả các con đường
			// nối từ nó (kể cả các đỉnh đã được duyệt rồi)
			// cập nhật giá trị cho các node nó nối tới
			// nếu node nó nối tới đã có giá trị mà lớn hơn giá trị tổng đi từ
			// đỉnh hiện tại, thì cập nhật lại cho node mới đó
			// chọn đỉnh có trọng số nhỏ nhất làm điểm đến tiếp theo

			// những đỉnh làm điểm đến thì không cần duyệt nữa
			for (Hotel next : hotel.roads.keySet()) { // duyệt danh sách key là
														// các hotel dưới dạng
														// Set
				int road = hotel.roads.get(next);
				if (hotel.distance + road < next.distance) {
					queue.remove(next);
					next.distance = hotel.distance + road;
					queue.add(next);
				}
			}
		}
	}

	class Hotel {
		int brand;
		int distance; // khoảng cách min từ vị trí start tới hotel này
		Map<Hotel, Integer> roads = new HashMap<>();
		// mỗi hotel có một map, lưu khoảng cách đường tới các hotel bên cạnh
		// dùng để connect, thay cho arraylist
	}

}


package LibraryClassification;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class UserSolution {
	// private final static int MAX_N = 5;
	// private final static int MAX_NAME_LEN = 7;
	// private final static int MAX_TAG_LEN = 4;

	// map type -> books
	Map<String, Set<String>> books = new HashMap<>();
	// map bookname -> int section
	// db lưu trữ sách - section phục vụ cho thêm, sửa, xóa
	Map<String, Integer> map = new HashMap<>();

	// M sections, đánh số từ 1 tới M
	void init(int M) {
		books.clear();
		map.clear();
	}

	void add(char mName[], int mTypeNum, char mTypes[][], int mSection) {
		for (int i = 0; i < mTypeNum; i++) {
			books.computeIfAbsent(string(mTypes[i]), k -> new HashSet<>()).add(
					string(mName));
		}
		map.put(string(mName), mSection);
	}

	int moveType(char mType[], int mFrom, int mTo) {
		// lấy danh sách sách có tham số Type / hashMap
		// từ danh sách đó lọc ra các sách có tham số Section / hashMap
		// cập nhật là method put
		int count = 0;
		for (String book : books.get(string(mType))) {
			if (map.get(book) == mFrom) {
				map.put(book, mTo);
				count++;
			}
		}
		return count; // trả về số sách được dịch chuyển
	}

	void moveName(char mName[], int mSection) {
		// bản chất là cập nhật section của sách
		// dùng lại put
		map.put(string(mName), mSection);
	}

	void deleteName(char mName[]) {
		// sections đánh dấu từ 1 tới M
		map.put(string(mName), 0);
	}

	// trả về số lượng sách thuộc mSection có ít nhất một nhãn dán Type trong
	// mảng
	// mTypes
	// lưu ý đếm trùng
	// CTDL HashSet
	int countBook(int mTypeNum, char mTypes[][], int mSection) {
		Set<String> set = new HashSet<>();
		for (int i = 0; i < mTypeNum; i++) {
			if (books.containsKey(string(mTypes[i]))) {
				for (String book : books.get(string(mTypes[i]))) {
					if (map.get(book) == mSection) {
						set.add(book);
					}
				}
			}
		}

		return set.size();
	}

	String string(char[] s) {
		int n = -1;
		while (s[++n] != 0)
			;
		return new String(s, 0, n);
		// char[], startIndex, endIndex
	}

	// void mstrcpy(char dst[], char src[])
	// {
	// int c = 0;
	// while ((dst[c] = src[c]) != '\0') ++c;
	// }

	// int mstrcmp(char str1[], char str2[])
	// {
	// int c = 0;
	// while (str1[c] != '\0' && str1[c] == str2[c]) ++c;
	// return str1[c] - str2[c];
	// }

}


package LibraryClassification;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class UserSolution2 {
	Map<String, Set<String>> books = new HashMap<>();;
	Map<String, Integer> sections = new HashMap<>();

	void init(int M) {
		books.clear();
		sections.clear();
	}

	void add(char mName[], int mTypeNum, char mTypes[][], int mSection) {
		for (int i = 0; i < mTypeNum; i++)
			books.computeIfAbsent(string(mTypes[i]), k -> new HashSet<>()).add(
					string(mName));
		sections.put(string(mName), mSection);
	}

	int moveType(char mType[], int mFrom, int mTo) {
		int cnt = 0;
		for (String book : books.get(string(mType)))
			if (sections.get(book) == mFrom) {
				sections.put(book, mTo);
				cnt++;
			}
		return cnt;
	}

	void moveName(char mName[], int mSection) {
		sections.put(string(mName), mSection);
	}

	void deleteName(char mName[]) {
		sections.put(string(mName), 0);
	}

	int countBook(int mTypeNum, char mTypes[][], int mSection) {
		Set<String> set = new HashSet<>();
		for (int i = 0; i < mTypeNum; i++)
			if (books.containsKey(string(mTypes[i])))
				for (String book : books.get(string(mTypes[i])))
					if (sections.get(book) == mSection)
						set.add(book);
		return set.size();
	}

	String string(char[] s) {
		int n = -1;
		while (s[++n] != 0)
			;
		return new String(s, 0, n);
	}
}


package LockerAssignment;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class UserSolution {
	// map id người --> id allocated locker
	Map<Integer, Integer> map;
	// tsSize --> tìm vị trí trống theo yêu cầu để đặt
	// tsID --> hỗ trợ nối blank space sau khi có người rời
	TreeSet<Space> tsSize, tsID;
	int N; // số lockers

	public void init(int N) {
		this.N = N;
		map = new HashMap<>();
		// ưu tiên size lớn -> sắp xếp giảm dần theo Size
		// ưu tiên locker trống đầu tiên -> sắp xếp tăng dần theo Start
		tsSize = new TreeSet<>((a, b) -> a.size() == b.size() ? a.start
				- b.start : b.size() - a.size());
		// danh sách blank locker theo thứ tự ID
		tsID = new TreeSet<>((a, b) -> a.start - b.start);
		tsSize.add(new Space(1, N));
		tsID.add(new Space(1, N));
	}

	public int arrive(int mId) {
		// xác định chuỗi blank dài nhất -> remove tại 2 cây
		Space blank = tsSize.pollFirst();
		tsID.remove(blank);

		// xác định ID của blank locker để allocated -> return ID này

		// điểm giữa chuỗi space, nếu chuỗi chẵn thì nhích hơn về bên trái
		int id = (blank.start + blank.end) / 2;
		// chuỗi blank dài nhất có start = 1 hoặc end = N
		if (blank.start == 1) {
			id = 1;
		} else if (blank.end == N) {
			id = N;
		}
		map.put(mId, id);

		// xác định lại các blank space để thêm vào treeSet
		// nếu chuỗi có độ dài >= 3 và id nằm giữa thì có 2 blank mới được tạo
		// nếu chuỗi có độ dài 1 thì không có blank nào mới
		// nếu chuỗi có độ dài >= 2 và id nằm ở đầu hoặc cuối thì có 1 blank mới
		// được tạo

		if (id > blank.start) {
			tsSize.add(new Space(blank.start, id - 1));
			tsID.add(new Space(blank.start, id - 1));
		}
		if (id < blank.end) {
			tsSize.add(new Space(id + 1, blank.end));
			tsID.add(new Space(id + 1, blank.end));
		}
		return id; // locker number allocated
	}

	public int leave(int mId) {
		int idSpace = map.remove(mId);
		Space blank = new Space(idSpace, idSpace);

		// nối blank space
		// tìm -> kiểm tra start, end, null -> remove và set lại start end cho
		// blank
		Space front = tsID.lower(blank);
		Space behind = tsID.higher(blank);
		if (front != null && front.end == idSpace - 1) {
			tsSize.remove(front);
			tsID.remove(front);
			blank.start = front.start;
		}
		if (behind != null && behind.start == idSpace + 1) {
			tsSize.remove(behind);
			tsID.remove(behind);
			blank.end = behind.end;
		}

		// thêm blank mới (đã được gộp với blank xung quanh) vào treeSet
		tsSize.add(blank);
		tsID.add(blank);
		return N - map.size();
		// số lượng ô trống = N - số những vị trí có người, tức
		// map.size()
		// C2 là duyệt treeSet, tính tổng các size của các Space trong treeSet
	}

	class Space {
		int start, end, size;

		// boolean blank ?

		Space(int mStart, int mEnd) {
			start = mStart;
			end = mEnd;
		}

		int size() {
			return end - start + 1; // không cần +1 cũng được
		}
	}
}


package LockerAssignment;

import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeSet;

class UserSolution2 {

	static int N, countEmpty;
	HashMap<Integer, Range> blankMap = new HashMap<Integer, Range>();
	Comparator<Range> compare = new Comparator<Range>() {
		public int compare(Range o1, Range o2) {
			if (o1.size == o2.size) {
				return o1.start - o2.start;
			}
			return o2.size - o1.size;
		}
	};
	TreeSet<Range> ts = new TreeSet<Range>(compare);
	HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

	void init(int N) {
		this.N = N;
		countEmpty = N;
		blankMap.clear();
		ts.clear();
		hm.clear();
		addRange(1, N);
	}

	void addRange(int start, int end) {
		// nếu làm theo cách arrive và arrive1 thì không cần đoạn code này
		// if (start > end)
		// return;
		Range newRange = new Range(start, end);
		blankMap.put(start, newRange);
		blankMap.put(end, newRange);
		ts.add(newRange);
	}

	void removeRange(Range blank) {
		blankMap.remove(blank.start);
		blankMap.remove(blank.end);
		ts.remove(blank);
	}

	public int arrive(int mId) {

		// đặt thì phải remove
		Range blank = ts.pollFirst();
		blankMap.remove(blank.start);
		blankMap.remove(blank.end);

		int idSpace = -1;
		countEmpty--;

		if (blank.start == 1) {
			if (blank.end > 1) {
				addRange(2, blank.end);
			}
			idSpace = 1;
		} else if (blank.end == N) {
			if (blank.start < N) {
				addRange(blank.start, N - 1);
			}
			idSpace = N;
		} else {
			// idSpace = blank.start + blank.size / 2;
			// if (blank.size % 2 == 0) {
			// idSpace--;
			// }
			idSpace = (blank.start + blank.end) / 2;
			if (idSpace > blank.start) {
				addRange(blank.start, idSpace - 1);
			}
			if (idSpace < blank.end) {
				addRange(idSpace + 1, blank.end);
			}
		}
		hm.put(mId, idSpace);
		return idSpace;
	}

	public int arrive1(int mId) {
		countEmpty--;

		// tìm blank dài nhất -> xóa khỏi tsSize và hashMap, ở cách 1 thì là
		// tsID
		Range blank = ts.pollFirst();
		blankMap.remove(blank.start);
		blankMap.remove(blank.end);

		int idSpace = (blank.start + blank.end) / 2;
		if (blank.start == 1) {
			idSpace = 1;
		} else if (blank.end == N) {
			idSpace = N;
		}

		if (idSpace > blank.start) {
			addRange(blank.start, idSpace - 1);
		}
		if (idSpace < blank.end) {
			addRange(idSpace + 1, blank.end);
		}
		hm.put(mId, idSpace);
		return idSpace;
	}

	public int arrive2(int mId) {
		int idSpace = -1;
		countEmpty--;

		Range blank = ts.pollFirst();
		blankMap.remove(blank.start);
		blankMap.remove(blank.end);
		if (blank.start == 1) {
			addRange(2, blank.end);
			idSpace = 1;
		} else if (blank.end == N) {
			addRange(blank.start, N - 1);
			idSpace = N;
		} else {
			// idSpace = blank.start + blank.size / 2;
			// if (blank.size % 2 == 0) {
			// idSpace--;
			// }
			idSpace = (blank.start + blank.end) / 2;
			addRange(blank.start, idSpace - 1);
			addRange(idSpace + 1, blank.end);
		}
		hm.put(mId, idSpace);
		return idSpace;
	}

	public int leave(int mId) {
		countEmpty++;
		// int idSpace = hm.get(mId);
		// hm.remove(mId);
		int idSpace = hm.remove(mId);
		Range front = blankMap.get(idSpace - 1);
		Range behind = blankMap.get(idSpace + 1);
		if (front != null && behind != null) {
			removeRange(front);
			removeRange(behind);
			addRange(front.start, behind.end);
		} else if (behind != null) {
			removeRange(behind);
			addRange(idSpace, behind.end);
		} else if (front != null) {
			removeRange(front);
			addRange(front.start, idSpace);
		} else {
			addRange(idSpace, idSpace);
		}
		return countEmpty;
	}

	static class Range {
		// range of blank spaces
		int start, end, size;

		public Range(int mStart, int mEnd) {
			start = mStart;
			end = mEnd;
			this.size = end - start + 1;
		}
	}

}


package MagicString;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class UserSolution {
	// DB quản lý các String prefix -> Node
	Map<String, Node> map = new HashMap<>();

	// dùng để cập nhật thời gian chết cho cụm String - Node
	Set<Node> set = new HashSet<>(); // quản trị cây Node

	void init(int N) {
		map.clear();
		set.clear();
	}

	// vấn đề thời gian sống được quyết định bởi endTime của node mới nhất
	// endTime của String được quyết định theo nhóm mà nó gia nhập
	// Node cũ gia nhập Node mới

	// quy tắc kết bạn: kết bạn với cả bạn của bạn
	int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]) {
		Node newNode = new Node();
		newNode.cnt[mLen]++;
		newNode.endTime = mTimestamp + mLifespan;
		set.add(newNode);

		// chưa put vào map vội
		// node cha gồm các chuỗi cũng chứa sub keyword của node con
		// node cha là node mới hơn được tạo
		for (int i = 0; i < mLen - 2; i++) {
			// tại sao cần "" ở đầu ?
			String sub = "" + mStr[i] + mStr[i + 1] + mStr[i + 2];
			Node node = map.get(sub); // node này có thể đã chết nhưng ta không
										// quan tâm
			if (node != null) {
				node = node.getRoot();
				node.update(mTimestamp);
				if (!node.isDeleted) {
					newNode.merge(node);
				}
			}
			map.put(sub, newNode);
		}
		return checkString(mTimestamp, mLen);
	}

	int checkString(int mTimestamp, int mLen) {
		int count = 0;
		set.forEach(node -> node.update(mTimestamp)); // xác định sống chết
		set.removeIf(node -> node.isDeleted); // vừa lọc vừa xóa node
		for (Node node : set) {
			count += node.cnt[mLen];
		}
		return count;
	}

	// tổ chức cây
	// mỗi Node đại diện cho một nhóm các chuỗi có chung substring

	class Node {
		int endTime;
		boolean isDeleted;
		Node parent; // ?
		int[] cnt = new int[11]; // đếm số chuỗi theo độ dài

		Node getRoot() {
			return parent == null ? this : parent.getRoot();
		}

		void update(int time) {
			if (endTime <= time) {
				isDeleted = true;
			}
		}

		void merge(Node node) { // ?
			if (node != this) {
				node.isDeleted = true;
				node.parent = this;
				for (int i = 5; i <= 10; i++) {
					cnt[i] += node.cnt[i]; // ?
				}
			}
		}
	}
}


package MagicString;

// Soumitra Jain
import java.util.ArrayList;
import java.util.HashMap;

class UserSolution2 {

	class Word {
		int deathTime;
		boolean isDel;
		int[] dataArr = new int[11];
		Word parent;

		public Word() {
			this.parent = this;
		}
	}

	private Word findParent(Word word) {
		if (word.parent == word) {
			return word;
		}
		return findParent(word.parent);
	}

	private void union(Word a, Word b) {
		Word aParent = findParent(a);
		Word bParent = findParent(b);
		if (aParent == bParent) {
			return;
		}
		b.parent = a;
		for (int i = 5; i < 11; i++) {
			a.dataArr[i] += b.dataArr[i];
		}
		b.isDel = true;
	}

	private void update(Word word, int timeStamp) {
		if (word.deathTime <= timeStamp) {
			word.isDel = true;
		}
	}

	HashMap<String, Word> hMap = new HashMap<>();
	ArrayList<Word> db = new ArrayList<>();

	void init(int N) {
		hMap.clear();
		db.clear();
	}

	int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]) {

		Word w1 = new Word();
		w1.dataArr[mLen]++;
		w1.deathTime = mTimestamp + mLifespan;
		db.add(w1);
		for (int i = 0; i < mLen - 2; i++) {
			String str = "" + mStr[i] + mStr[i + 1] + mStr[i + 2];
			if (hMap.containsKey(str)) {
				Word temp = hMap.get(str);
				Word tempParent = findParent(temp);
				update(tempParent, mTimestamp);
				if (!tempParent.isDel) {
					union(w1, tempParent);
				}
			}
			hMap.put(str, w1);
		}
		return checkString(mTimestamp, mLen);
	}

	int checkString(int mTimestamp, int mLen) {
		int res = 0;
		ArrayList<Word> toBeRemoved = new ArrayList<>();
		for (Word word : db) {
			update(word, mTimestamp);
			if (word.isDel) {
				toBeRemoved.add(word);
			}
		}
		for (Word word : toBeRemoved) {
			db.remove(word);
		}
		for (Word word : db) {
			res += word.dataArr[mLen];
		}
		return res;
	}
}


package MagicString;

// Bùi Văn Long, Bùi Khánh Hiển
import java.util.ArrayList;
import java.util.List;

class UserSolution3 {

	// HashMap<String, Word> wordDB = new HashMap<>();
	// List<Word> wordList = new ArrayList<>();
	// Word[][][] wordDB = new Word[26][26][26];
	List<Word> wordList = new ArrayList<>();
	Word[][][] wordDB = new Word[26][26][26];

	void init(int N) {
		wordList.clear();
		for (int i = 0; i < 26; i++) {
			for (int j = 0; j < 26; j++) {
				for (int k = 0; k < 26; k++) {
					wordDB[i][j][k] = null;
				}
			}
		}
	}

	int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]) {
		Word word = new Word();
		word.count[mLen]++;
		word.deadTime = mTimestamp + mLifespan;
		wordList.add(word);
		for (int i = 0; i < mLen - 2; i++) {
			int a = mStr[i] - 'a';
			int b = mStr[i + 1] - 'a';
			int c = mStr[i + 2] - 'a';
			if (wordDB[a][b][c] != null) {
				Word tmp = wordDB[a][b][c];
				Word tmp_parent = find(tmp);
				update(tmp_parent, mTimestamp);
				if (tmp_parent.isAlive) {
					union(word, tmp_parent);
				}
			}
			wordDB[a][b][c] = word;

			// String s = "";
			// s = "" + mStr[i] + mStr[i + 1] + mStr[i + 2];
			// if (wordMap.containsKey(s)) {
			// Word tmp = wordMap.get(s);
			// Word tmp_parent = find(tmp);
			// update(tmp_parent, mTimestamp);
			// if (tmp_parent.isAlive) {
			// union(word, tmp_parent);
			// }
			// }
		}
		return checkString(mTimestamp, mLen);
	}

	int checkString(int mTimestamp, int mLen) {
		int ans = 0;
		List<Word> deadList = new ArrayList<>();
		for (Word word : wordList) {
			update(word, mTimestamp);
			if (!word.isAlive) {
				deadList.add(word);
			}
		}
		for (Word word : deadList) {
			wordList.remove(word);
		}
		for (Word word : wordList) {
			ans += word.count[mLen];
		}
		return ans;
	}

	// Disjoint Set
	private Word find(Word word) {
		if (word.parent == word) {
			return word;
		}
		return find(word.parent);
	}

	private void union(Word w1, Word w2) {
		Word w1_parent = find(w1);
		Word w2_parent = find(w2);
		if (w1_parent == w2_parent) {
			return;
		}
		w2.parent = w1;
		for (int i = 5; i < 11; i++) {
			w1.count[i] += w2.count[i];
		}
		w2.isAlive = false;
	}

	private void update(Word w, int Timestamp) {
		if (w.deadTime <= Timestamp) {
			w.isAlive = false;
		}
	}

	class Word {
		int deadTime;
		boolean isAlive;
		int[] count = new int[11];
		Word parent;

		public Word() {
			this.isAlive = true;
			this.parent = this;
		}

	}
}


package MemorySystem;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class UserSolution {
	// map điểm bắt đầu lưu trữ và kích cỡ của đoạn lưu trữ đó
	Map<Integer, Integer> mapSize;
	TreeSet<Memory> freeSpace;

	public void init(int N) {
		mapSize = new HashMap<>();
		// định vị theo thứ tự
		freeSpace = new TreeSet<>((a, b) -> a.start - b.start);
		freeSpace.add(new Memory(0, N));
	}

	public int allocate(int mSize) {
		TreeSet<Memory> sortedFreeSpace = new TreeSet<>((a, b) -> a.size()
				- b.size());
		sortedFreeSpace.addAll(freeSpace);
		Memory memory = sortedFreeSpace.ceiling(new Memory(0, mSize));
		if (memory == null) {
			return -1;
		}
		mapSize.put(memory.start, mSize);
		freeSpace.remove(memory);
		if (mSize < memory.size()) {
			Memory remain = new Memory(memory.start + mSize, memory.end);
			freeSpace.add(remain);
		}
		return memory.start;
	}

	public int release(int mAddr) {
		if (!mapSize.containsKey(mAddr)) {
			return -1;
		}

		// trả về value của key bị remove
		int size = mapSize.remove(mAddr);
		Memory memory = new Memory(mAddr, mAddr + size);
		// gộp freeSpace
		Memory front = freeSpace.lower(memory);
		Memory rear = freeSpace.higher(memory);
		if (front != null && front.end == mAddr) {
			freeSpace.remove(front);
			memory.start = front.start;
		}
		if (rear != null && rear.start == mAddr + size) {
			freeSpace.remove(rear);
			memory.end = rear.end;
		}
		freeSpace.add(memory);
		return size;
	}

	class Memory {
		int start, end;

		Memory(int mStart, int mEnd) {
			start = mStart;
			end = mEnd;
		}

		int size() {
			return end - start;
		}
	}
}


package MemorySystem;

import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeSet;

class UserSolution2 {
	class Memory {
		int start;
		int end;
		int size;
		boolean blank;

		public Memory(int mStart, int mEnd, int mSize) {
			start = mStart;
			end = mEnd;
			size = mSize;
			blank = true;
		}
	}

	HashMap<Integer, Memory> hm = new HashMap<>();
	TreeSet<Memory> ts = new TreeSet<>(new CmpSize());

	public void init(int N) {
		hm.clear();
		ts.clear();
		Memory memory = new Memory(0, N - 1, N);
		ts.add(memory);
		hm.put(memory.start, memory);
		hm.put(memory.end, memory);
	}

	public int allocate(int mSize) {
		Memory temp = new Memory(-1, 0, mSize);
		Memory empty = ts.ceiling(temp);
		RemoveMemory(empty);
		int result = -1;
		if (empty != null) {
			temp.start = empty.start;
			temp.end = temp.start + mSize - 1;
			temp.size = mSize;
			temp.blank = false;
			hm.put(temp.start, temp);
			hm.put(temp.end, temp);
			result = temp.start;
			if (empty.size > temp.size) {
				Memory newMemory = new Memory(empty.start + mSize, empty.end,
						empty.size - mSize);
				hm.put(newMemory.start, newMemory);
				hm.put(newMemory.end, newMemory);
				ts.add(newMemory);
			}
		}
		return result;
	}

	public void RemoveMemory(Memory Memory) {
		if (Memory != null) {
			ts.remove(Memory);
			hm.remove(Memory.start);
			hm.remove(Memory.end);
		}
	}

	public int release(int mAddr) {
		Memory temp = hm.get(mAddr);
		int result = -1;
		if (temp != null && !temp.blank && temp.start == mAddr) {
			temp.blank = true;
			result = temp.size;
			Memory before = hm.get(temp.start - 1);
			if (before != null && before.blank) {
				temp.start = before.start;
				temp.size += before.size;
				ts.remove(before);
			}
			Memory after = hm.get(temp.end + 1);
			if (after != null && after.blank) {
				temp.end = after.end;
				temp.size += after.size;
				ts.remove(after);
			}
			hm.put(temp.start, temp);
			hm.put(temp.end, temp);
			ts.add(temp);
		}
		return result;
	}

	class CmpSize implements Comparator<Memory> {
		public int compare(Memory n1, Memory n2) {
			if (n1.size == n2.size)
				return n1.start - n2.start;
			return n1.size - n2.size;
		}
	}
}


package NewsFeed;

import java.util.TreeSet;

class UserSolution {

	News news[];
	TreeSet<News> sections[] = new TreeSet[10];
	int[] interested;

	void init() {
		news = new News[50001];
		for (int i = 0; i < 10; i++) {
			sections[i] = new TreeSet<>((a, b) -> a.read == b.read ? b.id
					- a.id : b.read - a.read);
		} // sắp xếp giảm dần theo lượt đọc
		interested = new int[100001];
		for (int i = 0; i < 100001; i++) {
			interested[i] = -1;
		}
	}

	void addNews(int mSection, int mNewsId) {
		news[mNewsId] = new News(mNewsId, mSection);
		sections[mSection].add(news[mNewsId]);
	}

	void eraseNews(int mNewsId) {
		sections[news[mNewsId].section].remove(news[mNewsId]);
	}

	void readNews(int mUserId, int mNewsId) {
		News n = news[mNewsId];
		interested[mUserId] = n.section;
		sections[n.section].remove(n);
		n.read++;
		sections[n.section].add(n);
	}

	void changeSection(int mNewsId, int mSection) {
		sections[news[mNewsId].section].remove(news[mNewsId]);
		sections[mSection].add(news[mNewsId]);
		news[mNewsId].section = mSection;
	}

	int getList(int mUserId, int mList[]) {
		int count = 0;
		while (!isEmpty()) {
			int maxScore = 0;
			int maxId = 0;
			for (int i = 0; i < 10; i++) {
				if (!sections[i].isEmpty()) {
					News topNews = sections[i].first();
					int score = interested[mUserId] == i ? topNews.read + 10
							: topNews.read;
					if (score > maxScore
							|| (score == maxScore && topNews.id > maxId)) {
						maxScore = score;
						maxId = topNews.id;
					}
				}
			}
			sections[news[maxId].section].remove(news[maxId]);
			mList[count++] = maxId;
			if (count == 10) {
				break;
			}
		}
		for (int i = 0; i < count; i++) {
			sections[news[mList[i]].section].add(news[mList[i]]);
		}
		return count;
	}

	boolean isEmpty() {
		for (int i = 0; i < 10; i++) {
			if (!sections[i].isEmpty()) {
				return false;
			}
		}
		return true;
	}

	class News {
		int id, section, read;

		public News(int mId, int mSection) {
			id = mId;
			section = mSection;
		}
	}

}


package NewsNotification;

// Doãn Thanh Tùng
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

class UserSolution {
	Map<Integer, Channel> channels = new HashMap<>();
	Map<Integer, User> users = new HashMap<>();
	Map<Integer, News> news = new HashMap<>();
	Queue<News> heap = new PriorityQueue<>((a, b) -> a.time - b.time);

	void init(int N, int K) {
		channels.clear();
		users.clear();
		news.clear();
		heap.clear();
	}

	void registerUser(int mTime, int mUID, int mNum, int mChannelIDs[]) {
		User user = users.computeIfAbsent(mUID, k -> new User());
		for (int i = 0; i < mNum; i++) {
			Channel channel = channels.computeIfAbsent(mChannelIDs[i],
					k -> new Channel());
			channel.users.put(mUID, mTime);
			user.channels.add(channel);
		}
	}

	int offerNews(int mTime, int mNewsID, int mDelay, int mChannelID) {
		News n = new News(mTime + mDelay, mNewsID, mChannelID);
		news.put(mNewsID, n);
		heap.add(n);
		return channels.get(mChannelID).users.size();
	}

	void cancelNews(int mTime, int mNewsID) {
		News n = news.get(mNewsID);
		Channel channel = channels.get(n.channelID);
		channel.news.remove(n);
		heap.remove(n);
	}

	int checkUser(int mTime, int mUID, int mRetIDs[]) {
		while (!heap.isEmpty() && heap.peek().time <= mTime) {
			News news = heap.poll();
			Channel channel = channels.get(news.channelID);
			channel.news.add(news);
		}
		int size = 0;
		TreeSet<News> top3 = new TreeSet<>((a, b) -> a.time == b.time ? b.id
				- a.id : b.time - a.time);
		for (Channel channel : users.get(mUID).channels) {
			int registerTime = channel.users.get(mUID);
			Set<News> noticed = channel.news.headSet(new News(registerTime + 1,
					0, 0));
			size += noticed.size();
			int cnt = 0;
			for (News news : noticed) {
				if (cnt++ == 3)
					break;
				if (top3.add(news) && top3.size() > 3)
					top3.pollLast();
			}
			channel.users.put(mUID, mTime);
		}
		int i = 0;
		for (News news : top3)
			mRetIDs[i++] = news.id;
		return size;
	}
}

class Channel {
	Map<Integer, Integer> users = new HashMap<>();
	TreeSet<News> news = new TreeSet<>((a, b) -> a.time == b.time ? b.id - a.id
			: b.time - a.time);
}

class User {
	List<Channel> channels = new ArrayList<>();
}

class News {
	int time, id, channelID;

	News(int mTime, int mID, int mChannelID) {
		time = mTime;
		id = mID;
		channelID = mChannelID;
	}
}


package NotepadProgram;

import java.util.LinkedList;

class UserSolution {
	int H, W, cursor, size;
	LinkedList<Character> notepad[];
	int count[][];

	void init(int H, int W, char mStr[]) {
		this.H = H;
		this.W = W;
		notepad = new LinkedList[H];
		// mỗi hàng là một LinkedList
		for (int i = 0; i < H; i++)
			notepad[i] = new LinkedList<Character>();

		count = new int[H][26];
		cursor = 0;
		size = 0;

		int i = 0; // index của xâu cần nhập - dùng để nhập
		int row = 0;
		while (mStr[i] != '\0') {
			if (i == (row + 1) * W)
				row++;
			notepad[row].add(mStr[i]); // nhập ký tự mStr[i]
			// đếm số lần xuất hiện trong hàng của ký tự
			count[row][mStr[i] - 'a']++;
			size++;
			i++;
		}
	}

	void insert(char mChar) {
		int row = cursor / W;
		int col = cursor % W;
		// thêm ký tự vào vị trí col của linkedlist row
		notepad[row].add(col, mChar);
		count[row][mChar - 'a']++;
		cursor++;
		size++;

		// dịch phần tử tràn xuống hàng dưới
		for (int i = row; i < H; i++) {
			if (notepad[i].size() > W) {
				char temp = notepad[i].removeLast();
				count[i][temp - 'a']--;
				notepad[i + 1].addFirst(temp);
				count[i + 1][temp - 'a']++;
			}
		}
	}

	char moveCursor(int mRow, int mCol) {
		// -1 để đưa về index 0
		cursor = (mRow - 1) * W + mCol - 1;
		if (cursor >= size) {
			cursor = size;
			return '$';
		}
		return notepad[mRow - 1].get(mCol - 1);
	}

	int countCharacter(char mChar) {
		int row = cursor / W;
		int col = cursor % W;
		int cnt = 0;
		int i = 0;
		for (char c : notepad[row]) {
			if (i >= col && mChar == c)
				cnt++;
			i++;
		}
		for (int j = row + 1; j < H; j++)
			cnt += count[j][mChar - 'a'];

		return cnt;
	}
}


package NotepadProgram;

import java.util.ArrayList;
import java.util.Collections;

class UserSolution2 {
	int H, W, cursor, size;
	ArrayList<Character> notepad[];
	int count[][];

	void init(int H, int W, char mStr[]) {
		this.H = H;
		this.W = W;
		notepad = new ArrayList[H];
		// mỗi hàng là một ArrayList
		for (int i = 0; i < H; i++)
			notepad[i] = new ArrayList<Character>();

		count = new int[H][26];
		cursor = 0;
		size = 0;

		int i = 0; // index của xâu cần nhập - dùng để nhập
		int row = 0;
		while (mStr[i] != '\0') {
			if (i == (row + 1) * W)
				row++;
			notepad[row].add(mStr[i]); // nhập ký tự mStr[i]
			count[row][mStr[i] - 'a']++;
			// đếm số lần xuất hiện trong hàng của ký tự
			size++;
			i++;
		}
	}

	void insert(char mChar) {
		int row = cursor / W;
		int col = cursor % W;
		// thêm ký tự vào vị trí col của ArrayList row
		notepad[row].add(col, mChar);
		count[row][mChar - 'a']++;
		cursor++;
		size++;

		// dịch phần tử tràn xuống hàng dưới
		for (int i = row; i < H; i++) {
			if (notepad[i].size() > W) {
				char temp = notepad[i].remove(notepad[i].size() - 1);
				count[i][temp - 'a']--;
				notepad[i + 1].add(0, temp);
				count[i + 1][temp - 'a']++;
			}
		}
	}

	char moveCursor(int mRow, int mCol) {
		// -1 để đưa về index 0
		cursor = (mRow - 1) * W + mCol - 1;
		if (cursor >= size) {
			cursor = size;
			return '$';
		}
		return notepad[mRow - 1].get(mCol - 1);
	}

	int countCharacter(char mChar) {
		int row = cursor / W;
		int col = cursor % W;
		// int cnt = 0;
		// int i = col;
		// for (char c : notepad[row]) {
		// if (i >= col && mChar == c)
		// cnt++;
		// i++; // tăng index cho tới khi bằng với vị trí cursor
		// }
		int cnt = Collections.frequency(
				notepad[row].subList(col, notepad[row].size()), mChar);
		// kể từ các row lớn hơn, cộng thẳng tần số xuất hiện
		for (int j = row + 1; j < H; j++)
			cnt += count[j][mChar - 'a'];

		return cnt;
	}
}


package PhylogeneticTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class UserSolution {
	Map<String, Node> map = new HashMap<>();
	static int countNode;

	public void init(char[] mRootSpecies) {
		map.clear();
		map.put(new String(mRootSpecies), new Node());
	}

	public void add(char[] mSpecies, char[] mParentSpecies) {
		Node a = map.get(new String(mParentSpecies));
		Node b = new Node();
		b.parent = a;
		b.depth = a.depth + 1;
		a.link.add(b);
		b.link.add(a);
		map.put(new String(mSpecies), b);

	}

	public int getDistance(char[] mSpecies1, char[] mSpecies2) {
		Node a = map.get(new String(mSpecies1));
		Node b = map.get(new String(mSpecies2));
		int count = 0;
		// dịch node cho đến khi trùng nhau
		// chiến thuật là cho 2 node dịch dần lên node cha, mỗi lần count++
		// cả 2 đều có chung node cha, vấn đề cần dịch sao cho gặp nhau ở node
		// cha gần nhất
		while (a != b) {
			if (a.depth > b.depth) {
				a = a.parent;
			} else {
				b = b.parent;
			}
			count++;
		}
		return count;
	}

	int getCount(char[] mSpecies, int mDistance) {
		countNode = 0; // nếu đặt global countNode = 0 và bên trong hàm getCount
						// thiếu đoạn này thì sẽ sai --> do countNode cần phải
						// reset mỗi khi hàm này được gọi
		Node start = map.get(new String(mSpecies));
		deQuy(start, null, mDistance);
		return countNode;
	}

	// đệ quy
	// không có chu trình nên không cần mảng đánh dấu các đỉnh đã được duyệt
	void deQuy(Node cur, Node pre, int dis) {
		if (dis == 0) {
			countNode++;
			return;
		}
		for (Node next : cur.link) {
			if (next != pre) {
				deQuy(next, cur, dis - 1);
			}
		}
	}

	public int getCount1(char[] mSpecies, int mDistance) {
		Node start = map.get(new String(mSpecies));
		return deQuy1(start, null, mDistance);
	}

	// đệ quy
	// không có chu trình nên không cần mảng đánh dấu các đỉnh đã được duyệt
	public int deQuy1(Node cur, Node pre, int dis) {
		int count = 0;
		if (dis == 0) {
			return 1;
		}
		for (Node next : cur.link) {
			if (next != pre) {
				count += deQuy1(next, cur, dis - 1);
			}
		}
		return count;
	}

	String string(char[] s) {
		return new String(s).trim();
	}

	class Node {
		Node parent;
		int depth; // ?
		List<Node> link = new ArrayList<>();
		Set<Node> link2 = new HashSet<>();
	}
}


package Reorganization;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class UserSolution {
	Map<Integer, Node> map = new HashMap<>();
	Node root;
	int curGroup;

	public void init(int mId, int mNum) {
		root = new Node(mId, mNum);
		map.put(mId, root);
	}

	public int add(int mId, int mNum, int mParent) {
		Node parent = map.get(mParent);
		if (parent.child.size() == 2) {
			return -1;
		}
		Node node = new Node(mId, mNum);
		map.put(mId, node);

		// connect node to its parent
		node.parent = parent;
		parent.child.add(node);

		// trả về tổng số người - root là parent
		Node cur = parent;
		// thêm mNum vào mọi node phía trên nó
		while (cur != null) {
			cur.total += mNum;
			cur = cur.parent;
		}
		return parent.total;
	}

	public int remove(int mId) {
		Node node = map.remove(mId);
		if (node == null) {
			return -1;
		}
		// cập nhật trạng thái
		node.isRemoved = true;
		// xóa khỏi danh sách node con của node cha
		Node parent = node.parent;
		parent.child.remove(node);
		// cập nhật total của các node bên trên node bị xóa
		Node cur = parent;
		while (cur != null) {
			if (cur.isRemoved) { // quan trọng
				return -1;
			}
			cur.total -= node.total;
			cur = cur.parent;
		}

		return node.total;
	}

	int tryCut(Node node, int M, int K) {
		// nếu có tòa nhà mà số lượng người lớn hơn K thì auto dừng
		if (curGroup > M || node.num > K) {
			curGroup = M + 1;
			return 0;
		}
		// từ Node gốc, xác định số người ở hai nhánh trái - phải
		// số lượng người ở nhánh trái numL là hàm đệ quy của node con thứ 1
		// số lượng người ở nhánh phải numR là hàm đệ quy của node con thứ 2
		// return của hàm tryCut phải là tổng số người của subTree tại node là
		// tham số truyền vào
		// return node.num + numL (của node đó) + numR (của node đó)
		int numL, numR;
		numL = numR = 0;

		int size = node.child.size();
		if (size >= 1) {
			numL = tryCut(node.child.get(0), M, K);
		}
		if (size == 2) {
			numR = tryCut(node.child.get(1), M, K);
		}

		// có thể chia nhánh trái của node (tức là tạo group từ node và nhánh
		// trái của nó)
		// numL là số người còn lại trong nhóm con trái chứ không phải số người
		// trong nhóm con trái
		// mục đích gán lại bằng 0 là để loại bỏ số lượng người còn lại ở nhóm
		// con trái
		// khỏi số lượng người ở nhóm hiện tại khi return ở cuối
		// khi numL hoặc numR được gán = 0, tức là số đó được gom thành 1 group
		if (node.num + numL > K) {
			numL = 0;
			curGroup++;
		}

		if (node.num + numR > K) {
			numR = 0;
			curGroup++;
		}

		// nếu chỉ dính 1 trong 2 if bên trên thì if thứ 3 này sẽ không dính
		// nếu cả 2 if bên trên đều không dính thì kiểm tra if thứ 3 này

		// quy tắc đệ quy là ép xuống phía dưới các đoạn nhỏ nhất có thể mà <= K
		// nên lựa chọn chia cắt nhóm con lớn hơn
		// vì kết quả của nhóm hiện tại chính lại được dùng để gán vào numL hoặc
		// numR của node bên trên
		// nên cần đảm bảo việc gom nhóm nhỏ nhất

		if (node.num + numL + numR > K) {
			if (numL >= numR) {
				numL = 0;
			} else {
				numR = 0;
			}
			curGroup++;
		}
		// trả về số lượng người của subTree hiện tại từ node tham số
		return node.num + numL + numR;
	}

	public int reorganize(int M, int K) {
		curGroup = 1;
		tryCut(root, M, K);
		return curGroup <= M ? 1 : 0;
	}
}

class Node { // represent a department
	int id;
	int num; // people in current department
	int total; // people in total subtree
	boolean isRemoved;
	Node parent;
	List<Node> child = new ArrayList<>();

	public Node(int mId, int mNum) {
		id = mId;
		num = total = mNum;
	}
}


package Reorganization;

import java.util.HashMap;

class UserSolution3 {

	public class department {
		int ID;
		int members;
		int sum_members;
		department parent;
		department[] subsivisions = new department[2];
		boolean isremove;

		public department(int id, int num, department par) {
			this.ID = id;
			this.members = num;
			this.parent = par;
			this.sum_members = num;
		}
	}

	HashMap<Integer, department> hashIDdeparment = new HashMap<>();
	int cnt = 0;
	department Root;

	public void init(int mId, int mNum) {
		hashIDdeparment.clear();
		Root = new department(mId, mNum, null);
		hashIDdeparment.put(mId, Root);
		return;
	}

	public int add(int mId, int mNum, int mParent) {
		department parent = hashIDdeparment.get(mParent);
		if (parent.subsivisions[1] != null && parent.subsivisions[0] != null) { // parent
																				// co
																				// 2
																				// subsivision
																				// roi
			return -1;
		}
		department ndepartment = new department(mId, mNum, parent);
		hashIDdeparment.put(mId, ndepartment);

		if (parent.subsivisions[0] == null) { // add subsivisions cho parent
			parent.subsivisions[0] = ndepartment;
			;
		} else {
			parent.subsivisions[1] = ndepartment;
		}
		department temp = parent;
		while (temp != null) {
			temp.sum_members += mNum;
			temp = temp.parent;
		}
		return parent.sum_members;
	}

	public int remove(int mId) {
		department rmdepartment = hashIDdeparment.remove(mId); // neu ko ton tai
																// key mId =>
																// rmdepartment
																// = null
		if (rmdepartment == null) {
			return -1;
		}
		department parent = rmdepartment.parent;
		rmdepartment.isremove = true;
		if (parent.subsivisions[0] == rmdepartment) { // xoa subsivisions cua
														// parent
			parent.subsivisions[0] = null;
		} else {
			parent.subsivisions[1] = null;
		}
		department temp = rmdepartment.parent;
		int x = rmdepartment.sum_members;
		while (temp != null) {
			if (temp.isremove) {
				return -1;
			}
			temp.sum_members -= x;
			;
			temp = temp.parent;
		}
		return x;
	}

	public int reorganize(int M, int K) {
		cnt = 0;
		make(M, K, Root);
		if (cnt < M) {
			return 1;
		}
		return 0;
	}

	int make(int M, int K, department dp) {
		if (dp == null) {
			return 0;
		}
		if (dp.members > K) { // ton tai department co employees lon hon K =>
								// fail
			cnt = M;
			return 0;
		}
		if (cnt >= M) {
			return 0;
		}

		int left = make(M, K, dp.subsivisions[0]);
		int right = make(M, K, dp.subsivisions[1]);
		int rsWleft = dp.members + left;
		int rsWright = dp.members + right;
		int rsWleft_right = dp.members + left + right;

		if (rsWleft_right <= K) { // ko chia
			return rsWleft_right;
		}
		if (rsWleft <= K && rsWright <= K) {
			cnt++;
			if (rsWleft <= rsWright) {
				return rsWleft;
			} else {
				return rsWright;
			}
		}
		if (rsWleft <= K) {
			cnt++;
			return rsWleft;
		}
		if (rsWright <= K) {
			cnt++;
			return rsWright;
		}
		cnt += 2;
		return dp.members;
	}
}


package SchoolRecordInquiry;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeSet;

class UserSolution {
	// chọn cấu trúc dữ liệu phù hợp
	// map id --> đối tượng
	Map<Integer, Student> map = new HashMap<>();
	// danh sách quản lý học sinh theo khối và giới tính
	// vì đây là hai thuộc tính tham số khi query
	TreeSet<Student> students[][] = new TreeSet[4][2];

	public void init() {
		map.clear();
		for (int i = 1; i <= 3; i++) {
			for (int j = 0; j < 2; j++) {
				// sắp xếp tăng dần theo điểm số và id (nếu điểm số bằng nhau
				// thì trả về id nhỏ hơn)
				// students[i][j] = new TreeSet<>(
				// (a, b) -> a.score == b.score ? a.id - b.id : a.score
				// - b.score);

				// students[i][j] = new TreeSet<>(new sort());

				students[i][j] = new TreeSet<>(sort);
			}
		}
	}

	public int add(int mId, int mGrade, char mGender[], int mScore) {
		// khởi tạo đối tượng từ tham số truyền vào
		Student newStudent = new Student(mId, mGrade, mGender, mScore);
		map.put(mId, newStudent);
		students[mGrade][newStudent.gender].add(newStudent);

		// trả về id student có điểm cao nhất
		return students[mGrade][newStudent.gender].last().id;
	}

	public int remove2(int mId) {
		Student student = map.get(mId);
		// map.remove(mId); không cần vì khi put đã được update lại
		if (student != null) {
			students[student.grade][student.gender].remove(student);
			if (!students[student.grade][student.gender].isEmpty()) {
				return students[student.grade][student.gender].first().id;
			}
		}
		return 0;
	}

	public int remove(int mId) {
		Student student = map.remove(mId); // return null nếu key không tồn tại
		// Student student = map.get(mId);
		// map.remove(mId); không cần vì khi put đã được update lại
		if (student == null) {
			return 0;
		}
		students[student.grade][student.gender].remove(student);
		if (students[student.grade][student.gender].isEmpty()) {
			return 0;
		}
		return students[student.grade][student.gender].first().id;
	}

	public int query(int mGradeCnt, int mGrade[], int mGenderCnt,
			char mGender[][], int mScore) {
		TreeSet<Student> querySet = new TreeSet<>(
				(a, b) -> a.score == b.score ? a.id - b.id : a.score - b.score);
		for (int i = 0; i < mGradeCnt; i++) {
			for (int j = 0; j < mGenderCnt; j++) {
				Student student = new Student(198, mGrade[i], mGender[j],
						mScore); // ?
				Student lowest = students[student.grade][student.gender]
						.ceiling(student);
				if (lowest != null) {
					querySet.add(lowest);
				}
			}
		}
		return querySet.isEmpty() ? 0 : querySet.first().id;
	}

	public int query2(int mGradeCnt, int mGrade[], int mGenderCnt,
			char mGender[][], int mScore) {
		PriorityQueue<Student> heap = new PriorityQueue<>(sort);
		for (int i = 0; i < mGradeCnt; i++) {
			for (int j = 0; j < mGenderCnt; j++) {
				// Student student = new Student(198, mGrade[i], mGender[j],
				// mScore); // ?
				int gender = mGender[j][0] == 'm' ? 1 : 0;
				Student lowest = students[mGrade[i]][gender]
						.ceiling(new Student(-1, -1, mGender[j], mScore));
				if (lowest != null) {
					heap.add(lowest);
				}
			}
		}
		return heap.isEmpty() ? 0 : heap.poll().id;
	}

	class sort implements Comparator<Student> {
		public int compare(Student o1, Student o2) {
			if (o1.score == o2.score) {
				return o1.id - o2.id;
			}
			return o1.score - o2.score;
		}
	}

	Comparator<Student> sort = new Comparator<Student>() {
		public int compare(Student o1, Student o2) {
			if (o1.score == o2.score) {
				return o1.id - o2.id;
			}
			return o1.score - o2.score;
		}
	};

	class Student {
		int id, grade, gender, score;

		Student(int mId, int mGrade, char[] mGender, int mScore) {
			id = mId;
			grade = mGrade;
			gender = mGender[0] == 'm' ? 1 : 0;
			score = mScore;
		}
	}
}


package SchoolRecordInquiry;

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.TreeSet;

class UserSolution2 {
	TreeSet<Student>[][] students;
	HashMap<Integer, Student> map;

	public void init() {
		map = new HashMap<>();
		students = new TreeSet[4][2];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 2; j++) {
				students[i][j] = new TreeSet<>(
						(a, b) -> a.score == b.score ? a.id - b.id : a.score
								- b.score);
			}
		}
	}

	public int add(int mId, int mGrade, char mGender[], int mScore) {
		int gender = 1;
		// if (mGender[0] - 'a' == 5)
		// gender = 0;
		if (mGender[0] == 'f') {
			gender = 0;
		}
		Student newStudent = new Student(mId, mGrade, gender, mScore);

		map.put(mId, newStudent);
		students[mGrade][gender].add(newStudent);
		return students[mGrade][gender].last().id;
	}

	public int remove(int mId) {
		Student student = map.get(mId);
		if (student == null)
			return 0;
		map.remove(student.id);
		students[student.grade][student.gender].remove(student);
		if (students[student.grade][student.gender].isEmpty())
			return 0;
		return students[student.grade][student.gender].first().id;
	}

	public int query(int mGradeCnt, int mGrade[], int mGenderCnt,
			char mGender[][], int mScore) {
		// chuyển mảng mGender -> gender
		int[] gender = { 0, 1 };
		if (mGenderCnt == 1) {
			int G = 1;
			// if (mGender[0][0] - 'a' == 5)
			// G = 0;
			if (mGender[0][0] == 'f')
				G = 0;
			gender = new int[] { G };
		}
		PriorityQueue<Student> heap = new PriorityQueue<>(
				(a, b) -> a.score == b.score ? a.id - b.id : a.score - b.score);
		for (int k = 0; k < mGradeCnt; k++) {
			for (int l = 0; l < mGenderCnt; l++) {
				int i = mGrade[k];
				int j = gender[l];
				// if (!students[i][j].isEmpty()) {
				// Student tailStudent = students[i][j].ceiling(new Student(
				// -1, -1, -1, mScore));
				// if (tailStudent != null) {
				// heap.add(tailStudent);
				// }
				// }

				Student lowest = students[i][j].ceiling(new Student(-1, -1, -1,
						mScore));
				if (lowest != null) {
					heap.add(lowest);
				}

			}
		}
		if (heap.isEmpty())
			return 0;
		return heap.poll().id;
	}

	class Student {
		int id;
		int score;
		int gender;
		int grade;

		public Student(int mId, int mGrade, int mGender, int mScore) {
			id = mId;
			grade = mGrade;
			gender = mGender;
			score = mScore;
		}
	}
}


package SecondHandMarketApp;

// tham khảo lời giải của Vũ Chí Bảo, XZ
// tham khảo UserSolution4 với phương thức filter
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class UserSolution {
	// map string tag với danh sách sản phẩm
	Map<String, List<Product>> products;

	void init(int N) {
		products = new HashMap<String, List<Product>>();
	}

	void addProduct(int mPrice, int tagNum, char tagName[][]) {
		// khởi tạo
		// thêm sản phẩm vào từng tag riêng
		Product product = new Product(mPrice);
		String[] tags = new String[tagNum];
		for (int i = 0; i < tagNum; i++) {
			tags[i] = string(tagName[i]);
			products.computeIfAbsent(tags[i], k -> new ArrayList<>()).add(
					product);
		}
		// sort tags để khi ghép tag được chuỗi duy nhất
		// thêm sản phầm vào cả 3 tags
		Arrays.sort(tags);
		for (int i = 0; i < tagNum; i++) {
			for (int j = i + 1; j < tagNum; j++) {
				for (int j2 = j + 1; j2 < tagNum; j2++) {
					products.computeIfAbsent(tags[i] + tags[j] + tags[j2],
							k -> new ArrayList<>()).add(product);
				}
			}
		}
	}

	int buyProduct(char tag1[], char tag2[], char tag3[]) {
		String[] tags = { string(tag1), string(tag2), string(tag3) };
		Arrays.sort(tags);
		String tag = tags[0] + tags[1] + tags[2];
		// xóa tất cả sản phẩm có isRemoved = true được gắn với tag
		products.computeIfAbsent(tag, k -> new ArrayList<>()).removeIf(
				x -> x.isRemoved);
		if (products.get(tag).isEmpty()) {
			return -1;
		}
		Product res = Collections.min(products.get(tag), (a, b) -> a.price
				- b.price);
		// tốt hơn là remove luôn khỏi danh sách của các tag1, tag2, tag3
		// Product res = Collections.max(products.get(tag), (a, b) -> b.price
		// - a.price);
		res.isRemoved = true;
		return res.price;
	}

	void adjustPrice(char tag1[], int changePrice) {
		for (Product product : products.get(string(tag1))) {
			product.price += changePrice;
		}

		// version đủ hơn
		// String key = string(tag1);
		// if (!products.containsKey(key)) {
		// return;
		// }
		// List<Product> proList = products.get(key);
		// for (Product product : proList) {
		// if (!product.isRemoved) {
		// product.price += changePrice;
		// }
		// }
	}

	String string(char s[]) {
		int n = -1;
		while (s[++n] != 0)
			; // tăng n = độ dài mảng ký tự
		// String temp = new String(s);
		// int n = temp.indexOf('\0');
		return new String(s, 0, n);
		// return String.valueOf(str, 0, c);
	}
	// String charToString(char tagName[]) {
	// StringBuilder res = new StringBuilder();
	// for (int i = 0; tagName[i] != '\0'; i++) {
	// res.append(tagName[i]);
	// }
	// return res.toString();
	// }
}

class Product {
	int price;
	boolean isRemoved;

	public Product(int mPrice) {
		price = mPrice;
		isRemoved = false;
	}
}


package SurvivalTrain;

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

class UserSolution3 {
	TreeSet<Passenger> sections[];
	Passenger passengers[];
	List<Integer> jobs[];

	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)
				sections[i / M] = new TreeSet<>(
						(a, b) -> a.point == b.point ? a.id - b.id : b.point
								- a.point); // sắp xếp giảm dần theo điểm và
											// tăng dần theo id
			passengers[i] = new Passenger(i, mPoint[i], mJobID[i]);
			sections[i / M].add(passengers[i]);
			jobs[mJobID[i]].add(i);
		}
	}

	void destroy() {
	}

	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

	int move(int mNum) {
		int sum = 0;
		// lưu danh sách hành khách
		List<Passenger> temp[] = new ArrayList[sections.length - 1];
		for (int i = 0; i <= sections.length - 2; i++) {
			temp[i] = new ArrayList<>();
			// find and remove min from section 0 to length-2
			// store in temp[]
			for (int j = 0; j < mNum; j++) {
				Passenger smallest = sections[i].pollLast(); // do sắp xếp giảm
																// dần
				temp[i].add(smallest);
				sum += smallest.point;
			}
			// find and remove max from section 1 to length-1
			// readd max to sections before
			for (int j = 0; j < mNum; j++) {
				Passenger largest = sections[i + 1].pollFirst();
				sections[i].add(largest);
				sum += largest.point;
			}
		}
		// readd min to sections after
		for (int i = 0; i < temp.length; i++)
			sections[i + 1].addAll(temp[i]);
		return sum;
	}

	class Passenger {
		int id, point, jobID;

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


package SurvivalTrain;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

class UserSolution4 {
	TreeSet<Passenger> sections[];
	Passenger passengers[];
	List<Integer> jobs[];
	int sectionSize;

	void init(int N, int M, int J, int mPoint[], int mJobID[]) {
		sectionSize = M;
		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)
				sections[i / M] = new TreeSet<>(
						(a, b) -> a.point == b.point ? a.id - b.id : b.point
								- a.point); // sắp xếp giảm dần theo điểm và
											// tăng dần theo id
			passengers[i] = new Passenger(i, mPoint[i], mJobID[i]);
			sections[i / M].add(passengers[i]);
			jobs[mJobID[i]].add(i);
		}
	}

	void destroy() {
	}

	// sai vì cách truy xuất dữ liệu section tương ứng passenger chỉ đúng khi sự
	// dịch chuyển chưa xảy ra sau init

	// int update(int mID, int mPoint) {
	// Passenger p = passengers[mID];
	// int sectionIndex = p.id / sectionSize;
	// if (sections[sectionIndex].remove(p)) {
	// p.point += mPoint;
	// sections[sectionIndex].add(p);
	// }
	// return p.point;
	// }
	//
	// int updateByJob(int mJobID, int mPoint) {
	// int sum = 0;
	// for (int pID : jobs[mJobID]) {
	// Passenger p = passengers[pID];
	// int sectionIndex = p.id / sectionSize;
	// if (sections[sectionIndex].remove(p)) {
	// p.point += mPoint;
	// sum += p.point;
	// sections[sectionIndex].add(p);
	// }
	// }
	// return sum;
	// }

	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

	int move(int mNum) {
		int sum = 0;
		// sum là tổng điểm các hành khách được di chuyển, nói cách khác là các
		// điểm min max
		// lưu danh sách hành khách
		List<Passenger> temp[] = new ArrayList[sections.length - 1];
		for (int i = 0; i <= sections.length - 2; i++) {
			temp[i] = new ArrayList<>();
			// find and remove min from section 0 to length-2
			// store in temp[]
			for (int j = 0; j < mNum; j++) {
				Passenger smallest = sections[i].pollLast(); // do sắp xếp giảm
																// dần
				temp[i].add(smallest);
				sum += smallest.point;
			}
			// find and remove max from section 1 to length-1
			// readd max to sections before
			for (int j = 0; j < mNum; j++) {
				Passenger largest = sections[i + 1].pollFirst();
				sections[i].add(largest);
				sum += largest.point;
			}
		}
		// readd min to sections after
		for (int i = 0; i < temp.length; i++)
			sections[i + 1].addAll(temp[i]);
		return sum;
	}

	class Passenger {
		int id, point, jobID;

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


package SurvivalTrain;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

class UserSolution5 {
	TreeSet<Passenger> sections[];
	Passenger passengers[];
	List<Integer> jobs[];
	int numS;

	void init(int N, int M, int J, int mPoint[], int mJobID[]) {
		numS = N / M;
		sections = new TreeSet[numS];
		passengers = new Passenger[N];
		jobs = new ArrayList[J];
		for (int i = 0; i < J; i++)
			jobs[i] = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			if (sections[i / M] == null)
				sections[i / M] = new TreeSet<>(new maxFirst());
			// 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);
		}
	}

	int update(int mID, int mPoint) {
		Passenger p = passengers[mID];
		sections[p.sectionIndex].remove(p);
		p.point += mPoint;
		sections[p.sectionIndex].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.sectionIndex].remove(p);
			p.point += mPoint;
			sum += p.point;
			sections[p.sectionIndex].add(p);
		}
		return sum;
	}

	int move(int mNum) {
		int sum = 0;
		List<Passenger> temp[] = new ArrayList[numS - 1];
		for (int i = 0; i <= numS - 2; i++) {
			temp[i] = new ArrayList<>();
			for (int j = 0; j < mNum; j++) {
				Passenger min = sections[i].pollLast();
				min.sectionIndex++;
				temp[i].add(min);
				sum += min.point;
			}
			for (int j = 0; j < mNum; j++) {
				Passenger max = sections[i + 1].pollFirst();
				max.sectionIndex--;
				sections[i].add(max);
				sum += max.point;
			}
		}
		for (int i = 0; i < temp.length; i++)
			sections[i + 1].addAll(temp[i]);
		return sum;
	}

	class maxFirst implements Comparator<Passenger> {
		public int compare(Passenger a, Passenger b) {
			if (a.point == b.point)
				return a.id - b.id;
			else
				return b.point - a.point;
		}
	}

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

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

	void destroy() {
	}
}


package SurvivalTrain;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.TreeSet;

class UserSolution6 {
	TreeSet<Passenger> sections[];
	Passenger passengers[];
	List<Integer> jobs[];
	HashMap<Integer, Integer> passengerSectionMap;

	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];
		passengerSectionMap = new HashMap<>();
		for (int i = 0; i < N; i++) {
			if (sections[i / M] == null)
				sections[i / M] = new TreeSet<>(
						(a, b) -> a.point == b.point ? a.id - b.id : b.point
								- a.point); // sắp xếp giảm dần theo điểm và
											// tăng dần theo id
			passengers[i] = new Passenger(i, mPoint[i], mJobID[i]);
			sections[i / M].add(passengers[i]);
			passengerSectionMap.put(i, i / M);
			jobs[mJobID[i]].add(i);
		}
	}

	void destroy() {
	}

	int update(int mID, int mPoint) {
		Passenger p = passengers[mID];
		int sectionIndex = passengerSectionMap.get(mID);
		sections[sectionIndex].remove(p);
		p.point += mPoint;
		sections[sectionIndex].add(p);
		return p.point;
	}

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

	// section có kiểu dữ liệu treeSey đã đã đượ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

	int move(int mNum) {
		int sum = 0;
		// lưu danh sách hành khách
		List<Passenger> temp[] = new ArrayList[sections.length - 1];
		for (int i = 0; i <= sections.length - 2; i++) {
			temp[i] = new ArrayList<>();
			// find and remove min from section 0 to length-2
			// store in temp[]
			for (int j = 0; j < mNum; j++) {
				Passenger smallest = sections[i].pollLast(); // do sắp xếp giảm
																// dần
				passengerSectionMap.put(smallest.id, i + 1);
				temp[i].add(smallest);
				sum += smallest.point;
			}
			// find and remove max from section 1 to length-1
			// readd max to sections before
			for (int j = 0; j < mNum; j++) {
				Passenger largest = sections[i + 1].pollFirst();
				passengerSectionMap.put(largest.id, i);
				sections[i].add(largest);
				sum += largest.point;
			}
		}
		// readd min to sections after
		for (int i = 0; i < temp.length; i++)
			sections[i + 1].addAll(temp[i]);
		return sum;
	}

	class Passenger {
		int id, point, jobID;

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


package ValueOfRestaurant;

// Đang Lỗi
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

// N cities, mỗi thành phố có ID từ 1 -> N
// tên của các nhà hàng được thêm vào thành phố theo ID của cities
class UserSolution {
	// dùng mảng để lưu các đối tượng cities
	City[] cities;
	// map tên -> điểm của nhà hàng
	Map<String, Integer> mapScore;
	// map substring -> điểm số max trong số những nhà hàng chứa substring
	Map<String, Integer> mapMax;

	// cần CTDL tối ưu để lưu N cities và M roads
	// dùng mảng để lưu N đối tượng cities, trong đối tượng cities có danh sách
	// Integer linkTo để lưu những thành phố khác cùng nó tạo thành đường
	void init(int N, int M, int mRoads[][]) {
		cities = new City[N + 1];
		for (int i = 1; i <= N; i++) {
			cities[i] = new City();
		}
		// mRoads[i][0] là chỉ số cities1; mRoads[i][1] là chỉ số cities2
		// của 2 đầu road thứ i (index từ 0 -> M-1)
		for (int i = 0; i < M; i++) {
			cities[mRoads[i][0]].linkTo.add(mRoads[i][1]);
			cities[mRoads[i][1]].linkTo.add(mRoads[i][0]); // đường 2 chiều
		}
	}

	public void addRestaurant(int mCityID, char mName[]) {
		cities[mCityID].resList.add(string(mName));
	}

	// thêm mScore vào điểm số hiện tại của nhà hàng mName
	// --> add, update
	// cấu trúc map lưu nhà hàng, có put vừa add + update
	// nếu nhà hàng chưa có điểm thì cần tạo mới --> getOrDefault
	void addValue(char mName[], int mScore) {
		String name = string(mName);
		int score = mapScore.getOrDefault(name, 0) + mScore;
		mapScore.put(name, score); // add hoặc update
		// gen tất cả các substring có thể
		for (int i = 0; i < name.length(); i++) {
			for (int j = 1; i + j <= name.length(); j++) {
				String sub = name.substring(i, i + j);
				if (mapMax.getOrDefault(sub, 0) < score) {
					mapMax.put(sub, score);
				}
			}
		}
	}

	// nếu không có nhà hàng nào chứa substring mStr thì return 0
	int bestValue(char mStr[]) {
		return mapMax.getOrDefault(string(mStr), 0);
	}

	public int regionalValue(int mCityID, int mDist) {
		Queue<Integer> queue = new ArrayDeque<>();
		Queue<Integer> top3 = new PriorityQueue<>(); // sắp xếp tăng dần
		// lưu quãng đường từ thành phố hiện tại tới một thành phố bất kỳ
		int[] dist = new int[cities.length];
		queue.add(mCityID);
		while (!queue.isEmpty()) {
			int curCity = queue.poll();
			// lọc ra top3 nhà hàng có điểm cao nhất trong 1 city
			// lại được đặt trong vòng while để duyệt city nên khi kết thúc vòng
			// while, sẽ tìm được top 3 nhà hàng ở tất cả city trong bán kính
			for (String name : cities[curCity].resList) {
				top3.add(mapScore.getOrDefault(name, 0));
				if (top3.size() > 3) {
					top3.poll(); // xóa phần tử nhỏ nhất
				}
			}

			for (int next : cities[curCity].linkTo) {
				if (dist[next] == 0 && next != mCityID) {
					dist[next] = dist[curCity] + 1;
					if (dist[next] <= mDist) {
						queue.add(next);
					}
				}
			}
		}
		int sum = 0;
		for (int score : top3) {
			sum += score;
		}
		return sum;
	}

	class City {
		// danh sách nhà hàng trong city
		List<String> resList = new ArrayList<>();
		// danh sách những thành phố mà city này nối tới
		List<Integer> linkTo = new ArrayList<>();
	}

	String string(char[] s) {
		return new String(s).trim();
	}
}



package ValueOfRestaurant;

// Doãn Thanh Tùng
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

class UserSolution2 {
	City[] city;
	Map<String, Integer> mapScore, best;

	void init(int N, int M, int mRoads[][]) {
		city = new City[N + 1];
		for (int i = 1; i <= N; i++)
			city[i] = new City();
		for (int i = 0; i < M; i++) {
			city[mRoads[i][0]].connect.add(mRoads[i][1]);
			city[mRoads[i][1]].connect.add(mRoads[i][0]);
		}
		mapScore = new HashMap<>();
		best = new HashMap<>();
	}

	void addRestaurant(int mCityID, char mName[]) {
		city[mCityID].restaurants.add(string(mName));
	}

	void addValue(char mName[], int mScore) {
		String name = string(mName);
		int score = mapScore.getOrDefault(name, 0) + mScore;
		mapScore.put(name, score);
		for (int i = 0; i < name.length(); i++) {
			for (int j = 1; i + j <= name.length(); j++) {
				String sub = name.substring(i, i + j);
				if (best.getOrDefault(sub, 0) < score)
					best.put(sub, score);
			}
		}
	}

	int bestValue(char mStr[]) {
		return best.getOrDefault(string(mStr), 0);
	}

	int regionalValue(int mCityID, int mDist) {
		Queue<Integer> queue = new ArrayDeque<>(), top3 = new PriorityQueue<>();
		int[] dist = new int[city.length];
		queue.add(mCityID);
		while (!queue.isEmpty()) {
			int currCity = queue.poll();
			for (String name : city[currCity].restaurants) {
				top3.add(mapScore.getOrDefault(name, 0));
				if (top3.size() > 3)
					top3.poll();
			}

			for (int i : city[currCity].connect)
				if (dist[i] == 0 && i != mCityID) {
					dist[i] = dist[currCity] + 1;
					if (dist[i] <= mDist)
						queue.add(i);
				}
		}

		int sum = 0;
		for (int score : top3)
			sum += score;
		return sum;
	}

	String string(char[] s) {
		int n = -1;
		while (s[++n] != 0)
			;
		return new String(s, 0, n);
	}
}

class City {
	List<String> restaurants = new ArrayList<>();
	List<Integer> connect = new ArrayList<>();
}


package WordMaze;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class UserSolution {
	// mapDir[] là global database
	Map<String, TreeSet<String>> mapDir[] = new HashMap[3];
	// mapDir dùng để lưu trữ tất cả tiền tố, trung tố, hậu tố và map vào các từ
	// được sắp xếp theo thứ tự từ điển
	// String = keyword - tiền tố, hậu tố... / TreeSet<String> là danh sách từ
	// toàn vẹn
	Map<String, Room> map = new HashMap<>();
	Room current;

	void init() {
		map.clear();
		for (int i = 0; i < 3; i++) {
			mapDir[i] = new HashMap<>();
		}
	}

	void addRoom(int mID, char[] mWord, int[] mDirLen) {
		Room room = new Room(mID, mWord, mDirLen);
		room.addToHash();
	}

	void setCurrent(char mWord[]) {
		current = map.get(string(mWord));
	}

	// di chuyển current, nếu không được return 0
	int moveDir(int mDir) {
		String keyWord = current.dir[mDir];
		if (mapDir[mDir].get(keyWord) != null) {
			for (String word : mapDir[mDir].get(keyWord)) {
				Room room = map.get(word);
				if (room != current) {
					current = room;
					return room.id;
				}
			}
		}
		return 0;
	}

	void changeWord(char mWord[], char mChgWord[], int mChgLen[]) {
		Room room = map.get(string(mWord));
		room.removeFromHash();
		addRoom(room.id, mChgWord, mChgLen);
		if (room == current) { // nếu phòng đang thay đổi là current thì cập
								// nhật lại current
			current = map.get(string(mChgWord));
		}
	}

	class Room {
		int id;
		String word;
		String dir[] = new String[3];

		Room(int mID, char[] mWord, int[] mDirlen) {
			id = mID;
			word = string(mWord);
			dir[0] = word.substring(0, mDirlen[0]);
			dir[1] = word.substring(4, 7);
			dir[2] = word.substring(word.length() - mDirlen[2]);
		}

		void addToHash() {
			// thêm Room vào map với từ khóa word
			// đảo ngược
			map.put(word, this);
			// back
			mapDir[2].computeIfAbsent(word.substring(0, 2),
					k -> new TreeSet<>()).add(word);
			mapDir[2].computeIfAbsent(word.substring(0, 4),
					k -> new TreeSet<>()).add(word);
			// middle
			mapDir[1].computeIfAbsent(word.substring(4, 7),
					k -> new TreeSet<>()).add(word);
			// front
			mapDir[0].computeIfAbsent(word.substring(7), k -> new TreeSet<>())
					.add(word);
			mapDir[0].computeIfAbsent(word.substring(9), k -> new TreeSet<>())
					.add(word);
		}

		void removeFromHash() {
			map.remove(word);
			mapDir[2].get(word.substring(0, 2)).remove(word);
			mapDir[2].get(word.substring(0, 4)).remove(word);
			mapDir[1].get(word.substring(4, 7)).remove(word);
			mapDir[0].get(word.substring(7)).remove(word);
			mapDir[0].get(word.substring(9)).remove(word);
		}
	}

	String string(char[] s) {
		return new String(s).trim();
	}
}