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;
}
My approach is this:
As the number of colour transitions is fixed I used them to generate valid strings. I’ll try to explain with this example:
RG - 1
GR - 1
RO - 0
OR - 0
GO - 0
OG- 0
now without considering “N” valid string combinations we can make from above pairs are:
RGR
GRG
RG
GR
R
G
O
Once we have all these valid pairs we need to expand them to the size of n in order to get all the valid strings. Let’s say n is 10, then we need to expand all the above strings to size 10.
For example, RG can be expanded as:
RRRRRRRRRG => 9 R’s followed by 1 G
RRRRRRRRGG => 8 R’s followed by 2 G’s.
RRRRRRRGGG => 7 R’s followed by 3 G’s.
and so on.
From above we can see that RG can be expanded as:
“x1” R’s followed by “x2” G’s, where x1+x2 = n.
So the number of valid strings we can form is the number of positive integral solutions to equation x1+x2 = n.
Similarly, RGR can be expanded as “x1” R’s followed by “x2” G’s followed by “x3” R’s where x1+x2+x3 = n.
So, for a valid string of size k. the number of possible expansions is the same as the number of positive integral solutions to the equation :
x1+x2+x3+x4+…+xk = n.
which can be calculated using formula C(n-1,k-1).
2 Likes
there are overlapping sub-problems that’s why I used dp array. I guess even your code was failing because of that.
Consider this case :
10 - RG
10 - GR
10 - RO
10 - OR
10 - OG
10 - GO
let’s say your filled first three positions as RGR then your remaining pairs will be 9,9,10,10,10,10 you’ll go on and calculate all the pairs in worst case you’ll do 9 * 9 * 10 * 10 * 10 * 10 operations.
now when you start filling with G you’ll encounter a case where first three letters are GRG then your remaining pairs will be 9,9,10,10,10,10 again you need to do same operations.
so to avoid this i used dp array to memorize.
cool, thanks 
Anyone received mail regarding finals?
Okay Thanks
BTW it is written in schedule section of techgig code gladiators website that final will held on 8th August and offline.
But In this lockdown how the offline finals be possible?
I think they should shift the finale to September or later.
God knows 
1 Like
Is it necessary to go for Hackathon before finale , or directly finale will be based on semi final results
Are the results for finale out?
1 Like
Yes But no confirmation mail received
And here S.No. is different from the rank in leaderboard.
My rank in leaderboard is 254 but in result section , my name is on S.No 687.
Yes , they just shortlist 768 users regardless of their rank.
1 Like
Yes they selected top 768 users from semifinalists as per their ranks in leader board but listed them randomly on the results page, not in the order of their ranks.
I dont know what miracle happened in this contest but as I checked on the last day of semifinals my score was 160 and my rank was around 190, but what miracle happened that 1000+ people got 200 score in just some hours or some days or the leader-board was faulty. Or May be my interpretation error.
When is the finale supposed to be held? It was sometime in June before COVID hit, but what is the new plan?