Hey, @onkar2000 where is the rank list, in whole contest, rank list is missing and after contest still missing, please update ASAP.
Add link to the contest as well
There was technical issue from Codechef side…We are in touch with the support team…Ranklist will be updated soon…Stay Tuned. Sorry for the inconvenience caused…
Bro can you please provide me the editorial or approach for Problem: CCWI1908
haan my approach was
if there are k envelops
put 1 crorepati in 1 envelop as long as possible
and put the remaining all in last enevelop
so if n>k-1:
ans=1/k+1/k+1/k+…(k-1) times
because we have put 1 crorepati in 1 enevelope and the probability of choosing each envelope is 1/k
if there are still some crorepati are left
then rem crorepati=n-(k-1)
and total number of cards in last coupon =n-(k-1)+m
winning probabilty is (n-k+1)/(n-k+1+m)
and the probability of choosing this coupon is 1/k
so ans=k-1/k + 1/k *(n-k+1/n-k+1+m)
if n<=k-1 then
we can keep n crorepatis in n enevelops and leave the remaining ones
ans=n/k
Example 1 :
n=5 m=2 k=3
put 2 creorepatis in 2 envelops
probability to choose these two enevelops=2/3
now put 3 crorepatis and 2 roadpatis in last enevelop
the winning probability =1/3 *(3/5)=1/5
ans=2/3+1/5
here find lcm=15
numerator=10+3
denominator=15
prob=13/15
Example 2:
n=2 m=2 k=3
put 2 crorepatis in 2 envelops and 2 roadpatis in 3rd enevelop
probability of choosing first 2 enevelops=2/3
Thanks bro.
Really nice approach.
Bro can you please make the image of last question public.
Problem: CCWI1902
My rank was 29
…
.Are we eligible for finals?
Was the expected time complexity for the last problem : - O(V^3 . K) . where, V=600 and K=500 , this shouldn’t have passed the 1 second time limit, but many solutions (almost all) had this time complexity and they got AC.
Graph-K?
Summary
Expected TC should be O(M*K)
CodeChef: Practical coding for everyone 2nd Subtask.
Here the graph is a very bad graph with multiple edges and self-loops, so I stored a[i][j]=(number of direct-edges from ‘i’ to ‘j’).
Now, for k=2, answer= (Matrix)^2
For k=3, answer=(Matrix)^3
Also, they are asking for all k's from 1 to 500, not just for a particular ‘K’ , so can’t use that method…(Maybe I am wrong?)
And, to my surprise this gave AC,(matrix-multiplication, 'k'-times)
I did not even do matrix exponentiation because they ask for all k’s
Thanks for the link !
Ok. Got it. Yup, if I knew the tcs would be weak I would submit it in the contest for sure.
I don’t see any solution with O(V^3 * K). Almost solutions have time complexity of O(M * K).