# 問題

# 解き方

二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指定回数分二分探索して見つからなかったら"NO"。

# 計算量

二分探索の繰り返し回数をkとすると O(kn)

二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指定回数分二分探索して見つからなかったら"NO"。

二分探索の繰り返し回数をkとすると O(kn)

Sometimes, program is forcibly quit when using xgboost. In that time, there are several solutions(It is true that the solution is existed except for the following).

https://www.kaggle.com/c/grupo-bimbo-inventory-demand/discussion/22321

use the external memory version http://xgboost.readthedocs.io/en/latest/how_to/external_memory.html

Try bagging sklearn.ensemble.BaggingRegressor — scikit-learn 0.18.1 documentation

You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi.

You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

1≤N≤100 1≤W≤109 1≤wi≤109 For each i=2,3,…,N, w1≤wi≤w1+3. 1≤vi≤107 W, each wi and vi are integers.

We have to check the constraints. In this problem w and v is big, so we cannot solve this problem in common dynamic programming way.
This time we use the constraint w1 ≤ wi ≤ w1 + 3. Because of this, there are at most 4 possible weights for a single item.
So I can test the all case that is how many items I have to use per 4 weights.
This time complexity is O(n^{4})

You are given a list of projects and a list of dependencies ( which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

This problem is topological sort. Topological sort algorithm is the following approach.

- Identify all nodes with no incoming edges and add those nodes to our topological sort.
- When we do the above, decline the number of incoming edges as the out coming from the added node.
- Repeat the above, When all the nodes have been added to the topological sort, then we done.

This algorithm is executed in time complexity O(V + E).

You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

If I can check the all path I can find the solution in O(n^{2}). So I suggest the optimized one.
In the optimized code, I use hash-table like two sum problem. This hash-table maps from a runningSum to the number of times we’ve seen that sum. In each node, I can find the count of root path to satisfy the condition in O(1) . So time complexity is O(n) and space complexity is O(n) to have a hash table.

T1 and T2 are two very large binary trees, with T1 much bigger than T2. Create an algorithm to determine if T2 is a subtree of T1. A tree T2 is a subtree of T1 if thre exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

I prepare two function. One is the function to determine if the 2 tree is same or not, and the other one is the function determine if the t1 is the subtree of t2. First function is implemented to check if all element is same or not recursively.

Implement an algorithm to find the kth to last element of a singly linked list

We use two pointers slow-pointer and fast-pointer. Firstly we proceed the fast-pointer in k step. Secondly, we move them at the same pace and slow pointer will hit the end of the linked list after k length . This algorithm takes O(n) time and O(1) space.