ADIGIT - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Precomputation

PROBLEM:

Given N(<=10^5 ) digits (0<=each digit<=9), and M(<=10^5) queries, each consisting of one x(1<=x<=n). Print B1 - B2.
B1 = sum of all ( ax - ay ) such that x > y and ax > ay.
B2 = sum of all ( ax - ay ) such that x > y and ax < ay.

EXPLANATION:

We define a new array A where A[i][j] is the number of times digit i occurs in a1,a2,…aj.
Code:

for i=0 to 9:    // calculate the row A[i] for each i=0 to 9.    
    for j=1 to n:   
        A[i][j]=A[i][j-1];   
        if a[j]==i: A[i][j]++;   // if a[j]==i, current value one more than previous.

For each input query p, let q=ap, we do:

B1=0    
for i=0 to q-1:  // sum of those where ax > ay    
    B1 += A[i][p-1]*(q-i)   // difference is (x-i)   

B2=0    
for i=q+1 to 9:  // sum of those where ax < ay    
    B2 += A[i][p-1]*(q-i)    // difference is (x-i)   

print B1-B2

Time Complexity: O( N * 10 ) [ Computation of A ] + M * 10 ( For M queries.)

AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.

7 Likes
2

Can someone please explain what is happening in the 1st code? In the A[i][j] array? Is A[i][j] a character array or integer array? I am unable to understand the logic of this solution.

3

It says, when a new digit is added, number of times every digit has occurred so far remains same except for the newly added digit. For newly added digit, it is 1 + count before this digit was added.

If you re-read the problem, I hope you would understand now.

4

How about this ->

a[…] is the input

in A[i][j] store sum of all Absolute( i - a[j] ) for i = 0 to 9… this takes O(10*n) time… n is input length

now if the query is q

then just print A[a[q]][q-1] … this is sum of all Absolute(a[q] - a[0…q])

This should run in
O( N * 10 ) [ Computation of A ] + M time … faster ??

1 Like
5

edit** previous comment
in A[i][j] store sum of all Absolute( i - a[0 to j] ) …

6

//Is it not the simpler way…?

#include
using namespace std;
#include
int main()
{
int i,a[20],b[20],n,m,x,k;
char s1[20];
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>s1[i];
a[i]=(s1[i]-‘0’);
}
for(k=1;k<=m;k++)
{
int B1=0,B2=0;
cin>>x;
for(i=1;i<x;i++)
{
b[i]=a[x]-a[i];
if(b[i]>0)
B1+=b[i];
else if(b[i]<0)
B2+=b[i];
}
cout<<(B1-B2)<<endl;
}
}

//Can anyone tell why it was giving a runtime error?

7

My submitted solution also precalculates all the steps with O(10 * N) time complexity and O(N) space.
Queries become constant.
Lets say “A” of size N to store the precalculated values and “a” the input:

for step = 0 to n
   int ans
   for i = step-1 to 0
       t = a[step] - a[i]
   if t == 0 // Meaning that we have calculated the values for 
                 // the same number previously and we only need to retrieve that value from A
        ans += A[i]; 
	A[step] = ans;
	break;
   end if
   ans += abs(t);
   A[step] = ans;
    end for
end for

Queries, let Q be the query:

print A[Q]
8

Thanks @mjbpl
I followed the ‘maintaining count of each digit’ logic as in the editorial yet I get a TLE for this solution. What could I be missing out?
http://www.codechef.com/viewsolution/3769202

9

Can someone help me in understanding why my solution throws a runtime error? I have followed the algorithm mentioned.

10

Please help…I was getting WA for my submissions. I think, I used the above mentioned algo in my code. Can anyone please point out the error in my code!
My Code

11

Check this solution
http://www.codechef.com/viewsolution/3727831

12

I also calculated all the possibilities with 0-9 O(10n) time n space and then O(1) in answering…

13

Can anyone please tell me what is wrong with this code http://www.codechef.com/viewsolution/3932929
I am getting WA

14

Check this solution:

https://www.codechef.com/viewsolution/9957518
You need to first precompute the value and then find the answer in constant amount of time, if you do not do so,
you will end up with an algorithm with complexity of O(m*n) in worst case scenario because for every query you will process the array.

15

we can store prefix sum… to reduce time complexity further

16

Can anyone explain why is my code wrong…?
I used a slightly different algo. I took a 2-d array where b[i][j] is the bj at ith index.

https://www.codechef.com/viewsolution/15149991