当前位置：首页 → 问答吧 → 编程挑战题：SPOJ MAX_NUM

编程挑战题：SPOJ MAX_NUM

时间：2013-11-29

来源：互联网

呢题初初睇落好容易，以为三两下搞掂，点知 WA（wrong answer）。

再三谂谂，先知错乜。

http://www.spoj.com/problems/MAX_NUM/
做完睇番，呢题虽然唔算系好难果只，但都唔系易，有挑战性，几好玩。

作者: fitcat07 发布时间: 2013-11-29

你系正常的向后扫..

定用binary search???

作者: Susan﹏汪汪发布时间: 2013-11-30

第一次submit就收货，不过比较慢（～0.7秒）。要再谂谂。

作者: code4food 发布时间: 2013-11-30

我冇用到二分搜寻法...

作者: fitcat07 发布时间: 2013-11-30

引用:原帖由 code4food 於 2013-10-3 03:32 PM 发表
第一次submit就收货，不过比较慢（～0.7秒）。要再谂谂。

思虑够周详

作者: fitcat07 发布时间: 2013-11-30

刚刚世界排名入到前 50，宜家系 49

将勤补拙策略成功

作者: fitcat07 发布时间: 2013-11-30

引用:原帖由 fitcat07 於 2013-10-3 02:09 AM 发表
思虑够周详

改algorithm用C++写（因为懒唔想用C写FIFO），0.19秒。http://www.spoj.com/status/MAX_NUM,code4food/

作者: code4food 发布时间: 2013-11-30

引用:原帖由 code4food 於 2013-10-7 03:44 PM 发表

改algorithm用C++写（因为懒唔想用C写FIFO），0.19秒。http://www.spoj.com/status/MAX_NUM,code4food/

系喎，可以用 FIFO 加速。

不过懒，唔想改，宁做下一题。

作者: fitcat07 发布时间: 2013-11-30

引用:原帖由 fitcat07 於 2013-10-7 02:36 AM 发表
系喎，可以用 FIFO 加速。

不过懒，唔想改，宁做下一题。

真linear time algorithm，同数目字基数无关，之前b进制系O(n * log b)。用C写FIFO，0.1秒收工唔tune。http://www.spoj.com/status/MAX_NUM,code4food/

作者: code4food 发布时间: 2013-11-30

hi all

I am new to SPOJ, I feel this problem quite difficult but interesting

and I found that if I define the length of array to hold the input number as

