612 - DNA Sorting

[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;
}

[daveon]

Please use an existing thread for problem 612.

[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

[subzero]

ejem..ejem...

any idea??:roll:

thanks

[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.

[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

[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");
		}
	}
}

[mf]

You need a buffer of size at least 51 to keep a string of length 50.

[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

[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.

[abid_iut]

I solved that problem but still WA
is there any other mistake
pls anyone check the code again and help

[mf]

I solved that problem

No, you didn't. Try again.

[abid_iut]

Sorry and Thankx
I made a silly mistake, now AC
anyway thankx again

[Obaida]

I got Acc..

[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;
}