Page 6 of 9

612 - WA

Posted: Sun Jan 21, 2007 6:28 pm
by ivanak
No matter what I do I get WA. I tried many inputs but for all of them i get correct output.. could anyone help me discovering a mistake?
I counted on multiple input and blanks between cases....

Code: Select all

#include <string>
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
typedef struct br1{
        int br, vr;
        string str;
}br;

br a[MAX];
int n, len, m;

int measure(string s){
    int sol = 0;

    for (int i = 0; i < (s.size()-1); ++i)
        for (int j = i+1; j < s.size(); ++j)
            if (s[i]>s[j]) ++sol;

    return sol;
}
bool cmp(struct br1 x,struct br1 y){
    return x.vr < y.vr;
}

int main(){
    cin >> n;

    for (int i = 0; i < n; ++i){
        cin >> len >> m;
            for (int j = 0; j < m; ++j){
                cin >> a[j].str;
                a[j].vr = measure(a[j].str);
            }

    sort(a, a+m, cmp);

    for (int j = 0; j < m; ++j)
        cout << a[j].str << endl;
    cout << endl;
    }

    return 0;
}

Posted: Sun Jan 21, 2007 9:00 pm
by daveon
Please use an existing thread for problem 612.

Posted: Tue Aug 21, 2007 10:29 am
by subzero
Hi, how are you??

I'm having problems with this problem...

with this code I got WA:

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>


using namespace std;

bool funcion (pair <int, string> a, pair <int, string> b){
	return a.first<b.first;
}
int main(){
	#ifndef ONLINE_JUDGE
		freopen("612.in","r",stdin);
		//freopen("10042.out","w",stdout);
	#endif
	int set,i,j,c,f;
	vector <pair<int, string> > lista;
	string cad;
	scanf("%d\n",&set);
	while(set--) {
		lista.clear();
		scanf("%*d %d\n",&f);
		while(f--) {
			cin>>cad;
			for (i=0,c=0;i<cad.length();i++) {
				for (j=i+1;j<cad.length();j++) {
					if(cad[i]>cad[j])
						c++;
				}
			}
			lista.push_back(pair <int,string> (c,cad));
		}
		
		sort(lista.begin(),lista.end(),funcion);
		for (i=0;i<lista.size();i++){
			cout<<lista[i].second<<endl;
			//cout<<lista[i].first<<"		"<<lista[i].second<<endl;
		}
		if (set!=0)
			printf("\n");
	}
	return 0;
}

but with this I got AC

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

bool funcion (pair <int, string> a, pair <int, string> b){
	
	return a.first<b.first;
}
int main(){
	#ifndef ONLINE_JUDGE
		freopen("612.in","r",stdin);
		//freopen("612.out","w",stdout);
	#endif
	int set,i,j,c,f;
	//vector <pair<int, string> > lista;
	vector <pair<int, int> >pos;
	vector <string> list;
	string cad;
	scanf("%d\n",&set);
	while(set--) {
		list.clear();
		pos.clear();
		scanf("%*d %d\n",&f);
		while(f--) {
			cin>>cad;
			for (i=0,c=0;i<cad.length();i++) {
				for (j=i+1;j<cad.length();j++) {
					if(cad[i]>cad[j])
						c++;
				}
			}
			list.push_back(cad);
			pos.push_back(pair <int,int> (c,list.size()-1));
		}
		
		sort(pos.begin(),pos.end());
		for (i=0;i<list.size();i++){
			cout<<list[pos[i].second]<<endl;
			//cout<<lista[i].first<<"		"<<lista[i].second<<endl;
		}
		if (set!=0)
			printf("\n");
	}
	return 0;
}
Both codes were made with the same idea, the difference is that in the WA-code I used a vector < pair<int, string> > to almacenate the strings and the number of flips, while in the AC-code I used 2 vectors: one for the strings and the other for the number of flips.

I have tested both codes with the same inputs and both generated the same output...

why de WA-code gives a WA??

thanx

Posted: Thu Aug 30, 2007 3:59 am
by subzero
ejem..ejem...

any idea??:roll:

thanks

Posted: Fri Oct 12, 2007 2:38 pm
by 898989
Hi subzero:

The problem said: "If two or more strings are equally sorted, list them in the same order they are in the input file."

This means sorting is not based only on our sawping count, but in case of tie, we will depend on the string position. In your first code, you forget this hint. BUT WHY YOUR CODE GIVES RIGHT ANSWERS EVEN IF THERE IS A TIE. Simply sort function from stl is not stable sorting. this means if two objects are equally, you should not assume they will be in their input order after sorting. So to solve your problem, we have one of 2 solutions
1) make our sort stable_sort() instead of sort() from sort. both in stl.
2) do like your second code, make a swapping count & index of string, when the sort, will find a tie between count, it will sort on the second element (the index).

For all people who still got WA.
1) Take care from above hints
2) input has repeated strings.

Hope this helps.

Posted: Wed Oct 17, 2007 2:09 pm
by sapnil
>> At first count the number of swap to sort each row
>> Sort them ascending order according to the number of swap of each row.

Thats all

Thanks
Keep posting
Sapnil

