Mathematical idea regarding solving “Not So Random” question asked in Google APAC Test 2015 Round E
up vote
2
down vote
favorite
I am trying to solve the Problem C titled "Not So Random" asked in Round E of Google APAC 2015 test (Link: https://code.google.com/codejam/contest/8264486/dashboard#s=p2). Following is the question:
My initial idea was to try to formulate a recursive equation for calculating the Expectation of a bit $i$ produced by an $n^{th}$ machine (denoted by $E[f^{n}(i)]$) given $f^{n-1}(i)$ and $k(i)$ ($i^{th}$ bit of $k$). The following is an equation I came up with (I am not completely sure about the correctness):
$E[f^{n}(i)] = frac{(B+C)}{100}*(f^{n-1}(i)oplus k(i)) + frac{(A+B)}{100}*(neg (f^{n-1}(i) oplus k(i)) ominus k(i))$
, where $oplus$ denotes the bitwise $XOR$ operation and $ominus$ denotes the bitwise $AND$ operation.
The thing is I do not how to proceed from there. Some solutions to this are available online: http://massivealgorithms.blogspot.com/2016/07/not-so-random-round-e-apac-test-of.html and https://stackoverflow.com/questions/39430741/logic-behind-codejam-apac-practice-round-not-so-random, but they do not give a properly explained mathematical answer.
(I do not need the code -- I can type it down on my own. Some proper mathematical idea and pointers in the right direction will help)
algorithms random-variables
asked Nov 8 at 9:12
Python_user
936
This question has an open bounty worth +50
reputation from Python_user ending in 6 days.
This question has not received enough attention.
Hi! I need a really good explanation for this solution. I have been working on this for quite some time, but unable to get some proper answer.
add a comment |
up vote
2
down vote
favorite
I am trying to solve the Problem C titled "Not So Random" asked in Round E of Google APAC 2015 test (Link: https://code.google.com/codejam/contest/8264486/dashboard#s=p2). Following is the question:
My initial idea was to try to formulate a recursive equation for calculating the Expectation of a bit $i$ produced by an $n^{th}$ machine (denoted by $E[f^{n}(i)]$) given $f^{n-1}(i)$ and $k(i)$ ($i^{th}$ bit of $k$). The following is an equation I came up with (I am not completely sure about the correctness):
$E[f^{n}(i)] = frac{(B+C)}{100}*(f^{n-1}(i)oplus k(i)) + frac{(A+B)}{100}*(neg (f^{n-1}(i) oplus k(i)) ominus k(i))$
, where $oplus$ denotes the bitwise $XOR$ operation and $ominus$ denotes the bitwise $AND$ operation.
The thing is I do not how to proceed from there. Some solutions to this are available online: http://massivealgorithms.blogspot.com/2016/07/not-so-random-round-e-apac-test-of.html and https://stackoverflow.com/questions/39430741/logic-behind-codejam-apac-practice-round-not-so-random, but they do not give a properly explained mathematical answer.
(I do not need the code -- I can type it down on my own. Some proper mathematical idea and pointers in the right direction will help)
algorithms random-variables
asked Nov 8 at 9:12
Python_user
936
This question has an open bounty worth +50
reputation from Python_user ending in 6 days.
This question has not received enough attention.
Hi! I need a really good explanation for this solution. I have been working on this for quite some time, but unable to get some proper answer.
It's premature to try to find the expectation right away before understanding the structure of the problem. Consider: in the beginning you have one possible value, $X$. After going through one machine, you have three possible values: $Xwedge K$, $Xvee K$, $Xoplus K$. After two machines, you have nine possible values... or do you? Do some of those turn out to be the same as each other, or to values you've seen before? Try drawing out the possibilities as though it's the transition graph of a state machine.
– Rahul
yesterday
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am trying to solve the Problem C titled "Not So Random" asked in Round E of Google APAC 2015 test (Link: https://code.google.com/codejam/contest/8264486/dashboard#s=p2). Following is the question:
My initial idea was to try to formulate a recursive equation for calculating the Expectation of a bit $i$ produced by an $n^{th}$ machine (denoted by $E[f^{n}(i)]$) given $f^{n-1}(i)$ and $k(i)$ ($i^{th}$ bit of $k$). The following is an equation I came up with (I am not completely sure about the correctness):
$E[f^{n}(i)] = frac{(B+C)}{100}*(f^{n-1}(i)oplus k(i)) + frac{(A+B)}{100}*(neg (f^{n-1}(i) oplus k(i)) ominus k(i))$
, where $oplus$ denotes the bitwise $XOR$ operation and $ominus$ denotes the bitwise $AND$ operation.
The thing is I do not how to proceed from there. Some solutions to this are available online: http://massivealgorithms.blogspot.com/2016/07/not-so-random-round-e-apac-test-of.html and https://stackoverflow.com/questions/39430741/logic-behind-codejam-apac-practice-round-not-so-random, but they do not give a properly explained mathematical answer.
(I do not need the code -- I can type it down on my own. Some proper mathematical idea and pointers in the right direction will help)
algorithms random-variables
asked Nov 8 at 9:12
Python_user
936
I am trying to solve the Problem C titled "Not So Random" asked in Round E of Google APAC 2015 test (Link: https://code.google.com/codejam/contest/8264486/dashboard#s=p2). Following is the question:
My initial idea was to try to formulate a recursive equation for calculating the Expectation of a bit $i$ produced by an $n^{th}$ machine (denoted by $E[f^{n}(i)]$) given $f^{n-1}(i)$ and $k(i)$ ($i^{th}$ bit of $k$). The following is an equation I came up with (I am not completely sure about the correctness):
$E[f^{n}(i)] = frac{(B+C)}{100}*(f^{n-1}(i)oplus k(i)) + frac{(A+B)}{100}*(neg (f^{n-1}(i) oplus k(i)) ominus k(i))$
, where $oplus$ denotes the bitwise $XOR$ operation and $ominus$ denotes the bitwise $AND$ operation.
The thing is I do not how to proceed from there. Some solutions to this are available online: http://massivealgorithms.blogspot.com/2016/07/not-so-random-round-e-apac-test-of.html and https://stackoverflow.com/questions/39430741/logic-behind-codejam-apac-practice-round-not-so-random, but they do not give a properly explained mathematical answer.
(I do not need the code -- I can type it down on my own. Some proper mathematical idea and pointers in the right direction will help)
algorithms random-variables
algorithms random-variables
asked Nov 8 at 9:12
Python_user
936
asked Nov 8 at 9:12
Python_user
936
asked Nov 8 at 9:12
Python_user
936
asked Nov 8 at 9:12
Python_user
936
asked Nov 8 at 9:12
Python_user
936
936
This question has an open bounty worth +50
reputation from Python_user ending in 6 days.
This question has not received enough attention.
Hi! I need a really good explanation for this solution. I have been working on this for quite some time, but unable to get some proper answer.
This question has an open bounty worth +50
reputation from Python_user ending in 6 days.
This question has not received enough attention.
Hi! I need a really good explanation for this solution. I have been working on this for quite some time, but unable to get some proper answer.
It's premature to try to find the expectation right away before understanding the structure of the problem. Consider: in the beginning you have one possible value, $X$. After going through one machine, you have three possible values: $Xwedge K$, $Xvee K$, $Xoplus K$. After two machines, you have nine possible values... or do you? Do some of those turn out to be the same as each other, or to values you've seen before? Try drawing out the possibilities as though it's the transition graph of a state machine.
– Rahul
yesterday
add a comment |
It's premature to try to find the expectation right away before understanding the structure of the problem. Consider: in the beginning you have one possible value, $X$. After going through one machine, you have three possible values: $Xwedge K$, $Xvee K$, $Xoplus K$. After two machines, you have nine possible values... or do you? Do some of those turn out to be the same as each other, or to values you've seen before? Try drawing out the possibilities as though it's the transition graph of a state machine.
– Rahul
yesterday
It's premature to try to find the expectation right away before understanding the structure of the problem. Consider: in the beginning you have one possible value, $X$. After going through one machine, you have three possible values: $Xwedge K$, $Xvee K$, $Xoplus K$. After two machines, you have nine possible values... or do you? Do some of those turn out to be the same as each other, or to values you've seen before? Try drawing out the possibilities as though it's the transition graph of a state machine.
– Rahul
yesterday
It's premature to try to find the expectation right away before understanding the structure of the problem. Consider: in the beginning you have one possible value, $X$. After going through one machine, you have three possible values: $Xwedge K$, $Xvee K$, $Xoplus K$. After two machines, you have nine possible values... or do you? Do some of those turn out to be the same as each other, or to values you've seen before? Try drawing out the possibilities as though it's the transition graph of a state machine.
– Rahul
yesterday
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2989719%2fmathematical-idea-regarding-solving-not-so-random-question-asked-in-google-apa%23new-answer', 'question_page');
}
);
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
It's premature to try to find the expectation right away before understanding the structure of the problem. Consider: in the beginning you have one possible value, $X$. After going through one machine, you have three possible values: $Xwedge K$, $Xvee K$, $Xoplus K$. After two machines, you have nine possible values... or do you? Do some of those turn out to be the same as each other, or to values you've seen before? Try drawing out the possibilities as though it's the transition graph of a state machine.
– Rahul
yesterday