Tutorial — codeforces problem 597C Subsequences http://codeforces.me/problemset/problem/597/C

Revision en9, by uditgupta, 2017-06-21 21:16:48

Codeforces contest[user:uditgupta][submission:27884973][problem:http://codeforces.me/problemset/problem/597/C]-Consider for index ith

-Now at each index we want to find number of subsequences ending at index i

of length 1 , 2 , 3 ... k+1 ;

How we can compute this ?

say arr[i] == 5

if know number of subsequences which end at value either 1 or 2 or 3 or 4

from index 1 to index i+1

pls read above lines again if not clear.

so now wat the equation becomes

no of subsequences of length k+1 which end at index i=

    number of subsequences of length k which end at [value 1] from index range 1  to (i-1) of given array

    +   number of subsequences of length k which end at [value 2] from index range 1  to (i-1) of given array 

    +   number of subsequences of length k which end at [value 3] from index range 1  to (i-1) of given array 

    +   number of subsequences of length k which end at [value 4] from index range 1  to (i-1) of given array   

For this part we can use Segemnt Tree to compute sum of subsequences ...

Segment tree : we use tree[1] to store number of subsequences which end at value 1

             : we use tree[2] to store number of subsequences which end at value 2


But we want number of subsequences of length 1 , 2 ,3 .. (k+1)

 So we will use 2-d Segment Tree

My submission : http://codeforces.me/contest/597/submission/27884973

Tags 597c, 2d segment tree, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English uditgupta 2017-06-21 21:16:48 55 Tiny change: '[user:udit' -> '[Codeforces contest](http://codeforces.me/contest/597)[user:udit' (published)
en8 English uditgupta 2017-06-18 16:24:53 75
en7 English uditgupta 2017-06-18 16:23:53 93
en6 English uditgupta 2017-06-18 16:22:30 38
en5 English uditgupta 2017-06-18 16:21:38 4
en4 English uditgupta 2017-06-18 16:21:00 2 Tiny change: 'ndex ith\n-Now at ' -> 'ndex ith\n\n-Now at '
en3 English uditgupta 2017-06-18 16:20:10 2 Tiny change: 'Consider for index ith\nNow at eac' -> '-Consider for index ith\n-Now at eac' (saved to drafts)
en2 English uditgupta 2017-06-18 16:16:27 3 Tiny change: 'ndex i= \n number' -> 'ndex i= \n\n number'
en1 English uditgupta 2017-06-18 16:15:50 1299 Initial revision (published)