Hello Codeforces, I am stuck in one of the challenges , all i can think of is dp, but i dont know how to implement that and i also think that the given sample test case( not in image) was wrong because possible arrangements for n=3 and p=1 are {1,2,3},{3,2,1},{3,1,2} that is, there are 3 arrangements but sample output was 2 ; link to image : https://drive.google.com/open?id=1y3CARnR4_KUKP6z3iUcMKhePkZWg6IS4
Auto comment: topic has been updated by adarsh000321 (previous revision, new revision, compare).
The image is not visible ...BTW were you able to solve the RSP game..Was it also dp/recursion ?
yup i did solve that prob... it was dp
Can you elaborate and tell the states and transitions ?
r=total rocks ... similarly for s and p
Sorry , but I dont quite understand the transition . I mean why are we multiplying..like by rr and pp in line 7 . Can you please explain ? Thank you for the help.
For that problem , you need to calculate dp for every situation . Let for current situation dp[i][j][k] means there are i rocks, j scissors and k papers. Total ways to select pairs from current situation = C(i+j+k,2)=i*j + j*k + k+i , where i*j = ways in which rock can win. Similarly for papers and scissors.
Now summing up all state with dp[i][0][0] (i=0 to rocks) u get rock winning probability situation . Same can be done for scissor and paper winning probs
Auto comment: topic has been updated by adarsh000321 (previous revision, new revision, compare).
Does anyone have any idea about the problem in the image
I solve this problem with combinatorics
If p is equals to n then the answer will be n!
Let's start from two
for two n = 2 p = 1 the anwer would be 2
because there is one possible anwer
2 1
for $$$2$$$ $$$2$$$ we have 2! answers
Let's check for 3
3 2 answer would be 3! — 2! because there are we need to take away 2! answers from the last case
and for 3 1 we have maximum (3! — 2!) answers and we need to take away the answer for 2 1 because there will be 2 1 combinations for(3! — 2!) for example : $$$3$$$ $$$2$$$ $$$1$$$ which is incorrect the answer (3! — 2! — 1)
We can create dp that the state will be the answer, and for every i dp[i][i] is equal to i factorial then for every state we need take away the n — 1 p combinations for dp[n][p] and the dp[n][p+1] combinations which are incorrect
I just want you to interrupt me if i am wrong . In this problem, we needed to find all arrangements where a[i]-i is not equal to p. So in array[]={3,1,2} , you said that array[3]-2=1 but array[3]=2 => array[3]-2=2-2=0 (all using 1-based indexing) . Comment if i am wrong anywhere. Thanks for your kind reply. Could you please elaborate the meaning of the question.
Yeah there are 3 arrangements, that input is incorrect, and my answer gives also 3, and there is two answers for that:
Because of your browser (|a[i] — i|) not opened
Authors forgot to write (|a[i] — i|) in problem
Oh Now i understand. Well thanks for your cooperation and kind reply. It helped a lot.