Doubt in STRPTRE

help
1

https://www.codechef.com/viewsolution/30835337
I passed the first sub task but failed the second, probably due to overflow .
What would be the correct approach for this ?

2

https://www.codechef.com/viewsolution/30843606
use a %= MOD in power

2 Likes
3

Thanks :smiley:

4

https://www.codechef.com/viewsolution/30844491
I think I am having the same error. Can you tell why ??

5

https://www.codechef.com/viewsolution/30845332
you were pre calculating dp, p over loop 1000 not 100000

1 Like
6

Really stupid of me ! Thanks for your help !

7

one more thing, why dp[1] = 4, should be 2, only black edges are allowed, but by chance 2 was cancel out by other 2 in q

8

Managed that in the denominator. Denominator is 2 * (nodes) * (nodes-1) instead of (nodes) * (nodes-1). Probability of choosing correct colour is 1/2.

9

ok, so you have considered pair (a, b) and (b, a) are two different

1 Like
10

Yes !

11

Why you multiply with (i+1)/2 when you iterate?

12

Notice that after the 2nd level we can either create an edge from 3rd level to 2nd level or 0th level maintaining the strip, so we have to multiply it by 2, similarly from 4th level , we can have an edge to 3rd or 1st level , from 5th level to 4th,2nd and 0th level. So you can see that the number of possibilities are increasing after each level. You will understand better if you draw the tree and check this out . Hope this helps.

13

@ajaymalik plzz help i am not getting error in my answer output is correct
//By IIITN
//only when x==1
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define mod 1000000007

int main()
{
ll t,i;
cin>>t;
while(t–)
{
int a,b;
cin>>a>>b;
int A[2];
int B[2];
int p=a;
int q=b;
A[0]=a/10;
A[1]=a%10;
/* for(i=0;i<2;i++)
{
cout<<A[i]<<" ";
}*/
B[0]=b/10;
B[1]=b%10;
// cout<<A[0]<<B[0]<<endl;
int c1,c2,c3,c4;
int l;
l=A[0];
A[0]=B[0];
B[0]=l;
a=A[0]*10+A[1];
b=B[0]*10+B[1];
//cout<<a<<b<<endl;
c1=a+b;//check
A[0]=p/10;
A[1]=p%10;
B[0]=q/10;
B[1]=q%10;
l=A[0];
A[0]=B[1];
B[1]=l;
a=A[0]*10+A[1];
b=B[0]*10+B[1];
// cout<<a<<b<<endl;//check
c2=a+b;
A[0]=p/10;
A[1]=p%10;
B[0]=q/10;
B[1]=q%10;
l=A[1];
A[1]=B[0];
B[0]=l;
a=A[0]*10+A[1];
b=B[0]*10+B[1];
// cout<<a<<b<<endl;
c3=a+b;//check
A[0]=p/10;
A[1]=p%10;
B[0]=q/10;
B[1]=q%10;
l=A[1];
A[1]=B[1];
B[1]=l;
a=A[0]*10+A[1];
b=B[0]*10+B[1];
// cout<<a<<b<<endl;
c4=a+b;//check
int max1,max2;
if(c1>c2)
max1=c1;
else
max1=c2;
if(c3>c4)
max2=c3;
else
max2=c4;
if(max1>max2)
cout<<max1<<endl;
else
cout<<max2<<endl;
//cout<<c1<<c2<<c3<<c4<<endl;
}

  }
14

what if any of the a, b is only single digit