484 - The Department of Redundancy Department

[Raiyan Kamal]

I assumed that no number will be less than -8000 and bigger than 8000. Hope this will help you.

[frankhuhu]

[cpp]
Here is my code. I don't know what's wrong? Who can help me?

#include <iostream.h>
#include <stdio.h>
#include <math.h>
#include <cctype>

int get(char *p,int *q)
{
int i,num=1,jumdata=0;
for (i=0;p!='\0';i++)
if (p==' ' && p[i+1]!=' ') num++;
int t=0,flag=1,cnt=0;
i=0;
while (1)
{
if (p == '\0') break;
if (p == '-') {flag=-1;i++;continue;}
else if (isdigit(p))
t = (t*10) + (p-'0');
else if (p==' ' && p[i+1]!=' ')
{
q[jumdata++] = flag*t;
t = 0;
flag = 1;
}
i++;
}
q[jumdata++] = flag*t;
return num;
}

int main()
{
char buf[100000];
int coe[10000];
bool flag[10000];
while (cin.getline(buf,100000))
{
int i,a;
a=get(buf,coe);
for (i=0;i<a;i++)
flag=true;
for (i=0;i<a;i++)
{
int cnt=0;
if (flag==true) cout<<coe<<' ';
if (flag[i]==false) continue;
for (int j=i;j<a;j++)
{
if (coe[j]==coe[i])
{
cnt++;
flag[j]=false;
}
}
cout<<cnt<<endl;
}
}
return 0;
}
[/cpp]

[A1]

you can not assume that input will be in one line.

[ahmed hasan]

PLZ HELP!!!

Code: Select all

#include<cstdio>
#include<cstring>
#define max 90000000

char s[max];
int  i[max];
int  freq[max];
int  n;

int main()
{
	char *st;
	int *f=freq+(max/2);
	while(gets(s))
	{
		st=s;
		n=0;
		while(1)
		{
			while(*st==' ')st++;
		    if(*st=='\0')break;
			sscanf(st,"%d",&i[n++]);
			while(*st!=' ' && *st!='\0')st++;
		}

		for(int c1=0;c1<n;c1++)
			*(f+i[c1])+=1;

		for(int c2=0;c2<n;c2++)
			if(*(f+i[c2])!=0)
			{
				printf("%d %d\n",i[c2],*(f+i[c2]) );
				*(f+i[c2])=0;
			}
	}
	return 0;
}

[mohiul alam prince]

hi
I think this a one input problem.

MAP

[Cruzer]

I created one solution to this problem that generates TLE, so I worked out another solution, but that one generates MLE. I can't find any way to do this within the time and memory limits.
My first solution uses 2 arrays, the first to store all unique integers in the input order, the other to store the corresponding number of occurrences of each integer. The problem here is that to change the occurrences, I have to search through my unsorted integer array (which is taking all the time I think). I can't sort the array because then I lose the input order. I've tried everything I can think of to speed it up. Here is the code for solution #1:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
int find( int* arr, int size, int target );
main() {
    register int input[7500];
    register int occurrences[7500];
    int input_count = 0;
    int input_int, temp;
    register int i;
    int duplicates;
    
    /* Init occurrences */
    for ( i = 7499; i >= 0; i-- ) {
        occurrences[i] = 1;
    }
    
    /* Insert all input  */
    while( scanf("%d", &input_int) ) {
        duplicates = find( input, input_count, input_int );
        if( duplicates != -1 ) {
            occurrences[duplicates] += 1;
        }
        else {
            input[input_count] = input_int; 
            input_count++;
        }
    }
    
    /* Print results */
    for( i = 0; i < input_count; i++ ) {
        printf("%d %d\n", input[i], occurrences[i]);
    }
}

int find( int* arr, int size, int target ) {
    register int i;
    for( i = size - 1; i >= 0; i--) {
        if( arr[i] == target ) {
            return i;
        }
    }
    return -1;
}

