UVA – 484 – The Department of Redundancy Department

    1. you can solve it using a map to map the number with it frequency and a vector indicating their order.
    2. or you can use it using an O(1) access solution by making adding a large displacement to the number ( as the input may contain negative numbers) this is supposed to remove the log N factor.
    •  but it seems for this problem that the number of distinct numbers is much much less than the input size. so the log n factor is incomparable to the cost of traversing through them all again.
#include <stdio.h>
#include <string.h>
#define MAX 1000002
int c[2 * MAX];
int Ns[2 * MAX];
int main() {

	int N, S = -1, i;
	for (i = 0; i < 2*MAX; ++i)
		c[i] = 0;
	while (scanf("%d", &N)==1) {
		Ns[++S] = N + MAX;
		++c[N + MAX];
	}

	for (i = 0; i <= S; ++i) {
		if (!c[Ns[i]]) continue;
		printf("%d %d\n", Ns[i] - MAX, c[Ns[i]]);
		c[Ns[i]] = 0;
	}
	return 0;
}
Advertisements

One thought on “UVA – 484 – The Department of Redundancy Department

  1. emtiaz says:

    I found ur map and vector technique useful 🙂

    #define M 1000002
    using namespace std;
    
    int main() {
    
    	int n, j;
    	vector v, x;
    	map m;
    	j = 0;
    	while (scanf("%d", &n) != EOF) {
    		if (j != 0 && count(v.begin(), v.end(), n) == 0)
    			v.push_back(n);
    		if (j == 0)
    			v.push_back(n);
    
    		m[n] += 1;
    		j++;
    	}
    	for (int i = 0; i < v.size(); i++) {
    		printf("%d %d\n", v[i], m[v[i]]);
    	}
    
    	return 0;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: