Editorial bytes1 - radix

general
,
1

Problem Link: http://www.codechef.com/problems/BYTES1

Difficulty: Easy

Strategy: Memoization

Explanation:
The problem can be solved by following strategy:

  1. Store the number of occurrence of each value from starting index to current index. e.g. For array A={1,2,1,3,2} declare a 2D array cnt[4][5] then cnt[1]={1,1,2,2,3}, cnt[2]={0,1,1,1,2} and cnt[3]={0,0,0,1,1}.
  2. After storing for every value, move on to queries.
  3. Now, for each query [i,j], count the no. of values of k such that cnt[k][j]-cnt[k][i-1] is non zero.