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:
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
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
here find lcm=15
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
Really nice approach.
@admin please look into this matter.As the organizers of the contest have to choose the winners.
Bro can you please make the image of last question public.
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.
Expected TC should be O(M*K)
https://www.codechef.com/OCT18A/problems/TREEWALK 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 !
Type of graph doesnt matter for this subtask.
For computing K. You are also computing answers for 1,2,…,K-1. Just save them. And answer all queries in O(1) per query.
Yet another weak tcs in external contests.
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).
@anon55659401 No you are not eligible for the finals