My second solution was designed to be faster at searching. I made one array of integers in the input order as before. I also made a binary search tree that held those integers and their occurrence count. Unfortuntately, with something like 7500 unique integers, I go over 32mb of memory because i have 7500 integers in the array, and 7500 nodes (each comprising of an int, a short (the count), and 2 pointers). I tried to lower memory usage here as well to no avail. Here is the code to solution #2:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

/* BST Node structure */
typedef struct node {
    int data;
    short count;
    struct node* left;
    struct node* right;
} BST_node_t;

/* BST Structure */
typedef struct {
    BST_node_t* root;
} BST_t;

/* Function Prots */
void init( BST_t* tree );
short insert( BST_t* tree, int item );
short find( BST_t* tree, int target );

main() {
    int input[7500];
    int input_count = 0;
    int input_int, temp;
    int i, duplicates;
    BST_t tree;
    
    init(&tree);
    
    /* Insert all input into BST */
    while( scanf("%d", &input_int) ) {
        duplicates = insert( &tree, input_int );
        if( duplicates == 1 ) {
            input[input_count] = input_int;
            input_count++;
        }        
    }
    
    /* Print results */
    for( i = 0; i < input_count; i++ ) {
        printf("%d %d\n", input[i], find(&tree, input[i]));
    }
}


/* BST STUFF */
void init( BST_t* tree ) {
    tree->root = NULL;
}

short insert( BST_t* tree, int item ) {
    BST_node_t *newNode;
    BST_node_t *currentNode;
    BST_node_t *parentNode;
    int direction = 0;
    
    /* Create the new node */
    newNode = (BST_node_t *)malloc( sizeof(BST_node_t) );
    newNode->data = item;
    newNode->count = 1;
    newNode->left = NULL;
    newNode->right = NULL;
    
    /* If tree is empty make root point to new node */
    if( tree->root == NULL ) {
        tree->root = newNode;
    }
    /* Find insertion point for new node */
    else {
        currentNode = tree->root;
        while( currentNode != NULL ) {
            if( currentNode->data == item ) {
                currentNode->count = currentNode->count + 1;
                return currentNode->count;
            }
            else if( currentNode->data < item ) {
                parentNode = currentNode;
                currentNode = currentNode->right;
                direction = 1;
            }
            else {
                parentNode = currentNode;
                currentNode = currentNode->left;
                direction = 0;
            }
        }
        
        if( currentNode == NULL ) {
            if( direction == 1 ) {
                parentNode->right = newNode;
            }
            else {
                parentNode->left = newNode;
            }
        }
    }
    
    /* Return the count of the inserted item */
    return newNode->count;
}

short find( BST_t* tree, int target ) {
    BST_node_t *currentNode;
    currentNode = tree->root;
    
    while( currentNode->data != target ) {
        if( currentNode->data > target ) {
            currentNode = currentNode->left;
        }
        else {
            currentNode = currentNode->right;
        }
    }
    return currentNode->count;
}

Any ideas or hints would be greatly appreciated thanks!

[mohiul alam prince]

hi
in your first code just change
while( scanf("%d", &input_int) == 1)
and get AC

MAP

[Cruzer]

Thanks, that worked.

[Rocky]

I Just Solve It.And I Astonised To See That About The Time.Some Body Solve In 0.00 Second.But My Programm Takes More Time.How Can Solve It In 0.00 Second.What Is The Way.Can Any Body Help Me With The Algorithm????

THANK'S IN ADVANCE
ROCKY

[dumb dan]

First of all you should note that both "Scott E August" and "Ivor L66bas" have more than 100 submissions for every solved problem. What they do is they "probe" the judge input. When you know what input there will be, it's much easier to write a program that will get a quick AC.

If you ask me this is highly immature and I feel a bit sorry for UVA who saves every submission sent to them from these guys. Trying to match their times is just stupid since their submissions don't truly solve the problem.

If you still want to know how to do this problem faster, explain your algorithm and perhaps someone can make a suggestion on how to improve it.

[CDiMa]

