TLE in ADIGIT

general
,
1

Problem: http://www.codechef.com/problems/ADIGIT

My solution: http://www.codechef.com/viewsolution/3769202

I followed the ‘maintaining count of each digit’ logic as in the editorial yet I get a TLE for the above solution. What could I be missing out?

2

you need to store number of occurrence of digit 0-9 at every index…

And the given X is the index not the value at that index.

check My solution

3

you should not compute from scratch for every query you need to store the values of your previous computation and use it for next computation

4

But it isn’t given that the queries are in ascending order. So how will use previous computation for next one?

5

for(i=1;i<=n;++i)

{

for(j=0;j<10;++j)

{

count_till_now[i][j]=count_till_now[i-1][j];

}

count_till_now[i][given[i]]++;

}

6

@letsctheworld 2d array is not necessary.you just need to have a single counter[10].@sandy999 firstly do the computation before evaluating the queries. 1,2,…n and store the values at each index in some array(say answer[n]).and after that you can answer queries directly through answer array.