vi
发帖数: 309 | |
b*****e
发帖数: 474 | 2 Let me throw in some idea.
Since each diagonal separates a square into 2 triangles,
we can begin by assigning all triangles (for all squares)
a different color.
The problem is then a classical disjoint set problem - if two triangles
share an edge, they become the same color (i.e. the two disjoint
sets are merged). When the disjoint set algorithm finish, the sizes
of the sets is the area/2.
Of course, the outside box should be marked as a color, too. So we know the
set containing the outside is not enclosed and should be exclude.
【在 vi 的大作中提到】
: http://neil.fraser.name/news/2013/03/16/
|
b***n
发帖数: 590 | 3
the
An 11th grade student is supposed to be able to work out and
implement a solution in 45 minutes in PASCAL. Therefore, it
got to be a 'simple' solution.
【在 b*****e 的大作中提到】
: Let me throw in some idea.
: Since each diagonal separates a square into 2 triangles,
: we can begin by assigning all triangles (for all squares)
: a different color.
: The problem is then a classical disjoint set problem - if two triangles
: share an edge, they become the same color (i.e. the two disjoint
: sets are merged). When the disjoint set algorithm finish, the sizes
: of the sets is the area/2.
: Of course, the outside box should be marked as a color, too. So we know the
: set containing the outside is not enclosed and should be exclude.
|
b*****e
发帖数: 474 | 4 The details:
A[i][j] == 0 means \ (i.e. left triangle\right triangle)
A[i][j] == 1 means / (i.e. left /right )
Given A[0..N-1][0..M-1],
Between A[i][j] and A[i+1][j],
triangle (i,j,right) is connected to (i+1,j,left)
Between A[i][j] and A[i][j+1],
(A[i][j]==0) ? (i,j,left) : (i,j,right )
is connected to
(A[i][j+1]==0) ? (i,j+1,right) : (i,j+1,left)
The outside box is connected to
all (0,j,left)
and all (N-1,j,right)
and all (A[i][0]==0)? (i,0,right) : (i,0,left)
and all (A[i][M-1]==0) ? (i,M-1,left) : (i,M-1,right)
The rest would be standard union-find algorithm for disjoint sets. |
b*****e
发帖数: 474 | 5 The "outside" part could be dropped since it's easy to tell
that a triangle with a border edge is in open area. That would
simplify things down quite a bit.
But, 45 minutes in class? I don't think many of my students (typical CS
undergrads) can do it without some serious help.
【在 b*****e 的大作中提到】
: The details:
: A[i][j] == 0 means \ (i.e. left triangle\right triangle)
: A[i][j] == 1 means / (i.e. left /right )
: Given A[0..N-1][0..M-1],
: Between A[i][j] and A[i+1][j],
: triangle (i,j,right) is connected to (i+1,j,left)
: Between A[i][j] and A[i][j+1],
: (A[i][j]==0) ? (i,j,left) : (i,j,right )
: is connected to
: (A[i][j+1]==0) ? (i,j+1,right) : (i,j+1,left)
|
b***n
发帖数: 590 | 6
Did you read the data file? From the data file, it's not
immediately clear about the triangle stuff, ex the size
of a unit square.
【在 b*****e 的大作中提到】
: The details:
: A[i][j] == 0 means \ (i.e. left triangle\right triangle)
: A[i][j] == 1 means / (i.e. left /right )
: Given A[0..N-1][0..M-1],
: Between A[i][j] and A[i+1][j],
: triangle (i,j,right) is connected to (i+1,j,left)
: Between A[i][j] and A[i][j+1],
: (A[i][j]==0) ? (i,j,left) : (i,j,right )
: is connected to
: (A[i][j+1]==0) ? (i,j+1,right) : (i,j+1,left)
|
c****p
发帖数: 6474 | 7 这个问题不是在google面试题里排第三么？
【在 b***n 的大作中提到】
:
: Did you read the data file? From the data file, it's not
: immediately clear about the triangle stuff, ex the size
: of a unit square.
|
d***a
发帖数: 13752 | 8 这问题不复杂，用一个O(N^3)的算法可以解出来...不知道是不是复杂度最优。 |
a*****e
发帖数: 1700 | 9 从这个 data file 看，就是个 raster image color filling 的问题，暴力解决很简
单，时间效率就是 O(n)
【在 b***n 的大作中提到】
:
: Did you read the data file? From the data file, it's not
: immediately clear about the triangle stuff, ex the size
: of a unit square.
|
vi
发帖数: 309 | 10
请老兄花半个小时暴力一把。
我看不出怎样暴力。
【在 a*****e 的大作中提到】
: 从这个 data file 看，就是个 raster image color filling 的问题，暴力解决很简
: 单，时间效率就是 O(n)
|
|
|
b*****e
发帖数: 474 | 11 What's raster image color filling problem? Can you provide a link pls.
Union/find is amortized linear time, and that's hard to beat already.
【在 a*****e 的大作中提到】
: 从这个 data file 看，就是个 raster image color filling 的问题，暴力解决很简
: 单，时间效率就是 O(n)
|
a*****e
发帖数: 1700 | 12 http://en.wikipedia.org/wiki/Flood_fill
【在 b*****e 的大作中提到】
: What's raster image color filling problem? Can you provide a link pls.
: Union/find is amortized linear time, and that's hard to beat already.
|
b*****e
发帖数: 474 | 13 Thx. Makes perfect sense. Using graph search is another natural way of
solving disjoint set problems
【在 a*****e 的大作中提到】
: http://en.wikipedia.org/wiki/Flood_fill
|
s*****V
发帖数: 21731 | 14 他没说都能用计算机解吧，GRADE11也太难了
【在 b***n 的大作中提到】
:
: Did you read the data file? From the data file, it's not
: immediately clear about the triangle stuff, ex the size
: of a unit square.
|
a*****e
发帖数: 1700 | 15 午饭前闲着也是闲着，写了个 Haskell 程序：
http://pastie.org/7093065
主体算法就是两个函数。
fill 是从一个点开始递归填色，如成功则返回结果地图，如此点不为空，则返回
Nothing。
fill :: Color -> Map -> Pos -> Maybe Map
fill c m p = guard (readColor m p == 0) >>
return (foldl (fill' c) (setColor m p c) (neighbor m p))
where fill' c m = maybe m id . fill c m
fillAll 对地图扫描，对每个点填色，如果填色成功，颜色要递增。
fillAll :: Map -> Map
fillAll m = fst $ foldl aux (m, 2) (indices m)
where aux (m, c) = maybe (m, c) (\m -> (m, c+1)) . fill c m
使用原题的数据文件 http://neil.fraser.name/news/2013/cs-vn/data.txt 运行结果如下：
15555555122218881;;;;;;;1
215555512221618881;;;;;1<
2215551222166618881;;;1<<
22215122216666618881;1<<<
122212221666166618881<<<<
3122222166616661918881<<<
33122216661666199918881<<
333121666166619999918881<
3333166616661999999918881
33316661616661999991:1888
3316661666166619991:::188
316661666661666191:::::18
16661666166616661:::1:::1
4166666171666661:::1:::1=
441666177716661:::1:::1==
44416177777161:::1:::1===
4444177777771:::1:::1====
Color 6 96
Color 9 25
假设 n 是数据文件的长度，因为每个点访问的次数与 n 无关，所以时间空间复杂度均
为 O(n)。
【在 vi 的大作中提到】
:
: 请老兄花半个小时暴力一把。
: 我看不出怎样暴力。
|
r***e
发帖数: 2000 | 16 你这个不是解。原题是求面积。
96个零很容易数出来，但是换成面积就复杂多了。
这个思路不对，还是最上面找三角的靠谱，
但是前面把原始数据转换成斜杠的一步似乎不方便。
【在 a*****e 的大作中提到】
: 午饭前闲着也是闲着，写了个 Haskell 程序：
: http://pastie.org/7093065
: 主体算法就是两个函数。
: fill 是从一个点开始递归填色，如成功则返回结果地图，如此点不为空，则返回
: Nothing。
: fill :: Color -> Map -> Pos -> Maybe Map
: fill c m p = guard (readColor m p == 0) >>
: return (foldl (fill' c) (setColor m p c) (neighbor m p))
: where fill' c m = maybe m id . fill c m
: fillAll 对地图扫描，对每个点填色，如果填色成功，颜色要递增。
|
r***e
发帖数: 2000 | 17
用PASCAL，从拿到题到找出解，一个班大多数都可以在45分钟以内完成。
【在 s*****V 的大作中提到】
: 他没说都能用计算机解吧，GRADE11也太难了
|
s*****V
发帖数: 21731 | 18 这肯定不是越南的普通班级吧，如果是什么理科实验班的，专门搞信息竞赛的应该不成
啥问题。
【在 r***e 的大作中提到】
:
: 用PASCAL，从拿到题到找出解，一个班大多数都可以在45分钟以内完成。
|
r***e
发帖数: 2000 | 19
就是普通班，博客作者是Google负责教育的联系员，专门到越南调查的。
CS老师一个月工资只有$100，他还捐了一年的工资。
越南全民从小学二年级开始学CS，四年级开始编程。
博客中和美国加州数理天才班的水平做了对比。
【在 s*****V 的大作中提到】
: 这肯定不是越南的普通班级吧，如果是什么理科实验班的，专门搞信息竞赛的应该不成
: 啥问题。
|
s*****V
发帖数: 21731 | 20 I don't believe, 你知道我们当年在高中以后到了省重点中学才能学计算机。越南比
中国经济要差很多，中国都做不到小学开始学计算机，越南有这个条件么？
【在 r***e 的大作中提到】
:
: 就是普通班，博客作者是Google负责教育的联系员，专门到越南调查的。
: CS老师一个月工资只有$100，他还捐了一年的工资。
: 越南全民从小学二年级开始学CS，四年级开始编程。
: 博客中和美国加州数理天才班的水平做了对比。
|
|
|
r***e
发帖数: 2000 | 21
您读英文吗？最上面是链接。
【在 s*****V 的大作中提到】
: I don't believe, 你知道我们当年在高中以后到了省重点中学才能学计算机。越南比
: 中国经济要差很多，中国都做不到小学开始学计算机，越南有这个条件么？
|
a*****e
发帖数: 1700 | 22 从数据文件就直接能够看出来是考递归的题，你也不要把问题想太复杂了。
毕竟是给高中生做的题，我那么大的时候 Pascal 很熟练，类似的算法也
实现过，做这个题绝对有把握。
退一万步讲，你要求的面积也是和数出来的零成正比，又有何不可呢？
【在 r***e 的大作中提到】
: 你这个不是解。原题是求面积。
: 96个零很容易数出来，但是换成面积就复杂多了。
: 这个思路不对，还是最上面找三角的靠谱，
: 但是前面把原始数据转换成斜杠的一步似乎不方便。
|
r***e
发帖数: 2000 | 23
题目上英文和越南话都写了，最后的结果是8（面积）。
你那个算法后面肯定走不通。
人家问的是北京到上海有多少里地，你回答坐火车27站，然后解释
你的答案和要求的答案数值上成正比？
【在 a*****e 的大作中提到】
: 从数据文件就直接能够看出来是考递归的题，你也不要把问题想太复杂了。
: 毕竟是给高中生做的题，我那么大的时候 Pascal 很熟练，类似的算法也
: 实现过，做这个题绝对有把握。
: 退一万步讲，你要求的面积也是和数出来的零成正比，又有何不可呢？
|
s*****V
发帖数: 21731 | 24 链接怎么样，他也不过是去越南看几天，就能知道全貌？还不是越南当地官员带他看几
个牛逼的学校。
【在 r***e 的大作中提到】
:
: 题目上英文和越南话都写了，最后的结果是8（面积）。
: 你那个算法后面肯定走不通。
: 人家问的是北京到上海有多少里地，你回答坐火车27站，然后解释
: 你的答案和要求的答案数值上成正比？
|
r***e
发帖数: 2000 | 25
您有时间灌水，倒是没有时间读一下原文，总共没有多少字。
越南官方不允许参观学校的。
这位老兄凭着一张西方面孔，一张Google名片，自己随机找学校往里闯。
【在 s*****V 的大作中提到】
: 链接怎么样，他也不过是去越南看几天，就能知道全貌？还不是越南当地官员带他看几
: 个牛逼的学校。
|
s*****V
发帖数: 21731 | 26 没你们想的那么难吧，
1.先判断是不是闭合的。
2.如果闭合，一行行扫描，从第一列有MAZE的开始，有MAZE的算1/2.
没MAZE算1，到最后一个有MAZE的结束。 有闭合区域的MAZE数目都是偶数个。
【在 r***e 的大作中提到】
:
: 您有时间灌水，倒是没有时间读一下原文，总共没有多少字。
: 越南官方不允许参观学校的。
: 这位老兄凭着一张西方面孔，一张Google名片，自己随机找学校往里闯。
|
s*****V
发帖数: 21731 | 27 你可以动脑子想一想就是了，Is it possible? 这边专业码农都要花很多时间争论，越
南随便一个高中班级全班都能SOLVE?
【在 r***e 的大作中提到】
:
: 您有时间灌水，倒是没有时间读一下原文，总共没有多少字。
: 越南官方不允许参观学校的。
: 这位老兄凭着一张西方面孔，一张Google名片，自己随机找学校往里闯。
|
r***e
发帖数: 2000 | 28
逻辑题啊！
你用了一个隐含前提就是专业码农的智力水平不低于大众平均智力水平。
For the sake of argument, 有些专业码农是别的工作做不了或者做不下去
才不得不做码农的。
【在 s*****V 的大作中提到】
: 你可以动脑子想一想就是了，Is it possible? 这边专业码农都要花很多时间争论，越
: 南随便一个高中班级全班都能SOLVE?
|
a*****e
发帖数: 1700 | 29 你难道看不出来是成比例的吗？
较这个劲没意思，我的结果 (96/12, 25/12) 略有出入是因为原数据的格式不是正好
4x4 一格，如果处理一下 (drop every 5th column) 就正常了。
【在 r***e 的大作中提到】
:
: 逻辑题啊！
: 你用了一个隐含前提就是专业码农的智力水平不低于大众平均智力水平。
: For the sake of argument, 有些专业码农是别的工作做不了或者做不下去
: 才不得不做码农的。
|
r***e
发帖数: 2000 | 30
中间有间断线的情况呢？不是那么简单。
【在 a*****e 的大作中提到】
: 你难道看不出来是成比例的吗？
: 较这个劲没意思，我的结果 (96/12, 25/12) 略有出入是因为原数据的格式不是正好
: 4x4 一格，如果处理一下 (drop every 5th column) 就正常了。
|
|
|
a*****e
发帖数: 1700 | 31 你这个说的对，给的数据是 25x17，但是图上画出来 6x4，硬要扣题则需要自己提供正
确数据。比如 2x2 表示每一格。
10 表示 \
01
01 表示 /
10
总的来说，编程题考的是算法和思路，这个对了就行了。
【在 r***e 的大作中提到】
:
: 中间有间断线的情况呢？不是那么简单。
|
d***a
发帖数: 13752 | 32 赞实证。
用原题的notation，复杂度是O(M*N)吧。也可以说是O(N^2)，假设M<=N。
...
【在 a*****e 的大作中提到】
: 午饭前闲着也是闲着，写了个 Haskell 程序：
: http://pastie.org/7093065
: 主体算法就是两个函数。
: fill 是从一个点开始递归填色，如成功则返回结果地图，如此点不为空，则返回
: Nothing。
: fill :: Color -> Map -> Pos -> Maybe Map
: fill c m p = guard (readColor m p == 0) >>
: return (foldl (fill' c) (setColor m p c) (neighbor m p))
: where fill' c m = maybe m id . fill c m
: fillAll 对地图扫描，对每个点填色，如果填色成功，颜色要递增。
|
b*****n
发帖数: 482 | 33 这题不就是uva 705么。从maze建matrix要稍微转个弯，然后一个简单的dfs就搞定了。
这应该算是国内搞OI和ACM都会做的基础练习。越南这个如果就是随便一个普通高中的
话，还是挺有实力的。
【在 vi 的大作中提到】
: http://neil.fraser.name/news/2013/03/16/
|
r***e
发帖数: 2000 | 34
xiexie!
我还是观察不细致，没有看出来是迷宫。
既然是迷宫，就不需要dfs，主要keep making left turns就可以了。
uva是个什么东西？为什么这么有名？
【在 b*****n 的大作中提到】
: 这题不就是uva 705么。从maze建matrix要稍微转个弯，然后一个简单的dfs就搞定了。
: 这应该算是国内搞OI和ACM都会做的基础练习。越南这个如果就是随便一个普通高中的
: 话，还是挺有实力的。
|
b*****n
发帖数: 482 | 35 google uva online judge 705. 题目就叫slash maze. 写完code自己submit 一下就行
了。
【在 r***e 的大作中提到】
:
: xiexie!
: 我还是观察不细致，没有看出来是迷宫。
: 既然是迷宫，就不需要dfs，主要keep making left turns就可以了。
: uva是个什么东西？为什么这么有名？
|
