I have been trying to understand this code, but still don't get the idea of the implementation.

The question that I am interested in is: Given an integer array, answer queries of the form (li, ri) by returning the number of distinct integers in that subarray. The code that I posted is a solution to the stated problem, plus an additional condition, but I only care for this subproblem.

I thought of an offline solution that answers queries in log n time each — Process each integer value in the array, and create a new interval for each pair of equal value integers that are "close" to one another. E.g. [1,x,x,1,x,1], x != 1 -> when I am processing the value 1, I will create two intervals (0,3), (3,5) Then, the answer to each query is the (ri-li+1) — number of intervals that are within (li, ri)

I could only think of an offline solution to this modified problem using BIT.

The solution from the code seems to handle the queries online. Can anybody help me understand the code?

Thanks!!

I have been struggling with a problem that involves DP. Usually, for dp problems, it's enough for me to just create arrays like int[][][][] dp, where a state can be indexed by the value of 4 integers. Just to be very concrete, let's say that dp[a][b][c][d] stores the minimum time to eat 'a' food of type 1, 'b' food of type 2, and so on. However, if the problem statement states that the amount of each food type ranges from 0 to 1000, it's no longer possible to store the table. But what if.. the restriction is that a+b+c+d <= 1000?

I use Java, and I tried using a Map. I made a wrapper class called Key that just stores int[4] foodAmounts, overrode hashCode, equals, and this allows me to have Map<Key, Integer> to store my dp values. However, whenever I want to access the map, I would have to create a new Key object. I might have to create multiple Key objects that correspond to the same array, and this eats up the memory. Is there a way to reuse these Key objects? E.g a function Key toKey(int[] arr) that returns the same object instance when given equivalent arrays.

I thought that solving this problem requires me to create a Map that stores a mapping between int[]arr and its unique Key object... but isn't this a recursive problem then? Since I need to make a Key out of int[] arr...

Thanks!

http://codeforces.net/problemset/problem/282/B

I thought of a slight modification to the problem to be "How many solutions are there", where a solution is defined as a string like "AGA".

-------------------my (possibly incorrect) approach

Due to the nice property of this problem, I think this is the sum from i= lo to hi of (n choose i) where lo = Math.ceil((aSum-500.0)/1000.0), and hi = Math.floor((aSum+500.0)/1000.0)

I found it really interesting that the permutation of A's and G's don't matter as long as number of G is in between lo and hi. Or maybe it's just because I'm slow and easily amused lol. Proof:

|sum a — sum g| <= 500

but sum g = sum a in B of(1000-ai)

|A — |B| 1000|<=500 -> then get lower and upper bound for B

where B is the set that you choose 'G' to have, and A is the sum of all values of ai

lol messy notations, but yeah

Not really the point of this problem, but is there a good way to calculate sum of combinations in sequence? Like sum from i=0 to j of (N choose i)