Here is one problem idea that I have. I do have a slight feeling that this might be a very standard or direct question. Please give feed back or suggestions to improve the question.
Here is the basic statement.
Given an array of 10^5 positive numbers ( each no. <= 10^5 ). and 10^5 queries of the form M L R.
output
aL%M + a(L+1)%M … aR%M.
Hey Sundar,
What I felt is that, this problem is too standard, and also I remember(vaguely), Ajay and me discussing some problem from some OJ which involved this as a sub-problem (I could search for where it occurred problem if you need).
Also, I’m not sure if this exact problem has already occurred somewhere.
We could keep this as a substitute problem though, or even develop on this and make it difficult. What do you think ?
^agreed, its standard. ( -_- editing the wrong suggestion)
@Anmol Ya… I also agree that it might be standard. We can keep this is for worst case as substitute i guess. If possible give me the link of that problem. It would help in modifying this question.
@ mohit Can you explain how to do without segment trees? . I could not think of anyway without using segment trees.
@sundar is it just not (sum[r] - sum[l-1]) % M. Where sum[i] = sum{a[0]…a[i]}
@anudeep no. For a = 100 150 200 300 and query = 150 1 4 answer is 100+ 0+ 50+ 0 = 150
Hey,
I had a Nsqrt(N)logN solution mind, which works for M <= 10^5.
It basically, is for M < sqrt(N), initially store mod of every element, and then later just do a range sum.
For M >= sqrt(N), do queries in form [0,M-1],[M,2M-1]…
For [Mi,M(i+1)-1] query, if count is c and sum is s, add sum - c(M*i) and so on…
And we’ll compute all queries offline.
I discussed different approaches to solve this problem with sundar then,
Sundar has a similar but less complex approach he said.
But now I feel, we should keep this in the problem set. What do you guys think ?
Also, does someone have a different approach maybe, or can we make this problem more tuff.
The best solution I have is O( N * sqrt( N * log N ) ). It is very similar to what is described above, just a different block size. I have one solution that is offline and another that is online. So you could as well add an update operation (change A[i] to X) if you want to make contestants avoid offline solution.
Even I had this block size in mind.Can you explain your online solution? I could not think of one. Also I think(not sure) we can add update a[i] = x and still do it offline by rebuilding the segment tree and calculating answers for queries whenever no. of queries added reaches N or no. of updates reaches sqrt(N).
I’d like to be the tester for this question.
@Sundar, could you give me the input format, and the exact constraints. Also, in the meantime, could you also start preparing the statement and the test-data.
Input format.
1 st line contains no. of test cases T.
For each test case
1st line contains an integer N <= 10^4
Next line contains N integers representing the array A.
3rd line contains M the no. of queries ( <= 10^4)
Next M lines contain queries. each are either of the form
1 L R MOD( find answer from L to R with modulo MOD)
2 i val ( set a[i] = val )
1 <= L <= R <= N
1 <= i <= N
1 <= val <= N.
T <= 20