A GOOD PROBLEM

general
1

please post the editorial of A GOOD PROBLEM :


please post the editorial for chef and tree:

why nobody post its?
3 Likes
2

A Good Problem solution:

It is easy to do the small test case using n^2 algo

Now for the larger case you divide the entire array into NBUC number of buckets of BUC_SIZE size. (I used NBUC=100 and BUC_SIZE=1000)

For each bucket you can calculate the value as asked. Now the problem remains for how to do it for pairs across buckets.

First thing you need to do is for each element from [0, 2^14) calculate its seniors and juniors. if (i&j == j) then j is junior of i and i is senior of j

Second thing you need to do is for each element in the array you need the index of closest higher value number in left lind[i] and the index of closest higher value number in right rind[i].

Third thing you will need is the for each bucket B you need to store two values aff_junB[i] aff_senB[i] 0<=i<2^14, where aff_junB[i] implies because of this bucket how many time ith junior values get affected and aff_senB[i] denotes how many times ith senior gets affected. What I mean is if there were only 4 2’s in the bucket aff_junB1 = 4 aff_junB[0] = 4 aff_senB[3] = 4, aff_senB[6] = 4 etc…

4th thing you need is per bucket frequency of each element in the bucket within the bucket

Now loop through each element i in the array, there are four cases majorly based on rightMax index (rind) and leftMax index (lind) either both lind[i] and rind[i] are in the same bucket so do nothing since it is already covered in first step
lind[i]_BUC = i_BUC or rind[i]_BUC = i_BUC or otherwise

In all this you you use you above data. in simple for loops. For eg I will take the last case when (lind[i]_BUC != i_BUC and rind[i]_BUC != i_BUC)

You have all elements frequency in lbuc to ibuc say FreqItoL so for 0<=j<2^14 add value of (aff_senRtoI[j]+aff_junRtoI[j])*FreqItoL[j]*a[i] to final answer (Here aff_senRtoI is same as above aggregated over buckets from Ibuc to Rbuc. There are few corner cases since rind and lind are not at boundary of their buckets but you can also calculate it with the above gathered data.

My solution Its not that great looking but is doing what I stated above

3

i check it now! thank you for appraoch:)