编程挑战题：SPOJ LOPOV

作者: fitcat07   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-10-27 08:36 PM 发表
无人有兴趣？
或者首先讲讲解答嘅方法。

最简单但最慢嘅方法：
0. 将 N 粒宝石价值由大至小排列，初始 answer = 0，i = 0
1. 喺 N 粒宝石中，最大价值嘅一粒系第 i 粒
2. 然后࢒ ...

有兴趣但无时间。

乜要O(n*k)咩? sort 一 sort就变O(n*log n)囉。。step 0由大至小排列已经系Θ(n*log n)啦。

作者: code4food   发布时间: 2013-12-05

引用:原帖由 code4food 於 2013-10-28 04:00 PM 发表
有兴趣但无时间。

重系咁忙呀...

引用:乜要O(n*k)咩? sort 一 sort就变O(n*log n)囉。。step 0由大至小排列已经系Θ(n*log n)啦。

步骤 0 无错系 O(N*log(N))，但每粒宝石要搵到最合身嘅袋，就要搵 K 次。总共系 O(N*log(N) + N*K)，正确应该系 O(N*(log(N) + K))。因最差情况下， K >> log(N)，所以我写 O(N*K)。

如果将 K 个袋由小至大排列(O(K*log(K))，咁每次搵就唔驶 K 次，而系 log(K) 次，快好多。总时间变成 O(N*log(N) + K*log(K) + N*log(K))。但问题系，当搵到合身嘅袋，要将之移除。有乜快嘅方法，可以移除后，使能保持搵嘅次数保持系 log(K) 呢？

呢个其实系我将会写嘅帖内容。

作者: fitcat07   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-10-28 12:36 PM 发表
无人有兴趣？
或者首先讲讲解答嘅方法。

最简单但最慢嘅方法：
0. 将 N 粒宝石价值由大至小排列，初始 answer = 0，i = 0
1. 喺 N 粒宝石中，最大价值嘅一粒系第 i 粒
2. 然后࢒ ...

Hi fitcat07,

I just think a little bit on the bus if the steps as described as your previous post that just find out the largest value of jewellery and put it to the bag such that Cm >= Mi, then how to handle the follow case:

input
3 1
4 5
6 6
7 7
10

In this case, the jewellery has largest value should be skipped and the largest total value is 5+6 = 11 and not 7. (Please tell me, if I interpret your meaning incorrectly, )

[ 本帖最后由 assembly.jc 於 2013-10-28 05:39 PM 编辑 ]

作者: assembly.jc   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-10-28 12:43 AM 发表

重系咁忙呀...
步骤 0 无错系 O(N*log(N))，但每粒宝石要搵到最合身嘅袋，就要搵 K 次。

我话sort一sort，系袋都sort埋。用balanced tree (例如std::set)。建立树嘅时间系O(k * log k), 每次搵(e.g. std::set::lower_bound())个袋同更新(std::set::erase()嘅时间系O(log k)，每个袋都装粒宝石要要用O(n* log k). k <= N, 加埋之前Θ(n * log n)都系Θ(n * log n).http://www.cplusplus.com/reference/set/set/

作者: code4food   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-10-28 06:00 PM 发表
N = 3, K = 1.

Step 0:
Sort the N pieces of jewellery: (7, 7), (6, 6), (5, 4)

Hi fitcat07,

Thanks for detail explanation. As I miss this sentence: "but at most one jewellery piece in each bag", so I think the bag can carry 2 piece of jewllery yesterday (and hence the answer should be 5+6 = 11, not 7), and now I read your post #1 and the description of the problem on SPOJ again, I eventually know why I am confused on your solution

Otherwise, if the bag can be allowed to carry any number of piece of jewellery, this problem become very complex

[ 本帖最后由 assembly.jc 於 2013-10-29 10:56 AM 编辑 ]

作者: assembly.jc   发布时间: 2013-12-05

引用:原帖由 code4food 於 2013-10-29 01:17 AM 发表
我话sort一sort，系袋都sort埋。用balanced tree (例如std::set)。建立树嘅时间系O(k * log k), 每次搵(e.g. std::set::lower_bound())个袋同更新(std::set::erase()嘅时间系O(log k)，每个袋都装粒宝石 ...

我第一眼都谂到呢个方法，我自以为用 std::set （正确系用 std::multiset）系唔够快，之前无试过。於是我谂用 std::priority_queue 会更快，因为唔须要将所有元素排序，方法系：
0. 将 N 粒宝石嘅价值由大至小排列，K 个袋依容量由小至大排列，i = 0，j = 0，pq = {}，answer = 0
1. 如果 Mi <= Cj，将 Vi 加入 pq，i = i + 1
2. 否则，如果 pq 唔系空，answer = answer + pq.top()，pq.pop()
2a. j = j + 1
3. 重复 1 直至 i >= N 或 j >= K
4. 如 j < K 同埋 pq 唔系空，answer = answer + pq.top()，pq.pop()，j = j + 1，重复 4

时间复杂度：
0. O(N*log(N) + K*log(K))
1 - 4. O(N*log(N) + N*log(N)) （加入完素 pq：N*log(N)，取出完素 pq：N*log(N)）总时间复杂度：O(3N*log(N) + K*log(K))，但出乎意料结果系 TLE。就系因为咁都唔得，我无再尝试 std::multiset，因为大家时间复杂度相似。
今日先发现原来有一个臭虫，改咗之后（错误地将步骤 2a 归入 2），用 std::priority_queue 时间系 0.11s！

经你一提，今日一试 std::multiset，竟然 AC，时间大约系 0.30s。原来呢题真系咁易（自己谂得过於复杂），早知唔驶花咁多时间去谂其他方法。不过，亦因此谂到暂时最快方法。

作者: fitcat07   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

作者: code4food   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-10-29 05:33 PM 发表
Yes, it will become a more complicated version of the normal Knapsack problem (NP-complete):
http://en.wikipedia.org/wiki/Knapsack_problem

Hi fitcat07,

Actually, many problems related to combination, such marksix, probability... combination obtains elegant properties in mathematics but not in computer science.

However, anyway, let us return to jewellery problem. and so, the problem now can be transformed to how to find a bag (that has least mass Ci) to hold the largest value Vi of piece of jewellery. Okey, haha, let me guess your best soluation (fastest version). Firstly, let us split this problem into 2 parts:

1. find the largest value of piece of jewellery
2. find the least mass of bag to hold the jewellery

for part 1, the fastest way seems to sort the values of piece of jewellery, or using heap structure. either method has complexity O(n lg n).
for part 2, instead of sorting the mass Ci hold by bags, we may apply the concept of Hash.

For example, Assume 1 <= Ci <= 100 (actually, it is 1 <= Ci <= 1,000,000, 000), we create an array that hold 10 linked-list, each node of linked-link hold the mass of bag Ci. It may look like:

复制内容到剪贴板代码:struct _linked_list;
typedef struct _linked_list {
int mass;
struct _linked_list next;
} LinkedList;

LinkedList list[10] = {NULL};

and then, once receive a value of piece of jewellery Vi, calculate i = Vi / 10. and using i to locate suitable linked-list and finally find the bag to hold the jewellery. Using Hash we may find the bag in constant time.

[ 本帖最后由 assembly.jc 於 2013-10-31 02:44 PM 编辑 ]

作者: assembly.jc   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-11-1 11:36 AM 发表 Using heap doesn't help here as we have to go through all pieces of jewellery one by one in descending order. I tried and the result showed that using heap performed worse.If the sizes of the bags are ...

Hi fitcat07,

Before you said that, I expected heap may be faster... but anyway, sorting has more choices, it is good chance for me to test the efficient of variety of sorting method, haha

引用:If the sizes of the bags are uniformly distributed, your theory is correct. However, there are no such constraint provided by the problem description. The worst case occurs when all the sizes of the bags fall into a single bucket.

and so, to avoid all bags fall into a single bucket, we may reduce the size of single bucket as small as possible. may be my previous example is too simple so that unable to present my idea clearly, let us come back to Lopov problem, since the mass hold by bag Ci can be huge (1 <= Ci <= 100,000,000), so we may use a 8-dimension void* pointer array to simulated the Hash, it may look like

void *ciHash[10][10][10][10][10][10][10][10] = {NULL};

and so, the size of each bucket of Hash can be reduced to 10 and such an array occupied 40 Mb memory. However, I am not sure whether C support 8-dimension array, if it is not, we may allocate a large block of memory firstly (say 40Mb), and calculate the hash code for each Ci by myself.

[ 本帖最后由 assembly.jc 於 2013-11-2 10:44 AM 编辑 ]

作者: assembly.jc   发布时间: 2013-12-05

引用:原帖由 assembly.jc 於 2013-11-2 10:38 AM 发表
Before you said that, I expected heap may be faster... but anyway, sorting has more choices, it is good chance for me to test the efficient of variety of sorting method, haha

This is one of the reasons that SPOJ (or other online judges) is good.

引用:to avoid all bags fall into a single bucket, we may reduce the size of single bucket as small as possible. may be my previous example is too simple so that unable to present my idea clearly, let us come back to Lopov problem, since the mass hold by bag Ci can be huge (1 <= Ci <= 100,000,000), so we may use a 8-dimension void* pointer array to simulated the Hash, it may look like

void *ciHash[10][10][10][10][10][10][10][10] = {NULL};

and so, the size of each bucket of Hash can be reduced to 10 and such an array occupied 40 Mb memory. However, I am not sure whether C support 8-dimension array, if it is not, we may allocate a large block of memory firstly (say 40Mb), and calculate the hash code for each Ci by myself.

I don't know the limit of the array dimensions of C/C++. I believe 8 is supported. If not, use of pointers can get rid of the limit.
No matter how small you set the bucket size (unless it is 1 - which decompose to a 1D array), the worst case scenario does not change - all bags can still fall into a single bucket.
Having said that, it is theoretically not helpful but it doesn't mean in practice it performs poorer. Just like quick sort, the worst case time complexity is O(N^2) but it is fast enough in normal use.
If the test cases were large and/or well-constructed, it would include data for such scenario. In practice, it may not. So, try to implement and submit it, and see...

BTW, an array of size 10^8 of pointer type (assume 32-bit pointer) has a size of 4*10^8 = 4*100MB = 400MB.

作者: fitcat07   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-11-2 04:33 PM 发表
I think I may misinterpret your method. You defined a pointer for each element in the range 1 - 100,000,000. Each pointer points to the corresponding mass of the bag. When mass x is required, the poin ...

Hi fitcat07,

Yes, you got the point, I read the problem again and find that the limit of memory size is 1536Mb, so, as you said that, it can be simply allocated 400Mb memory for an array such as

int ciHash[100000000] = { 0 };

and when the mass x of bag is provided, perform the follow operation

ciHash[x]++;

However, this method is not work, since when a jewellery associated with value Vi need to find a bag, using the Hash, then when ciHash[Vi] == 0, we can not find the mass y quickly such that

y > Vi and ciHash[y] > 0

Maybe I thank it in wrong direction from the begin

Anyway, besides the above method, I also made a wrong concept on finding the bag(please refers the part 2 as mentioned on previous post #12). that is. When the value of all pieces of jewellery have been sorted and the largest value of piece of jewellery (say Vi) is given, we don't need to find the least mass (say Ci, Ci >= Vi of course) of bag to hold the piece of jewellery, any bags that has the mass >= Vi can be chosen and don't affect the final answer. And so the mass of bags may not need to sort.

[ 本帖最后由 assembly.jc 於 2013-11-4 03:12 AM 编辑 ]

作者: assembly.jc   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-11-4 11:53 AM 发表

However, I am afraid you're wrong regarding the sorting of bags is not needed.

Consider this test case:
2 21 992 65101
If we place the f ...

Hi fitcat07,

Yes, you're right, I wrongly assume that larger value of piece of jewellery has larger mass

Otherwise, I am confused by the method on #9 as below:

引用:0. 将 N 粒宝石嘅价值由大至小排列，K 个袋依容量由小至大排列，i = 0，j = 0，pq = {}，answer = 0
1. 如果 Mi <= Cj，将 Vi 加入 pq，i = i + 1
2. 否则，如果 pq 唔系空，answer = answer + pq.top()，pq.pop()
2a. j = j + 1
3. 重复 1 直至 i >= N 或 j >= K
4. 如 j < K 同埋 pq 唔系空，answer = answer + pq.top()，pq.pop()，j = j + 1，重复 4

Does it iterate the Mi through the descending order of value of piece of jewellery ? In step 3, Is it repeats step 1 to 2a instead of step 1 until i >= N or j >= k?
How to handle the follow case?

Input:
2 1
5 5
2 2
4

N = 2, K = 1
0. Sort the value of piece of jewellery in descending order: [(M:5, V:5), (M:2), (V:2)],
Sort the mass of bag in ascending order : [(C:4)]
i=0, j=0, pg={}, anwser = 0

1. M0 = 5 > C0 = 4 => do nothing
2. pg is empty => do nothing
2a. j = j + 1 => j == 1
3. j == K => goto step 4
4. j == k => end

finally, the answer is 0, but the answer should be 2??

[ 本帖最后由 assembly.jc 於 2013-11-5 12:00 PM 编辑 ]

作者: assembly.jc   发布时间: 2013-12-05

引用:原帖由 assembly.jc 於 2013-11-5 11:53 AM 发表
Does it iterate the Mi through the descending order of value of piece of jewellery ? In step 3, Is it repeats step 1 to 2a instead of step 1 until i >= N or j >= k?

Yes, it should repeat step 1 to 2a. I should use pseudo code instead of steps as it should be more clear.

引用:How to handle the follow case? ...
1. M0 = 5 > C0 = 4 => do nothing
2. pg is empty => do nothing
2a. j = j + 1 => j == 1
3. j == K => goto step 4
4. j == k => end

finally, the answer is 0, but the answer should be 2??

Oops, Step 0 was incorrect. The sorting of jewellery should be in "ascending" order of "mass". Sorry.

作者: fitcat07   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

作者: assembly.jc   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

引用:原帖由 fitcat07 於 2013-11-20 11:26 AM 发表
The easiest way to answer your question is to use std::sort in your code, submit it and then see the result.The time complexity of radix sort is O(dn) where d is the number of digits. Since max(n) is ...

Hi fitcat07,

Thanks for your suggestion and kindly reply I shall try std::sort later. (But I have to learn C++ firstly and I have no idea on what is template )

Yes, as you said that the radix sort has been improved by switching pointers instead of copy all elements between arrays before submit to SPOJ. Also, you're right, I make a mistake on previous post, I refers back to my text book (introduction to algorithms, MIT press) the time complexity of radix sort is O(d(2n+k)), i.e. O(d(2n + 10), but since the Ci > 1,000,000 can be reduced to 1,000,001 before sorting (because of the maximum of Mi is 1,000,000) , and so, the time complexity is O(7 (2n + 10)), i.e. O(14n) for sorting the mass of bag and jewellery, right?

Otherwise, Would I ask a stupid question? Does pre-allocation of memory mean using array instead of dynamic allocate memory using malloc() like functions? If it is true, actucally, I have used pre-allocation of memory method

作者: assembly.jc   发布时间: 2013-12-05

作者: fitcat07   发布时间: 2013-12-05

作者: assembly.jc   发布时间: 2013-12-05

Glad to know my analysis is close to the fact.

The difference in time may be due to the following issues in order of significance:
1. I use fread() to read most (or all depends on the input size) of the input. My buffer size is 64KB and the maximum input size is 6.9MB. So, the total number of calls to read input is at most about 100. Yours is at most 300,000. Calling system functions especially on input/output is time consuming.
2. Since we know the maximum size, we should call std::vector.reserve() to allocate sufficient memory to avoid dynamic memory allocation due to growth in size. Fyi, GCC reserve storage for 16 elements by default, IIRC. I use static array to store both bags and jewellery. Static array is usually faster than std::vector.
3. std::sort by default sorts the elements in ascending order. So, you don't need to pass in std_comp_bag. I don't know whether this affects performance or not. Since std::sort is highly optimized, I believe omitting the third argument will help though the difference may not be significant.

作者: fitcat07   发布时间: 2013-12-05