Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

xgboost memory problem

Memory is shortage in xgboost program

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

solution

AtCoder Beginner Contest 060 D - Simple Knapsack

Problem Statement

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.

Constraints

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.

how to solve

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(n4)

code is following

Build Order

problem

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.

how to solve

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).

code

Remove all ads

Paths with Sum

problem

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).

how to use

If I can check the all path I can find the solution in O(n2). 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.

code

Remove all ads

Check Subtree

problem

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.

how to solve

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.

code

Remove all ads

return k-th to last

problem

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

how to solve

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.

code

gist.github.com

Atcoder Grand Contest : B Splatter Painting

problem

agc012.contest.atcoder.jp

how to solve

The limitation of d is very small and it is key point to solve this problem. Consider that dp[v][i] which means “paint dp[v][i] among the range d distance from vertex v”. The time complexity is O(d(n+m) + q)

code