#define MAX_DIGIT_LEN 100000
...
char n[MAX_DIGIT_LEN];
scanf("%s %d, n, &k);

It fail the test

and change to

#define MAX_DIGIT_LEN 100001

It pass

[ 本帖最后由 assembly.jc 於 2013-10-13 03:06 PM 编辑 ]

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 assembly.jc 於 2013-10-12 08:54 AM 发表
hi all

I am new to SPOJ, I feel this problem quite difficult but interesting

and I found the if I define the length of array to hold the input number as

#define MAX_DIGIT_LEN 100000
...

C string要预多一个byte装null charater '\0'。例如“hello”要6个byte 'h', 'e', 'l', 'l', 'o', '\0'。

作者: code4food 发布时间: 2013-11-30

引用:原帖由 code4food 於 2013-10-13 05:37 AM 发表

C string要预多一个byte装null charater '\0'。例如“hello”要6个byte 'h', 'e', 'l', 'l', 'o', '\0'。

hi code4food

thanks for your explanation, actually, I know C string need extra byte to hold the '\0' to indicated the end of string, but I don't expected some test cases of this problem the input number have 10^5 digits

And the description of the problem is not clear also. The author just state that

0 <= k <= n

It should be

0 <= k <= number of digit in n

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 Susan﹏汪汪於 2013-10-3 02:02 PM 发表
你系正常的向后扫..

定用binary search???

Hi Susan,

I just scan the input digits one by one from left to right and copy the suitable digits to another array. the loop may run k (the number of deleted digits) times or ended while meet the end of the input digits' array:

char t[MAX_DIGIT_LEN];
scanf("%s %d", n, &k);
...
t[0] = n[0];
i=1; j=0;

while(k && n != '\0') copy suitable digits from n to t
...

the function to find the maximum number just 20 lines and it got 0.22 second to complete this problem. I never think this problem in the way of using binary search, it may make the problem more complex and I am sure that whether it can improve the efficiency of the running time.

[ 本帖最后由 assembly.jc 於 2013-10-13 04:08 PM 编辑 ]

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 assembly.jc 於 2013-10-12 11:16 PM 发表
I don't expected some test cases of this problem the input number have 10^5 digits

玩SPOJ预左要handle boundary case是常识吧。

作者: code4food 发布时间: 2013-11-30

引用:原帖由 code4food 於 2013-10-13 04:20 PM 发表

玩SPOJ预左要handle boundary case是常识吧。

Actually this is the first problem I attempt to attack in SPOJ. and as you said that since I lack of "common sense of SPOJ", I submit more than 30 times to get the AC. Otherwise, I see your name in the rank of best solutions, Does you attempt to accelerate the program and make the running time within 0.1 second?

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 assembly.jc 於 2013-10-13 01:49 AM 发表
Actually this is the first problem I attempt to attack in SPOJ. and as you said that since I lack of "common sense of SPOJ", I submit more than 30 times to get the AC. Otherwise, I see your name in the rank of best solutions, Does you attempt to accelerate the program and make the running time within 0.1 second?

My first submission used a simple O(n * b) algorithm, where b is the base of the number system (b = 10 in this question). It was simple enough that I made no mistake in the 1st try. However, I was not particular happy with it and it was slow (~0.7s). So I optimized the algorithm to O(n) (i.e independent of the number system) to bring it down to 0.1 eventually.
Below is my submission history. I got one bad submission because of a server issue in SPOJ. Everybody failed during that time.
http://www.spoj.com/status/MAX_NUM,code4food/

作者: code4food 发布时间: 2013-11-30

引用:原帖由 code4food 於 2013-10-14 01:59 AM 发表

My first submission used a simple O(n * b) algorithm, where b is the base of the number system (b = 10 in this question). It was simple enough that I made no mistake in the 1st try. However, I was ...

great!

作者: ceap2003 发布时间: 2013-11-30

Hi code4food

0.1s is really fast!! but I found that If I just read the input data using scanf() and do nothing (just as the code as below), it spend 0.11 second (submit to SPOJ and of course got Wrong Ans). How can the program achieve the speed faster than 0.11s in C??

int main() {
int t, k;
char n[100001];

scanf("%d", &t);
while(t--) {
scanf("%s %d", n, &k);
printf("\n");
}

return(0);
}

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

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 assembly.jc 於 2013-10-19 06:54 PM 发表

Hi code4food

0.1s is really fast!! but I found that If I just read the input data using scanf() and do nothing (just as the code as below), it spend 0.11 second (submit to SPOJ and of course got ...

Try using fgets() to read each line instead, that was what I used. The total input size is about 100M, which is well within the limit of 256M. You can read the whole file once though I have not tried that. The trick is to reduce processing over data as much as possible.

作者: code4food 发布时间: 2013-11-30

引用:原帖由 code4food 於 2013-10-20 12:01 PM 发表

Try using fgets() to read each line instead, that was what I used. The total input size is about 100M, which is well within the limit of 256M. You can read the whole file once though I have not tr ...

Hi code4food

Thanks for your suggestion, I shall try it and wish one day can break the record (say 0.06s). In past week, I have tried other algorithms for this problem, but eventually cannot make the speed faster than of 0.21s.
I even thank it in the way of using Heap structure, but it seems not suitable to this problem, since if we read k digits and build the Heap, The complexity is O(k) and this same as just read k digits and each compare to the largest one. The point is that, If using Heap, the advantage is, once we extract the maximum digit from the Heap, The Heap can be reused to find another maximum digits (say the complexity is O(lg k)) . However, it is not true for this problem. Since the digits before (at the left side of) the extracted maximum digit must be deleted from the Heap. Otherwise, the Heap is invalid and cannot be reused. if we search such undesired digits and delete them in order to maintain a valid Heap, the complexity is no longer O(lg k)

For example : consider the number 4315123 and build the tree as

5
/ \
4 3
/ \ / \
3 1 1 2

and extract 5 from Heap, we have
4
/ \
3 3 / \ /
2 1 1
Then, the next extracted maximum digit is 4, but it it wrong, since 4 is at the left side of 5, the next maximum digit should be 2, that's 6th digit.

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 assembly.jc 於 2013-10-20 04:56 AM 发表

Hi code4food

Thanks for your suggestion, I shall try it and wish one day can break the record (say 0.06s). In past week, I have tried other algorithms for this problem, but eventually cannot make ...

A min-heap can be used but it is probably an over-kill. For a simpler approach, consider this: Suppose you have these number in a k=4 number window:

7, 5, 2, 1

If you append 4 into the list. 4 can "kill" all the numbers in front of it until it see something greater than or equal to 4. So this becomes

7 5, 2, 1, 4 red means deleted.

This way, each deletion is O(1). Once a number is deleted, you will not see it again. You can implement this easily using std::deque if you use C++. It is not difficult to implement something similar in C.

作者: code4food 发布时间: 2013-11-30

引用:原帖由 code4food 於 2013-10-21 04:00 AM 发表

A min-heap can be used but it is probably an over-kill. For a simpler approach, consider this: Suppose you have these number in a k=4 number window:

7, 5, 2, 1

If you append 4 into the list. ...

great!

作者: ceap2003 发布时间: 2013-11-30

hi code4food

I agree with you. Since the nature of this problem is simple, apply any data structure on it may make unnecessarily overhead. Actually, My original approach may same as what you said on previous post, but I am not familiar C++ and no any idea on the concept of queue, I just merely delete the digits that in front of the coming greater digit. I have tried several approach, but the original approach is the fastest so far.

In past weekend, I optimized the code and the running time dramatically be reduced from 0.21 to 0.08. It is concluded as below:

1. using fgets() instead of scanf() : time 0.21 -> 0.10 (around 0.13 to 0.10)

2. check k == number of digits in n before any process: time 0.10 -> 0.08 (around 0.11 to 0.08)

3. using fread() read whole input data instead of fgets() : no improvement

4. using pointer instead of array index scripting : no improvement (sometime worse than array scripting)

A point I want to point out is that, The test cases from SPOJ may be generated randomly each time submit the code, and so, the running time is different even thought submit the same code, but it seems not exceed the range from +0.03 to -0.03 second.

After playing with this problem for almost two weeks, I think I have found the best way to solve it, though I have not broken the record yet. The running time further be reduced from 0.08 to 0.06 seems may not related to the algorithm. It may be achieved by further optimization of IO or even using inline assembly, and that is no longer the purpose of this problem.

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

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 assembly.jc 於 2013-10-28 11:54 AM 发表
A point I want to point out is that, The test cases from SPOJ may be generated randomly each time submit the code, and so, the running time is different even thought submit the same code, but it seems not exceed the range from +0.03 to -0.03 second.

The differences of running time were due to the stability of the judge server. +/- 0.02s is quite common. You may get better running time when the server is idle.
The test cases for each problem are the same, though. Otherwise, it will not be fair.

BTW, you are a very dedicated person. Achieving 0.08s is amazing.

Now, would you try the problem LOPOV?

作者: fitcat07 发布时间: 2013-11-30

引用:原帖由 fitcat07 於 2013-10-28 12:07 PM 发表
The differences of running time were due to the stability of the judge server. +/- 0.02s is quite common. You may get better running time when the server is idle.
The test cases for each problem are ...

Hi fitcat07,

oic, thanks for your explanation

引用:Now, would you try the problem LOPOV?

Yes, of course, I may try it at weekend if I have time. At first glance, It seems not difficult

作者: assembly.jc 发布时间: 2013-11-30

引用:原帖由 assembly.jc 於 2013-10-28 12:59 PM 发表

oic, thanks for your explanation

You're welcome.

引用:Yes, of course, I may try it at weekend if I have time. At first glance, It seems not difficult

I had the same feeling as yours. Actually, it is 4-star class problem (5-star to be the most difficult). Although it is not difficult, it is surely not easy.

作者: fitcat07 发布时间: 2013-11-30

引用:原帖由 fitcat07 於 2013-10-28 04:46 PM 发表
You're welcome.

I had the same feeling as yours. Actually, it is 4-star class problem (5-star to be the most difficult). Although it is not difficult, it is surely not easy. :lovelin ...

Hi fitcat07,

Yes, you' re right, I just think it on the bus and unable to find a way to solve it so far

作者: assembly.jc 发布时间: 2013-11-30