RE in acm612

Posted: Sun Dec 16, 2007 12:01 pm
by hridoy
Can anyone please tell me why I m getting RE in this program??

Code: Select all

#include<stdio.h>
#include<string.h>

void sort(char a[][50], int m, int n)
{
	int i,j,k,t,ar[100]={0};
	char b[100][50],temp,c[50];

	for(i=0;i<m;i++)
		strcpy(b[i],a[i]);
	
	for(k=0;k<m;k++)
		for(i=0;i<(n-1);i++)
			for(j=i+1;j<n;j++)
				if(b[k][i]>b[k][j])
				{
					temp=b[k][i];
					b[k][i]=b[k][j];
					b[k][j]=temp;
					ar[k]++;
				}
	
	for(i=0;i<m-1;i++)
		for(j=m-1;j>i;j--)
			if(ar[j-1]>ar[j])
			{
				t=ar[j];
				ar[j]=ar[j-1];
				ar[j-1]=t;
				strcpy(c,a[j]);
				strcpy(a[j],a[j-1]);
				strcpy(a[j-1],c);
			}
}

main()
{
	int i,j,n,m,N;
	char a[100][50];
	
	while(scanf("%d",&N)!=EOF)
	{
		printf("\n");
	
		for(i=1;i<=N;i++)
		{
			scanf("%d %d",&n,&m);
			
			for(j=0;j<m;j++)
				scanf("%s",a[j]);
			
			sort(a,m,n);
			
			for(j=0;j<m;j++)
				printf("%s",a[j]);
			
			printf("\n");
		}
	}
}

Posted: Sun Dec 16, 2007 12:58 pm
by mf
You need a buffer of size at least 51 to keep a string of length 50.

Re: 612 - DNA Sorting

Posted: Thu Dec 04, 2008 9:19 am
by abid_iut
I took help from the board and solve the problem
but it is shoeing WA
can any one pls tell me where is the problem in the code
here is the code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;


int count(char str[100],int n){
	int sum=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(str[i]>str[j])sum++;
		}
	}
	return sum;
}

int main()
{
	int N,n,m,i,j,t,store[100],line=0;
	char str[100][100],temp[100];
	cin>>N;
	while(N--){
		cin>>n>>m;
		for(i=0;i<m;i++){
			cin>>str[i];
			store[i]=count(str[i],n);
		}

		/*Bubble Sort*/

		for(i=0;i<m-1;i++){
			for(j=0;j<m-i-1;j++){
				if(store[j]>store[j+1]){
					t=store[j+1];
					store[j+1]=store[j];
					store[j]=t;
					strcpy(temp,str[j+1]);
					strcpy(str[j+1],str[j]);
					strcpy(str[j],temp);
				}
			}
		}
		for(i=0;i<m;i++)cout<<str[i]<<endl;
		if(line<N)cout<<endl;
		line++;
	}
	return 0;
}
pls help

Re: 612 - DNA Sorting

Posted: Thu Dec 04, 2008 4:21 pm
by mf
Quote from the problem statement:
Output:
Print a blank line between consecutive test cases.
That means there should be no blank lines after the output for the last test case.

Re: 612 - DNA Sorting

Posted: Thu Dec 04, 2008 8:19 pm
by abid_iut
I solved that problem but still WA
is there any other mistake
pls anyone check the code again and help :(

Re: 612 - DNA Sorting

Posted: Thu Dec 04, 2008 8:40 pm
by mf
abid_iut wrote:I solved that problem
No, you didn't. Try again.

Re: 612 - DNA Sorting

Posted: Fri Dec 05, 2008 9:51 am
by abid_iut
Sorry and Thankx
I made a silly mistake, now AC
anyway thankx again

Re: 612 - DNA Sorting

Posted: Tue Feb 17, 2009 7:39 am
by Obaida
I got Acc.. :D

Re: 612 - DNA Sorting without SORTING

Posted: Sat Oct 31, 2009 12:36 am
by george3456
One of my solution is accepted. But it is taking almost 2.4s which is longer. So I tried to reduce the time. In the following approach I tried not to use any sorting....... but this code is getting RTE. do you have any idea???

Code: Select all

#include<stdio.h>
#include<string.h>

int main()
{
	int tcase;
	
	scanf("%d",&tcase);

	getchar();
	getchar();

	while(tcase--)
	{

			char s[100],loc[1500][105][55]={0};
			long size, looper,i,j,len,count=0,m,n;

			scanf("%ld %ld",&n,&m);
			getchar();

			for(looper = 0;looper<m;looper++)
			{
				gets(s);
				count = 0;
				len = strlen(s);

				for(i=0;i<len;i++) // calculating the sorted value
					for(j=i+1;j<len;j++)
						if(s[i]>s[j])
							count++;
					
				size = count;
				count = 0;

				if(loc[size][count][0]) //if that location is not empty....
					while(loc[size][count][0])
						count++;
				
				strcpy(loc[size][count],s);
			}

			for(i=0;i<1500;i++)
				for(j=0;loc[i][j][0];j++)
					printf("%s\n",loc[i][j]);

			if(tcase>=1)
				printf("\n");
	}
	return 0;
}