当前位置：首页 → 问答吧 → 每周编程题：SPOJ NR2 （15/3/2014）

每周编程题：SPOJ NR2 （15/3/2014）

时间：2014-03-30

来源：互联网

之前有网友提议，周末搵条较浅嘅编程题目，等大家一齐玩。
今个周末，我搵到呢题畀大家：

http://www.spoj.com/problems/NR2/

因为输入数量好大，所以好有可能只得 C、C++ 或 Pascal 可以喺限时内做到。
Java 可能都得，但系我谂须要快速嘅输入方式。请参考以下连结：

http://stackoverflow.com/questions/14195351/reduce-program-runtime-in-java-making-a-code-faster

如果你识，请你暂时唔好贴上你嘅程式码，又或讲解点样做得到，以便其他人可以尝试。
过咗一星期后，就请随便。

作者: fitcat07 发布时间: 2014-03-30

有贴码的冲动

作者: form5 发布时间: 2014-03-30

引用:原帖由 form5 於 2014-3-15 08:36 PM 发表
有贴码的冲动

增加难度：
尝试加快速度，最快者系 0.46s，我就 0.51s，排第三。

作者: fitcat07 发布时间: 2014-03-30

引用:原帖由 fitcat07 於 2014-3-15 10:30 PM 发表

增加难度：
尝试加快速度，最快者系 0.46s，我就 0.51s，排第三。

Spoj fail to compile my C# code, their compiler might be too old to handle System.Numerics.BigInteger, I guess

作者: form5 发布时间: 2014-03-30

引用:原帖由 form5 於 2014-3-15 11:54 PM 发表

Spoj fail to compile my C# code, their compiler might be too old to handle System.Numerics.BigInteger, I guess

When you select C#, you can see the description: C# (gmcs 2.0.1). Yes, it's a very old one.

作者: fitcat07 发布时间: 2014-03-30

引用:原帖由 fitcat07 於 2014-3-15 04:46 PM 发表
之前有网友提议，周末搵条较浅嘅编程题目，等大家一齐玩。
今个周末，我搵到呢题畀大家：

http://www.spoj.com/problems/NR2/

因为输入数量好大，所以好有可能只得 C、C++ 或 Pascal 可以喺限时内 ...

Hi All,

这题目似乎不易 (至少对我来说

)，因为 input size 太大，N 有可能是 10^6, 即是说要 xor 10^6C2 (4.99e11) pair numbers，所以不可能直接运算吧，需要找到能简化以下算式的方法，right ?
K = (a1 ^ a2) | (a1 ^ a3) .....

另外，comments 里面所说的: "here input isn't terminated by a '\n', it's quite unusual"，对用普通的方法 handle input (I mean, use fgets() or scanf()) 有没有影响?

[ 本帖最后由 assembly.jc 於 2014-3-16 07:55 AM 编辑 ]

作者: assembly.jc 发布时间: 2014-03-30

引用:原帖由 assembly.jc 於 2014-3-16 07:53 AM 发表
这题目似乎不易 (至少对我来说

)，因为 input size 太大，N 有可能是 10^6, 即是说要 xor 10^6C2 (4.99e11) pair numbers，所以不可能直接运算吧，需要找到能简化以下算式的方法，right ?

全中。呢题系考大家对位元逻辑运算嘅能力。并只针对其中两种：互斥或同或。呢两种逻辑运算有乜嘢特性呢？

引用:另外，comments 里面所说的: "here input isn't terminated by a '\n', it's quite unusual"，对用普通的方法 handle input (I mean, use fgets() or scanf()) 有没有影响?

完全冇影响。佢咁讲系因为使用快捷输入方式时，可能要特别处理呢种情况。

作者: fitcat07 发布时间: 2014-03-30

引用:原帖由 fitcat07 於 2014-3-16 01:28 PM 发表
全中。呢题系考大家对位元逻辑运算嘅能力。并只针对其中两种：互斥或同或。呢两种逻辑运算有乜嘢特性呢？完全冇影响。佢咁讲系因为使用快捷输入方式时，可能要特别处理呢种情况。

呢题都叫简单
就算系大数字都好

Xor和or操作都好容易
唔似bit shift、数字加法、乘法咁要同时操作一列data

作者: Susan﹏汪汪发布时间: 2014-03-30

Hi all,

睇返一些简单 Boolean algebra theorems, 尝试简化题目的算式，可惜失败了，看来用纯数的方法是解决不了的，但也是预料之内，毕竟这不是数学问题。现在从 bit pattern 方向去想，因为是 combination 的关系，有很多以下的 pattern

(a1 ^ a2) | (a2 ^ a3)

如果限 ai 的值为 0<= ai <= 3，那么若 a1=1, a2=2, (a1 ^ a2) = 3, in binary is 11, 已经不需要理会 (a2 ^ a3)了...只是初步的构思。
p.s 我完全不知答案，以上说的不算是提示吧，仍在黑暗中摸索答案

and thanks fitcat answered my input problem

作者: assembly.jc 发布时间: 2014-03-30

方向啱...
进一步简化，设每个 ai 只可以 0 或 1，你能给出答案吗？

作者: fitcat07 发布时间: 2014-03-30

复制内容到剪贴板代码:given x, y, z
result = (x | y | z) ^ ( x & y &z)

作者: form5 发布时间: 2014-03-30

引用:原帖由 form5 於 2014-3-17 08:44 PM 发表
given x, y, z
result = (x | y | z) ^ ( x & y &z)

高手

作者: Susan﹏汪汪发布时间: 2014-03-30

