March 9, 2019 SRM 752 Editorial
Poker Round
Solution:
Let us see what happens after one round if they had 10000-x and x initially.
After 1 round, it becomes 2*(10000-x) and 2*x-10000.
Lets assume second player had z after first round.
Then z=2*x-10000, i.e x= (z+10000)/2
So now we can try to go 1 step back at a time for 3 times to reach initial amounts. If the final amount is not an integer then answer is -1.
Code:
public int getamt(int t,int left){
if(left==0){
return t;
}
if(t%2==1){
return -1;
}
return getamt(t+(10000-t)/2,left-1);
}
public int amount(int T){
return getamt(T,3);
}Time complexity:
To move back each round, it takes O(1) time because we are simply evaluating a formula. To move back 3 rounds, it takes O(1) operations.
Literature Optimal
Solution:
Teja understands everyones cards if and only if at least one of Vinay or Sohail calls out the cards of the other person.
Proof:
Backward direction is trivial because when a person(say Vinay) calls out all the cards of other person(say Sohail). He knows all the cards of Sohail. He also knows his cards. So he can deduce the set of Vinay. Hence, Teja knows exact distribution of all the cards.
Forward direction:
Assume each have atleast one card which was not called by other person. Lets say such card with Sohail is x and Vinay is y. Now,Teja cannot say who has x and who has y. Hence, atleast one of Vinay or Sohail should call out cards of other person.
Now lets say during history, Vinay called x cards of Sohail and Sohail called y cards of Vinay. Let us see how to compute this from the history. Any card Vinay calls must belong to Teja or Sohail, so if a card called by Vinay is not Teja’s then it must belong to Sohail. Using this, we can count number of distinct cards not belonging to Teja that Vinay called as x. Similarly y also.
For the game to end in minimal moves.The best thing that can happen is Vinay and Sohail to call out the cards of the other player which were not called yet.
So we can just simulate their steps assuming each one calls the cards not yet called of the other person.
Code:
public int minTurns(int n,int[] Teja,int[] history){
int y=history.length;
int[] a0 = new int[12345];
TreeSet<Integer> set1 = new TreeSet<Integer>();
TreeSet<Integer> set2 = new TreeSet<Integer>();
int i;
for(i=0;i<n;i++){
a0[Teja[i]]=1;
}
for(i=0;i<y;i++){
if(i%3==1 && a0[history[i]]==0){
set1.add(history[i]);
}
else if(i%3==2 && a0[history[i]]==0){
set2.add(history[i]);
}
}
int lef1 = set1.size();
int lef2 = set2.size();
lef1=n-lef1;
lef2=n-lef2;
if(lef1==0 || lef2==0)
return 0;
i=y;
int cnt=0;
while(true){
cnt++;
if(i%3==1)
lef1--;
if(i%3==2)
lef2--;
if(lef1==0 || lef2==0)
return cnt;
i++;
}
}Time Complexity: O(n+size(history)). size(history) because we have to iterate the whole history array. The simulation part takes O(n) because in every three steps, we discover 2 unknown cards. Since total number of unknown cards is atmost 2*n, we need O(n) turns in simulation and simulating each turn takes O(1) time.
Problems to try: Div1 Medium is a problem with similar background sharing some part of the solution.
Literature:
Solution:
Teja understands everyones cards if and only if atleast one of Vinay or Sohail calls out the cards of the other person.
Proof:
Backward direction is trivial because when a person(say Vinay) calls out all the cards of other person(say Sohail). He knows all the cards of Sohail. He also knows his cards. So he can deduce the set of Vinay. Hence, Teja knows exact distribution of all the cards.
Forward direction:
Assume each have atleast one card which was not called by other person. Lets say such card with Sohail is x and Vinay is y. Now,Teja cannot say who has x and who has y. Hence, atleast one of Vinay or Sohail should call out cards of other person.
Now let’s say during history, Vinay called x cards of Sohail and Sohail called y cards of Vinay. Let us see how to compute this from the history. Any card Vinay calls must belong to Teja or Sohail, so if a card called by Vinay is not Teja’s then it must belong to Sohail. Using this, we can count number of distinct cards not belonging to Teja that Vinay called as x. Similarly y also.
Let us dp state dp[person][call1][call2] as expected number of turns needed for Teja to understand everyone’s cards if current turn belongs to person and Vinay has called out call1 cards of Sohail and Sohail has called out call2 cards of Vinay. Let us person takes values 0,1,2 representing Teja, Vinay, Sohail respectively,
We can define the following recurrence relations.
dp[2][call1][call2] = ((n-call2)/(2*n)) * dp[0][call1][call2+1] + ((n+call2)/(2*n)) * dp[0][call1][call2] +1.
The first term corresponds to player 2 calling a card that gives new information. Second term corresponds to player 2 calling a card that gives no new information.
dp[1][call1][call2] = ((n-call1)/(2*n)) * dp[2][call1+1][call2] + ((n+call1)/(2*n)) * dp[2][call1][call2] +1.
Similar explanation as first equation.
dp[0][call1][call2] = dp[1][call1][call2] + 1
Whatever card Teja calls, it’s never informative because he knows his own cards.
Now if the dependency graph of these equations was a DAG, then we could have directly solved this as a standard dp.
But the dependency graph contains cycles (for example if player 1 and player 2 calls cards which do not give new information then we come back to the same state where we started),
To avoid this, one idea is we can solve using Gaussian Elimination.
There is a more easier approach, we can rewrite the equations in such a way that there will be no cycles.
dp[0][call1][call2] = dp[1][call1][call2] + 1
dp[1][call1][call2] = ((n-call1)/(2*n)) * dp[2][call1+1][call2] + ((n+call1)/(2*n)) * dp[2][call1][call2] +1.
The second and third from previously defined equations remains the same. Let us expand the first equation a little more.
dp[2][call1][call2] = ((n-call2)/(2*n)) *( dp[0][call1][call2+1] +1) + ((n+call2)/(2*n)) * ((n-call1)/(2*n)) *(dp[2][call1+1][call2] +3) + ((n+call2)/(2*n)) * ((n+call1)/(2*n)) *(dp[2][call1+1][call2] +3).
The terms are as follows,
1st : player 2 calls a new card of player 1.
2nd: player 2 calls a card of no new information and player 0 move is irrelevant and player 1 calls a card of some new information
3rd: player 2 calls a card of no new information and player 0 move is irrelevant and player 1 calls a card of no new information
We can rewrite last equation as
(1 – ((n+call2)/(2*n)) * ((n+call1)/(2*n))) *dp[2][call1][call2] = ((n-call2)/(2*n)) *( dp[0][call1][call2+1] +1) + ((n+call2)/(2*n)) * ((n-call1)/(2*n)) *(dp[1][call1+1][call2] +3) + ((n+call2)/(2*n)) * ((n+call1)/(2*n)) *3 .
Now the dependency graph is a DAG, Hence we can solve the problem like it is a standard dp problem.
Proof that dependency graph is DAG : We can see that from every state either one of the card counts (call1 or call2 ) rises or index of the person called rises. Hence ,there cannot be cycles.
Code:
int n;
double[][][] dp = new double[3][1003][1003];
int[][][] visit = new int[3][1003][1003];
public double getprob(int val1,int val2){
double x=1.0;
x*=val1;
x/=val2;
return x;
}
public double solve(int person,int given1,int given2){
if(given1==n || given2==n){
return 0;
}
if(visit[person][given1][given2]==1)
return dp[person][given1][given2];
visit[person][given1][given2]=1;
if(person==2){
dp[person][given1][given2] = getprob(n-given2,2*n) *
(solve((person+1)%3 , given1,given2+1)+1);
dp[person][given1][given2] + = getprob(n+given2,2*n) *
getprob(n-given1,2*n) * (solve(person,given1+1,given2)+3);
dp[person][given1][given2] + = getprob(n+given2,2*n) *
getprob(n+given1,2*n)*3;
dp[person][given1][given2] / = 1-getprob(n+given2,2*n)*
getprob(n+given1,2*n);
}
else if(person==1){
dp[person][given1][given2] = getprob(n-given1,2*n) *
(solve((person+1)%3,given1+1,given2)+1);
dp[person][given1][given2] + = getprob(n+given1,2*n) *
(solve((person+1)%3,given1,given2)+1);
}
else{
dp[person][given1][given2]=solve(person+1,given1,given2)+1;
}
return dp[person][given1][given2];
}
public double expectation(int _n,int[] Teja,int[] history){
n=_n;
int y=history.length;
int[] a0 = new int[12345];
TreeSet<Integer> set1 = new TreeSet<Integer>();
TreeSet<Integer> set2 = new TreeSet<Integer>();
int i;
for(i=0;i<n;i++){
a0[Teja[i]]=1;
}
for(i=0;i<y;i++){
if(i%3==1 && a0[history[i]]==0){
set1.add(history[i]);
}
else if(i%3==2 && a0[history[i]]==0){
set2.add(history[i]);
}
if(set1.size()==n || set2.size()==n){
return i+1;
}
}
int given1=set1.size();
int given2=set2.size();
double ans=solve(y%3,given1,given2);
ans=ans+y;
return ans;
}Time Complexity :O (n*n + size(history)) , Initial preprocessing takes O(size(history)) time. Dp table has 3*n*n states with each taking O(1) time to be computed. Hence, time complexity for the dp part is O(n*n).
Reconstruct Number:
Let us define the dp state dp[pos][dig] as if it is possible to fill the digits from the pos position (assuming zero based indexing) and previous digit was dig. We will handle the first digit (position 0)(separately as it has different restrictions.
Let us define nex[pos][dig] as the best digit to give to current position so that we reach minimum number from pos position till end obeying all the restrictions.
Since the total number of digits in the final number is always same at any state, The key observation to minimise the number is pick the first digit as small as possible. So now we can use dynamic programming to solve this.
Iterate from 0 to 9 for the current digit, check if comparison given holds between previous digit and current current digit and also dp[pos+1][current digit] this is true. Then current digit can be chosen at present position. Choose the minimum one among all those satisfying the criteria.
For the first digit, we iterate from 1 to 9 , and all are valid digits with respect to comparison because there is comparison it needs to hold because it does not have previous digit.
The computation of dp states will be clear from the code.
And finally we can reconstruct the answer using the nex array built during the dp.
Code:
int n;
string s;
int dp[12345][12],nex[12345][12],visit[12345][12];
int solve(int pos,int dig){
if(pos==n)
return 1;
if(visit[pos][dig])
return dp[pos][dig];
int i;
visit[pos][dig]=1;
for(i=0;i<10;i++){
if(s[pos]=='=' && dig==i){
if(solve(pos+1,i)){
dp[pos][dig]=1;
nex[pos][dig]=i;
return 1;
}
}
if(s[pos]=='<' && dig<i){
if(solve(pos+1,i)){
dp[pos][dig]=1;
nex[pos][dig]=i;
return 1;
}
}
if(s[pos]=='>' && dig>i){
if(solve(pos+1,i)){
dp[pos][dig]=1;
nex[pos][dig]=i;
return 1;
}
}
if(s[pos]=='!' && dig!=i){
if(solve(pos+1,i)){
dp[pos][dig]=1;
nex[pos][dig]=i;
return 1;
}
}
}
return 0;
}
string printans(int dig){
string ans="";
int i=0;
while(i<=n){
ans+=(char)(dig+'0');
dig=nex[i][dig];
i++;
}
return ans;
}
class ReconstructNumber{
public:
string smallest(string comparisons){
s=comparisons;
n=s.length();
int i;
for(i=1;i<10;i++){
if(solve(0,i)){
return printans(i);
}
}
return "";
}
};Token Doubling Game:
First let us see what exactly is happening in the game.
Let us denote number of token on the table as x and in hand as y.
- If heads, y=1 then x=x+y
- If tails, x=x-y then y=2*y,
If x goes outside (1,2*n-1) then game ends.
Now let us define dp[i] as expected number of coin flips for the game to end with currently having x=i and y=1.
The key observation is we want to consider possible moves from a state such that always the state we reach has y=1. So the kind of moves we can consider from a state is something like tail,tail,… head (till first head occurs or x goes out of the range). Since as tails keep occuring , y increases exponentially and x decreases at a exponential rate as tails increase. So we can observe there can atmost O(logn) tails continuously such that x still stays in range. So number of possible moves from a state will be O(logn) because each move is the type (Tail)*Head or only tails until you go below x=1. Now we can try to write these dynamic programming equations , We will try to give a taste of how the equation looks for a particular i.
dp[i] = ½(dp[i+1]+1) + ¼(dp[i]+2) +⅛(dp[i-2]+3) + …
Similarly we can write other equations. Also dp[2*n]=0.
Now we can observe that we cannot solve this dp straight forward because there are cycles. One way to solve is to use gaussian elimination. The complexity of gaussian elimination is n*n*n which is not enough.
Now we can rewrite the equation written for i=1,2,….,2*n-2 such that
½(dp[i+1]+1) = -¾(dp[i]) + ½ + ⅛(dp[i-2]+3) + …
So now we have expressing i = 2,3,…., 2*n-1 using only lower indexed states.
And we still haven’t used dp equation written for 2*n-1.
So we can take equation written for dp[2*n-1] and keep removing highest indexed term by substituting its formula using only lower indexed terms (as found above). Finally we will be left with some equation of the form a*dp[1]-b =0. And dp[1] = b/a = b *(a^(-1)).
Now once we find dp[1], we can use
½(dp[i+1]+1) = -¾(dp[i]) + ½ + ⅛(dp[i-2]+3) + …
To find all the dp values. We need to return dp[n] because initially x=n and y=1.
Now, question guarantees few things such as inverse exists. Do you see a way to prove inverse exists ? We could not see a way, so we simulated all the possible values for n from 1 to 100000 and checked that always inverse existed at the step where dp[1] is calculated.
Code:
public class TokenDoublingGame{
public long getpow(long a,long b){
long mod=(1000*1000*1000+7);
long res=1;
while(b!=0){
if(b%2==1){
res*=a;
res%=mod;
}
b/=2;
a*=a;
a%=mod;
}
return res;
}
public long inverse(long val){
long mod=(1000*1000*1000+7);
return getpow(val,mod-2);
}
public int expectation(int n){
if(n==1){
return 1;
}
long inv2=inverse(2);
long mod=(1000*1000*1000+7);
long[] dp = new long[2*n+10];
long[] ans = new long[2*n+10];
long[] remem = new long[2*n+10];
long[] pr = new long[200];
long[] st = new long[200];
ArrayList<Integer> states_reachable[] = new ArrayList[2*n+10];
ArrayList<Long> coeffs[] = new ArrayList[2*n+10];
long prob;
long twos,val;
long value=0;
long steps;
int i,j;
pr[0]=1;
for(i=1;i<200;i++){
pr[i]=pr[i-1]*inv2;
pr[i]%=mod;
}
for(i=0;i<200;i++){
st[i]=i*pr[i];
st[i]%=mod;
}
for(i=0;i<2*n+5;i++){
states_reachable[i]=new ArrayList<>();
coeffs[i]=new ArrayList<>();
}
for(i=2;i<2*n-1;i++){
prob=1;
twos=1;
val=i;
value=0;
steps=0;
j=0;
while(true){
if(val<=0){
value+=st[(int)steps];
value%=mod;
break;
}
prob = pr[(int)steps+1];
value+=st[(int)steps+1];
if(val+1!=i+1){
states_reachable[i+1].add((int)val+1);
if(val+1==i){
coeffs[i+1].add((2*prob-2)%mod);
}
else{
coeffs[i+1].add((2*prob)%mod);
}
}
val-=twos;
twos*=2;
steps=steps+1;
}
remem[i+1]=2*value;
remem[i+1]%=mod;
}
states_reachable[2].add(1);
coeffs[2].add(-2L);
remem[2]=2;
for(i=2*n-1;i<=2*n-1;i++){
prob=1;
twos=1;
val=i;
value=0;
steps=0;
j=0;
dp[2*n-1]=1;
while(true){
if(val<=0){
value+=st[(int)steps];
value%=mod;
break;
}
prob = pr[(int)steps+1];
value+=st[(int)steps+1];
if(val+1!=i+1){
dp[(int)val+1]-=prob;
dp[(int)val+1]%=mod;
}
val-=twos;
twos*=2;
steps=steps+1;
}
value*=-1;
value%=mod;
}
for(i=2*n-1;i>=2;i--){
for(j=0;j<states_reachable[i].size();j++){
dp[states_reachable[i].get(j)]-=dp[i]*coeffs[i].get(j);
dp[states_reachable[i].get(j)]%=mod;
}
value-=dp[i]*remem[i];
value%=mod;
dp[i]=0;
}
assert(dp[1]!=0);
ans[1]=-1*value*inverse(dp[1]);
ans[1]%=mod;
for(i=2;i<=n;i++){
ans[i]=0;
for(j=0;j<states_reachable[i].size();j++){
ans[i]+=ans[states_reachable[i].get(j)]*coeffs[i].get(j);
ans[i]%=mod;
}
ans[i]+=remem[i];
ans[i]=-1L*ans[i];
ans[i]%=mod;
}
ans[n]%=mod;
ans[n]+=mod;
ans[n]%=mod;
return (int)ans[n];
}
}Time Complexity: Since each equation of size O(log(n)). We need O(nlogn) time to find all the equations. Each equation will be substituted atmost once. So we need O(nlogn) time. And to evaluate all the equations from bottom to top , we need O(nlogn) time.
Hence, total time complexity is nlogn.
teja349
Guest Blogger
