last year they select top 500 , This year i think same , but not sure .
1 Like
Did anyone here solve question 2 all 10 cases ? Can you please share logic ?
Now the contest is over.
So Please send the solution of both the problems, anyone who solved them.
Problem 2 was really Interesting. Where can I practice more such problems ?
And also can someone share it’s solution ?
1 Like
It was a standard dp problem, I can’t access my code though.
It was a dp-problem with a small mathematical formula.
Here’s my code:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1e9+7;
ll n,_ro,_rg,_or,_og,_gr,_go;
ll fac[100010];
ll rpow(ll a,ll b)
{
if(b==0)
return 1;
if(b==1)
return a;
ll ret1=rpow(a,b/2)%mod;
ll ret2=(ret1*ret1)%mod;
if(b%2==0)
return ret2%mod;
return (ret2*a)%mod;
}
ll inv(ll n)
{
return rpow(n,mod-2);
}
ll ncr(ll n,ll r)
{
if(n<r)
return 0;
// cout<<n<<" "<<r<<endl;
return (fac[n]*((inv(fac[r])*inv(fac[n-r]))%mod))%mod;
}
ll goo(ll ss) {
// cout<<ss<<endl;
ll ret = ncr(n-1,ss-1);
return ret;
}
ll dp[4][11][11][11][11][11][11];
ll fil(ll pc , ll ss) {
if(dp[pc][_rg][_ro][_go][_gr][_og][_or]!=-1)
return dp[pc][_rg][_ro][_go][_gr][_og][_or];
if(ss>n) {
indent preformatted text by 4 spaces
return 0;
}
ll ret = goo(ss)%mod;
if(pc == 1) {
if(_ro > 0) {
_ro--;
ret = ((ret%mod) + (fil(2,ss+1)%mod))%mod;
_ro++;
}
if(_rg>0) {
_rg--;
ret = ((ret%mod) + (fil(3,ss+1)%mod))%mod;
_rg++;
}
}
else if(pc == 2) {
if(_og > 0) {
_og--;
ret = ((ret%mod) + (fil(3,ss+1)%mod))%mod;
_og++;
}
if(_or>0) {
_or--;
ret = ((ret%mod) + (fil(1,ss+1)%mod))%mod;
_or++;
}
}
else {
if(_gr > 0) {
_gr--;
ret = ((ret%mod) + (fil(1,ss+1)%mod))%mod;
_gr++;
}
if(_go>0) {
_go--;
ret = ((ret%mod) + (fil(2,ss+1)%mod))%mod;
_go++;
}
}
return dp[pc][_rg][_ro][_go][_gr][_og][_or]=ret%mod;
}
ll foo(ll ai) {
// cout<<fil(1,1)<<" "<<fil(2,1)<<" "<<fil(3,1)<<endl;
ll ans= (fil(1,1)%mod) + (fil(2,1)%mod) + (fil(3,1)%mod) ;
ans%=mod;
return ans;
}
int main() {
memset(dp,-1,sizeof(dp));
fac[0]=1;
for(ll i=1;i<=100000;i++) {
fac[i] = ( (fac[i-1] %mod) * (i%mod) )%mod;
}
cin>>n;
cin>>_ro>>_rg>>_or>>_og>>_gr>>_go;
ll res = foo(0);
cout<<res<<endl;
}
I don’t know if it’s ok to share my solution if it’s not allowed someone please let me know.
1 Like
I was able to solve 1st question using DP.
But I think that my approach is not good as I used 12-D array to find solution using DP.
1 dimension for previous doctor, 1 for patient and 10 dimensions for 10 doctors availability -> Total 12 D array.
It is a very lengthy approach.
Please anyone share a short approach or other DP solution.
If possible, Please share code also or share the approach.
Take an Integer mask instead of 10 integers, If ith bit is set then doctor is taken, else not taken.
I think you know the rest. (Search about bitmask dp if you want more detail.)
1 Like
@hetp111 @ssrivastava990 Can You Share Your Approach and code For First Problem of Code Gladiators , I Kept thinking of Bitmasking and i am sure it will be a 2^n Solution.
But the Problem is i was not able to implement it.
hey , how did you become the moderator & what benefits do you get with this role ??
1 Like
I dont know… Maybe I was worthy.
wdym ?
You could clear all cases with this ? I could do only 9. 1 was giving TLE
can you explain ?
Yes, my code cleared all the test cases. I submitted it twice two times it cleared all the cases. If your implementation is same as mine then even your code should pass all the test cases
All I did was, I counted number of ways for 1,2,…n (G-R,R-G,R-O,O-R,O-G,G-O) transformations together and then filled in between by using logic of putting n similar items in k different bins using (n+k-1Ck-1). I didn’t use any DP array. Can you explain yours a bit ?
1 Like
This was my logic, i optimized a little later though, but could not still get the last case done.
void rec_func(long long ro, long long rg, long long or1, long long og, long long gr, long long go, char last, long long cnt)
{
if(cnt==N)
return;
a[cnt]++;
if(last==‘r’)
{
if(ro>0)
rec_func(ro-1,rg,or1,og,gr,go,‘o’,(cnt+1)%M);
if(rg>0)
rec_func(ro,rg-1,or1,og,gr,go,‘g’,(cnt+1)%M);
}
if(last==‘o’)
{
if(or1>0)
rec_func(ro,rg,or1-1,og,gr,go,‘r’,(cnt+1)%M);
if(og>0)
rec_func(ro,rg,or1,og-1,gr,go,‘g’,(cnt+1)%M);
}
if(last==‘g’)
{
if(gr>0)
rec_func(ro,rg,or1,og,gr-1,go,‘r’,(cnt+1)%M);
if(go>0)
rec_func(ro,rg,or1,og,gr,go-1,‘o’,(cnt+1)%M);
}
return;
}
using namespace std;
int main()
{
long long a1,b,c,d,e,f,ans,cnt,k,r,n;
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % p;
cin >> N;
for(i=0;i<N;i++)
a[i]=0;
cin >>a1>>b>>c>>d>>e>>f;
ans=3;
rec_func(a1,b,c,d,e,f,‘r’,0);
rec_func(a1,b,c,d,e,f,‘g’,0);
rec_func(a1,b,c,d,e,f,‘o’,0);
for(i=1;i<N;i++)
{
r=i+1;
n=N-(i+1);
k=nCrModPFermat(n+r-1,r-1,M);
k=(k*a[i])%M;
ans=(ans+k)%M;
}