hrishabhpatel09's blog

Can some Explain why my solution fails

By hrishabhpatel09, history, 20 months ago, In English

Here is a Problem: 2069B - Set of Strangers Here is Soln: 306760751

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

Comments Comments (2)
| Write comment?
»
20 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Bro tune third question 2069C - Красивая последовательность,dp ka implementation kaise kiya hai yeh bata sakta hai , like approach mujhe bhi aagayi thi but i don't know how to implement it

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

    good subsequences are of form 12222....3. count of 2s >= 1 and start me 1 and end me 3.

    // dp[i][1] bolega no of subsequences of form "1" till i // dp[i][2] bolega no of subsequences of form "122...." till i // dp[i][3] bolega no of subsequences of form "12....3" till i

    // dp[i][1] ,agar a[i] == 1, dp[i][1] = 1 + dp[i-1][1], nhi toh base dp[i][1] = dp[i-1][1]

    // dp[i][2], agar a[i] != 2 toh dp[i][2] = dp[i-1][2] // but if a[i] == 2 // i-1 tak jo already 12... bangayi ume 2 jod de, ya mat jod. total 2 * dp[i-1][2] hojayengi // i-1 tak jo no of form "1" ki subsequences hai unme 2 jod de, toh dp[i — 1][1] // so dp[i][2] = dp[i — 1][1] + 2 * dp[i — 1][2]

    //dp[i][3], i-1 tak jo already 12.... bangayi unme 3 jod de bas, dp[i][3] = dp[i-1][2]

    → Reply