咁快开估，重要系最佳（优化）答案...

就算开，都整个更直观嘛...

作者: fitcat07 发布时间: 2014-03-30

佢只gmcs 系神器，点run都系超时，己经除晒衫库都过吾到

作者: form5 发布时间: 2014-03-30

引用:原帖由於 2014-3-17 08:44 PM 发表
given x, y, z
result = (x | y | z) ^ ( x & y &z)

Hi form5,

That's great

, It is what I looking for yesterday but can't figure out anything.

[ 本帖最后由 assembly.jc 於 2014-3-18 05:06 AM 编辑 ]

作者: assembly.jc 发布时间: 2014-03-30

引用:原帖由 fitcat07 於 2014-3-17 09:41 PM 发表
都整个更直观嘛...

Hi fitcat,

That's enough, same truth table as (a1 ^ a2) | (a2 ^ a3). But Is it the optimized solution? need further simplification?

I mean that, via the formula provided by form5, we can combine two pair of number (say (a1, a2), (a2, a3)) into one expression. let we use (a1a2a3) to denote (a1 | a2 | a3) ^ (a1 & a2 & a3). Thus, the whole equation can be expressed as

(a1a2a3) | (a2a3a4) | ...

Does need to find a way to combine (a1a2a3) | (a2a3a4) ?

[ 本帖最后由 assembly.jc 於 2014-3-18 05:26 AM 编辑 ]

作者: assembly.jc 发布时间: 2014-03-30

I think you might misunderstood the solution given by form5.

For the time being, forget about that. Try to answer the question raised on my previous post (repeat here):

Suppose all ai are either 0 or 1, can we simplify the formula in this case?

作者: fitcat07 发布时间: 2014-03-30

引用:原帖由 fitcat07 於 2014-3-18 11:35 AM 发表
I think you might misunderstood the solution given by form5.

For the time being, forget about that. Try to answer the question raised on my previous post (repeat here):

Suppose all ai are either ...

Hi fitcat,

Ok, let us go back to the previous post, if all ai are either 0 or 1, then
(a1 ^ a2) | (a2 ^ a3) = 0 if and only if a1 = a2 = a3, otherwise, (a1 ^ a2) | (a2 ^ a3) = 1.

So, instead of binary operations, we just need to check whether all admin number ai are equal?

Besides, I can't figure out a simpler form of (a1 ^ a2) | (a2 ^ a3) after examining it's truth table

[ 本帖最后由 assembly.jc 於 2014-3-19 08:18 AM 编辑 ]

作者: assembly.jc 发布时间: 2014-03-30

引用:原帖由 assembly.jc 於 2014-3-19 08:17 AM 发表
(a1 ^ a2) | (a2 ^ a3) = 0 if and only if a1 = a2 = a3, otherwise, (a1 ^ a2) | (a2 ^ a3) = 1.

Exactly.

引用:So, instead of binary operations, we just need to check whether all admin number ai are equal?

You've just proved it yourself.

引用:Besides, I can't figure out a simpler form of (a1 ^ a2) | (a2 ^ a3) after examining it's truth table

Let A = a1 ^ a2 and B = a2 ^ a3.
Then, the truth table for A and B are:

复制内容到剪贴板代码:A:
a1 a2 a3 a1^a2
0 0 - 0
0 1 - 1
1 0 - 1
1 1 - 0

B:
a1 a2 a3 a2^a3
- 0 0 0
- 0 1 1
- 1 0 1
- 1 1 0

where - means don't care.

The truth table of A | B is then:

复制内容到剪贴板代码:A|B:

a1 a2 a3 A|B
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

From that, we can clearly see that A|B is 0 iff a1=a2=a3 and A|B is 1 otherwise.

[ 本帖最后由 fitcat07 於 2014-3-19 12:12 PM 编辑 ]

作者: fitcat07 发布时间: 2014-03-30

Now, you know the answer is 0 when all ai are equal and 1 otherwise. Then, what if ai now consists of 2 bits, ie, ai can be 00, 01, 10 or 11 in binary form? Finally, in general, what if ai consists of k bits for an integer k > 0?

作者: fitcat07 发布时间: 2014-03-30

引用:原帖由 fitcat07 於 2014-3-19 12:16 PM 发表
Now, you know the answer is 0 when all ai are equal and 1 otherwise. Then, what if ai now consists of 2 bits, ie, ai can be 00, 01, 10 or 11 in binary form? Finally, in general, what if ai consists of ...

Hi fitcat,

Thanks a lot! I got it! and now I know why from5's solution is optimized

[ 本帖最后由 assembly.jc 於 2014-3-20 07:03 AM 编辑 ]

作者: assembly.jc 发布时间: 2014-03-30

在解答这道题目的过程中，我又上了一课:方向比方法更重要

开始时，我用了大量时间希望利用 boolean algebra 去简化给定的算式，但「死做烂做」都是徒劳无功。因为方向错误了，结果反而愈走愈远。后来经 fitcat 的指点后回到正确的方向上，答案一下子就出来了。

这令我体会到，所谓难的问题，不是因为它极其复杂，而是因为很难发现能找到答题的方向。这令我想起费马大定理的证明故事，证明该定理的教授花了八年的时间去完成证明，而发现证明的方向是二个日本教授，但在这个方向发现之前，已花了三百多年的时间尝试不同的方向了。

作者: assembly.jc 发布时间: 2014-03-30

引用:原帖由 assembly.jc 於 2014-3-20 07:02 AM 发表
在解答这道题目的过程中，我又上了一课:方向比方法更重要

绝对赞同！