Samarth12's blog

How to solve this ICPC problem??
By Samarth12, history, 5 years ago, In English

How to solve this problem of ICPC Online round 2019: https://www.codechef.com/ICPCIN19/problems/SHUFGRID

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Practice

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

    If u can't solve it then please don't spam....

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

      Make a dp of state N X (2 X 2) i.e. dp[i][j][k] , i represents number of steps you have taken. j represents whether you are in the same row. k represents whether you are in the same column. The answer will be independent of the row and column i.e. all points in the grid will have the same probability.

      Make appropriate transition in the dp from ith step to (i+1)th step.

      → Reply