First of all you should note that both "Scott E August" and "Ivor L66bas" have more than 100 submissions for every solved problem. What they do is they "probe" the judge input. When you know what input there will be, it's much easier to write a program that will get a quick AC.

If you ask me this is highly immature and I feel a bit sorry for UVA who saves every submission sent to them from these guys. Trying to match their times is just stupid since their submissions don't truly solve the problem.

Actually Scott and Ivor solved all their AC problems with fast times. They spent hundreds of submissions trying to optimize their code and squeezing every cycle of CPU to make their program work faster. They did this by improving the algorithm, using custom, buffered, optimized I/O routines and writing some routines directly in assembler.

Probably is questionable wether the objective of the OJ is to specialize to solve a single problem in the absolute fastest way possible rather than to solve the maximum number of problems with solutions just as fast as needed to get AC within time limit.
Or maybe is questionable to use assembler code embedded in C code rather than using pure C, Java or Pascal code. You could argue that's unfair rewriting I/O routines instead of using the ones provided by the language.

But you can't say that their submissions don't solve the problem.

I learned a lot trying to improve my runtimes to such high standards.
In many cases I simply tried to improve my algorithms and found out that there were ways to make my program 20x times faster without needing to use fast I/O and assembler routines.
I learned when it's worth improving the I/O speed and when it's pointless.
And I learned to distinguish when a solution takes 0.00 on the OJ because it's a printf solution or because the author of the solution is a skilled programmer.

It's up to you if you want to improve your optimizing skills or not, but it's sure that optimizing within the rules posed by the OJ is a programming skill.

Ciao!!!

Claudio

[dumb dan]

Of course they also do a lot of fair optimizing and of course they are good programmers.

Maybe you know something I don't, but I think their submission stats speak for themselves. If they wanted to optimize their code they could do it on their own machines (I'm certain they are more than capable of this).

The only reason I see for any of those two to spend more than 100 submissions on the same problem trying to get a better time, is to see how it reacts on the judge input data (in other words probing it).

[CDiMa]

Of course they also do a lot of fair optimizing and of course they are good programmers.

Maybe you know something I don't, but I think their submission stats speak for themselves. If they wanted to optimize their code they could do it on their own machines (I'm certain they are more than capable of this).

This is not true for the OJ. I applied in many occasion optimizations that worked faster on my machine but were actually slower when submitted to the OJ. When you are trying to shave a millisecond from the runtime of your program, many variables come into play that usually you don't have to consider.
Not only the version of the compiler, but also the OS (kernel and libs), the CPU, bus speed of the motherboard, speed of the host controller and disks, cache size can make a real difference in the effectiveness of a singular optimization.
It's not that easy to reproduce the OJ environment.

You can also see from the stats that not only they made hundreds of submissions for every problem solved, they also have hundreds of AC submissions.
Is it probing to submit a hundred AC programs? I don't think so.

Ciao!!!

Claudio

[Rocky]

Thank's Every one For reply
Now I Explain My Algorithm:

I Take A 3 Big Array One For INput,One For Sorted Input & Another For Count The Repeatation .Then Take The INPUT To The Input & Sorted Input Array And Direct Incress The Counter In The Counter Array.
That Is If The 3.i Take It To Input array & To The Sorted Array And Incress counter[3]++;
After This I Sort The Sorted Array & Remove All The Duplication From Sorted Array And Then After Checking I Print The Result From The Counter Array.

Now What Is The Efficient Way.

Thank's In Advance
Rocky

[dumb dan]

> That Is If The 3.i Take It To Input array & To The Sorted Array And Incress counter[3]++;

What do you mean by this?
Do you mean if the input is '3' you increase counter[3]++;?
Or do you mean that if the input number is equal to the fourth element of the input array (element inpt[3]) you increase counter[3]++;?
Or do you mean something else??

This problem can be solved in O(n log n). Or faster if input is nice, but we have no reason to believe input is nice. Of my two guesses above of what you mean, the first would lead to horrible complexity if input isn't nice and the second would lead to complexity O(n^2).