l****2
发帖数: 7 | 1 发个帖，咱齐心协力把这几道题拿下~~
6.N people in the room, A is a matrix, A_ij=0 means i-th person knows j-th
person, and A is not symmetric. There is one celebrity in the room,
everybody knows him and he know nobody(like Obama), how to find this person
efficientely?(In O(n) time)
7.Three nine digits number e,f,and g. If we replace f_i with e_i they the
new nine digites can be divided by 7, for all i. Same happens if we replace
g_i with f_i,prove that g_i-e_i==0 mod 7 for all i.
9.x,y independent uniform distribution on [0,1], calculate p(x*y<0.5)
10.Three R.Vs,x,y,z, can they be negatively correlated pairwise? | m*********g
发帖数: 646 | 2 for 6,how about: find_max(sum( rows )-sum(columns))
for 9, 0.5+0.5ln(2) - corrected...
for 10, yes, [-0.5~1] | t*******y
发帖数: 637 | 3 how about 8?
8.I know Ben have Two kids, and I know one is boy and is born on Tuesday,
what is the probability that he has two boys?(Answer:13/27)
I didn't get 13/27 here
person
replace
【在 l****2 的大作中提到】
: 发个帖，咱齐心协力把这几道题拿下~~
: 6.N people in the room, A is a matrix, A_ij=0 means i-th person knows j-th
: person, and A is not symmetric. There is one celebrity in the room,
: everybody knows him and he know nobody(like Obama), how to find this person
: efficientely?(In O(n) time)
: 7.Three nine digits number e,f,and g. If we replace f_i with e_i they the
: new nine digites can be divided by 7, for all i. Same happens if we replace
: g_i with f_i,prove that g_i-e_i==0 mod 7 for all i.
: 9.x,y independent uniform distribution on [0,1], calculate p(x*y<0.5)
: 10.Three R.Vs,x,y,z, can they be negatively correlated pairwise?
| t*******y
发帖数: 637 | 4 for 9 i get 0.5-0.5ln(0.5)
【在 m*********g 的大作中提到】
: for 6,how about: find_max(sum( rows )-sum(columns))
: for 9, 0.5+0.5ln(2) - corrected...
: for 10, yes, [-0.5~1]
| a***u
发帖数: 67 | 5 list all of then
there is a cose when both of them are boys who born on Tuesday
【在 t*******y 的大作中提到】
: how about 8?
: 8.I know Ben have Two kids, and I know one is boy and is born on Tuesday,
: what is the probability that he has two boys?(Answer:13/27)
: I didn't get 13/27 here
:
: person
: replace
| t*******y
发帖数: 637 | 6 for no 6
can we check each diagonal element, if we find its four neighbours are 0,0,1
,1 then we find it? not sure though | m*********g
发帖数: 646 | 7 you are right. Some how, I firstly took it as a quarter - circle...
【在 t*******y 的大作中提到】
: for 9 i get 0.5-0.5ln(0.5)
| t*******y
发帖数: 637 | 8 thanks
it's much clearer to list all cases
【在 a***u 的大作中提到】
: list all of then
: there is a cose when both of them are boys who born on Tuesday
| p******5
发帖数: 138 | 9 第六题，不像算法题，更好brainteaser题
先check a_{1, N}, 如果a_{1,N} 是 0， 去掉第一行，和 第一列，应为不可能是 1号
， 如果a_{1, N} 是 1， 去掉 最后列 和 最好行，因为不可能是 N 号， 如此下去，
只要扫描第一行就搞定了 | m*********g
发帖数: 646 | 10 you mean for (i,i) check (i-1,i); (i+1, i); (i,i-1);(i,i+1)?
Well, I don't think so. This could only find one knows nothing about his
neighbors, but is known by his neighbors. Nothing guaranteed for the people
other than the one's neighbors.
,1
【在 t*******y 的大作中提到】
: for no 6
: can we check each diagonal element, if we find its four neighbours are 0,0,1
: ,1 then we find it? not sure though
| | | p******5
发帖数: 138 | 11 第10题，of course, 平面三个向量可能互相成 120 度角 | m*********g
发帖数: 646 | 12 p(two boys| {that boy on Tue| there is a boy| two kids} )
= (1/2)*(1/2)*[1-(6/7)*(6/7)]/ p(that boy on Tue|one is boy|two kids)
p(that boy on Tue|one is boy|two kids)
=p(only one boy, that boy on tue)+p(two boys, at least one on Tue)
=1/2 * 1/7+1/4 * 13/49= 27/(4*49)
p_desired=13/(4*49) / 27/(4*49) = 13/27
【在 t*******y 的大作中提到】
: how about 8?
: 8.I know Ben have Two kids, and I know one is boy and is born on Tuesday,
: what is the probability that he has two boys?(Answer:13/27)
: I didn't get 13/27 here
:
: person
: replace
| T*******r
发帖数: 30 | 13 第7题有个笨办法，希望抛砖引玉吧
以下的式子都模7,记f=f_9f_8...f_1，e,g同
f=f_9*10^8+f_8*10^7+...+f_1=e_9*10^8+f_8*10^7+...+f_1+10^8(f_9-e_9)
=10^8(f_9-e_9)=10^7(f_8-e_8)=...=f_1-e_1
则将后九项相加，我们有
9f=f-e， 即f+e=0
同理
g=10^8(g_9-f_9)=10^7(g_8-f_8)=...=g_1-f_1
和
g+f=0
现在 10^8(g_9-e_9)=10^8(f_9-e^9)+10^8(g_9-f_9)=f+g=0
其余相同
j-th
person
the
replace
【在 l****2 的大作中提到】
: 发个帖，咱齐心协力把这几道题拿下~~
: 6.N people in the room, A is a matrix, A_ij=0 means i-th person knows j-th
: person, and A is not symmetric. There is one celebrity in the room,
: everybody knows him and he know nobody(like Obama), how to find this person
: efficientely?(In O(n) time)
: 7.Three nine digits number e,f,and g. If we replace f_i with e_i they the
: new nine digites can be divided by 7, for all i. Same happens if we replace
: g_i with f_i,prove that g_i-e_i==0 mod 7 for all i.
: 9.x,y independent uniform distribution on [0,1], calculate p(x*y<0.5)
: 10.Three R.Vs,x,y,z, can they be negatively correlated pairwise?
| l*********t
发帖数: 89 | 14 感觉找max要慢些。
那个名人列全为0，行除了对角元素其他全为1，所以
find([行sum(i)-列sum(i)]=N-1), i为对角线上第i个元素。
不过不知道这样咋就 ln O(N) 呢？
还有，第7题能不能用上费马小定理啥的？
【在 m*********g 的大作中提到】
: for 6,how about: find_max(sum( rows )-sum(columns))
: for 9, 0.5+0.5ln(2) - corrected...
: for 10, yes, [-0.5~1]
| t*******y
发帖数: 637 | 15 这个算法是O(n^2)的吧
【在 l*********t 的大作中提到】
: 感觉找max要慢些。
: 那个名人列全为0，行除了对角元素其他全为1，所以
: find([行sum(i)-列sum(i)]=N-1), i为对角线上第i个元素。
: 不过不知道这样咋就 ln O(N) 呢？
: 还有，第7题能不能用上费马小定理啥的？
| m*******d
发帖数: 9 | 16 第六题，检查A_ij：若A_ij=0，即i认识j，说明i不是名人；若A_ij~=0，即i不认识j，
说明j不是名人。无论哪种情况都可以否定掉一个人
每次在没有被否定的人群中取i，j，可以新否定一个人，否定N-1次，剩下的那个就是
名人
person
replace
【在 l****2 的大作中提到】
: 发个帖，咱齐心协力把这几道题拿下~~
: 6.N people in the room, A is a matrix, A_ij=0 means i-th person knows j-th
: person, and A is not symmetric. There is one celebrity in the room,
: everybody knows him and he know nobody(like Obama), how to find this person
: efficientely?(In O(n) time)
: 7.Three nine digits number e,f,and g. If we replace f_i with e_i they the
: new nine digites can be divided by 7, for all i. Same happens if we replace
: g_i with f_i,prove that g_i-e_i==0 mod 7 for all i.
: 9.x,y independent uniform distribution on [0,1], calculate p(x*y<0.5)
: 10.Three R.Vs,x,y,z, can they be negatively correlated pairwise?
|
|
