adarsh000321's blog

Code n Counter 4.0 Problem
By adarsh000321, history, 5 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adarsh000321 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The image is not visible ...BTW were you able to solve the RSP game..Was it also dp/recursion ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yup i did solve that prob... it was dp

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate and tell the states and transitions ?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        • all you needed to do is to get the states ... which i guessed as double dp[][][]=new double[total_rock+1][total_scessiors+1][total_papers+1] and the rest is below: `` ~~~~~
        1. dp[r][s][p] = 1.0;
        2. for (int rr = r; rr >= 0; rr--) {
        3. for (int ss = s; ss >= 0; ss--) {
        4. for (int pp = p; pp >= 0; pp--) {
        5. int all = rr * ss + ss * pp + pp * rr;
        6. if (all == 0) continue;
        7. if (rr > 0) dp[rr — 1][ss][pp] += dp[rr][ss][pp] * rr * pp / all;
        8. if (ss > 0) dp[rr][ss — 1][pp] += dp[rr][ss][pp] * rr * ss / all;
        9. if (pp > 0) dp[rr][ss][pp — 1] += dp[rr][ss][pp] * ss * pp / all;
        10. }
        11. }
        12. } ~~~~~
        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          r=total rocks ... similarly for s and p

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            1. import java.text.DecimalFormat;
            2. import java.util.*;
            3. public class Main {
            4.     public static void main(String args[]) {
            5.         Scanner sc = new Scanner(System.in);
            6.         int t = sc.nextInt();
            7.         while (t-- > 0) {
            8.             int r = sc.nextInt();
            9.             int s = sc.nextInt();
            10.             int p = sc.nextInt();
            11.             double dp[][][] = new double[r + 1][s + 1][p + 1];
            12.             dp[r][s][p] = 1.0;
            13.             for (int rr = r; rr >= 0; rr--) {
            14.                 for (int ss = s; ss >= 0; ss--) {
            15.                     for (int pp = p; pp >= 0; pp--) {
            16.                         int all = rr * ss + ss * pp + pp * rr;
            17.                         if (all == 0) continue;
            18.                         if (rr > 0) dp[rr — 1][ss][pp] += dp[rr][ss][pp] * rr * pp / all;
            19.                         if (ss > 0) dp[rr][ss — 1][pp] += dp[rr][ss][pp] * rr * ss / all;
            20.                         if (pp > 0) dp[rr][ss][pp — 1] += dp[rr][ss][pp] * ss * pp / all;
            21.                     }
            22.                 }
            23.             }
            24.             double rock = 0.0;
            25.             for (int i = 0; i <= r; i++) {
            26.                rock += dp[i][0][0];
            27.            }
            28.            double scissor = 0.0;
            29.            for (int i = 0; i <= s; i++) {
            30.                scissor += dp[0][i][0];
            31.            }
            32.            double paper = 0.0;
            33.            for (int i = 0; i <= p; i++) {
            34.                paper += dp[0][0][i];
            35.            }
            36.            DecimalFormat f = new DecimalFormat("#0.000000000");
            37.            System.out.println(f.format(rock) + " " + f.format(scissor) + " " + f.format(paper));
            38.        }
            39.    }
            40. }
            → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 what if we want to calculate situation having i-1 rocks, j scissors and k papers i.e., when rock doesnt win. It can be done using dp transition as
 dp[i-1][j][k]+=dp[i][j[k]*prob of current_rock_loosing_situation(i.e., i*k divided by total_ways);
same can be done for j-1 and k-1

            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

            → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adarsh000321 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Does anyone have any idea about the problem in the image

→ Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

I solve this problem with combinatorics

Spoiler
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah there are 3 arrangements, that input is incorrect, and my answer gives also 3, and there is two answers for that:

      1. Because of your browser (|a[i] — i|) not opened

      2. Authors forgot to write (|a[i] — i|) in problem

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh Now i understand. Well thanks for your cooperation and kind reply. It helped a lot.

        → Reply