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:
- 37A Towers
- 113B Opposites Attract
- 127B Canvas Frames
- 4C Registration System
- 50B Choosing Symbol Pairs
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).
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.
Oh, it was nice, your tutorials are pretty much useful, I guess Codeforces should have an fixed place, to all Tutorials and Editorials;
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:
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...
Hi
Thanks 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. :)