Betlista's blog

By Betlista, 10 years ago,

Counting map is special map used for counting things — values in map are integers. In Java it could be (first type, the one for key, could be something else):

Map<String, Integer> map = new HashMap<String, Integer>();


When incrementing counts I'm using this code(using tricks with autoboxing):

String s = ...; // we have value
Integer cnt = map.get( s );
map.put( s, cnt == null ? 1 : ++cnt );


When decreasing count I'm using (in most cases decresing is not needed):

String s = ...; // we have value
int cnt = map.get( s );
if ( cnt == 1 ) map.remove( s );
else map.put( s, --cnt );


Problems where counting map could be helpful:

On the other hand there are other aproaches to solve same problems, for example when you need to count characters, more effective solution is char[], but maps are my favourite data structure 0:-), but ones in TopCoder SRM the performace was a big issue that caused that my solution failed in system test (TLE).

• +20

 » 10 years ago, # |   +18 Hello guys, if you do not like this blog entry I would like to know why, really ;-)I know that it is quite simple. My rating is not high, but I think it could help to someone.
•  » » 10 years ago, # ^ |   +6 Oh, it was nice, your tutorials are pretty much useful, I guess Codeforces should have an fixed place, to all Tutorials and Editorials;
 » 10 years ago, # | ← Rev. 2 →   +15 It's also a good way to compress coordinates (did I express this term correctly?..)If we need to compress an array A, than we can do that in three steps: int A[N]; // ...blah-blah-blah, A is filled with some big numbers map M; for (int i = 0; i < n; i++) M[A[i]]; // 1. Creating a key A[i] in M int pt = 0; for (map::iterator it = M.begin(); it != M.end(); it++) it->second = pt++; // 2. Assigning unique value for each key keeping order in set of values for (int i = 0; i < n; i++) A[i] = M[A[i]]; // 3. Compressing source array That's good way because if we need to put points in some special cases, like they are ends of some segments, we can just call something like M[A[i] — 1], M[A[i]], M[A[i] + 1] instead of thinking what we should put as A[i], what as A[i] + 1 etc...
 » 10 years ago, # |   0 HiThanks for your tutorials. I generally using c++, I using Java (with IdeOne ) if I have to use BigInteger (but I feel I don't use BigIntegers in the natural way, I feel there definitions and usage hard, maybe it's my fault). So I would really happy if you write a tutorial about BigInteger or any area where Java know something that c++ don't. :)