612 - DNA Sorting

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ivanak
New poster
Posts: 1
Joined: Sun Jan 21, 2007 6:15 pm

612 - WA

Post by ivanak » Sun Jan 21, 2007 6:28 pm

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sun Jan 21, 2007 9:00 pm

Please use an existing thread for problem 612.

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

Post by subzero » Tue Aug 21, 2007 10:29 am

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
There is no knowledge that is no power.

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

Post by subzero » Thu Aug 30, 2007 3:59 am

ejem..ejem...

any idea??:roll:

thanks
There is no knowledge that is no power.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Fri Oct 12, 2007 2:38 pm

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.
Sleep enough after death, it is the time to work.
Mostafa Saad

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Wed Oct 17, 2007 2:09 pm

>> 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
"Dream Is The Key To Success"

@@@ Jony @@@

hridoy
New poster
Posts: 21
Joined: Tue May 08, 2007 10:30 am
Location: Dhaka
Contact:

RE in acm612

Post by hridoy » Sun Dec 16, 2007 12:01 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Dec 16, 2007 12:58 pm

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

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 612 - DNA Sorting

Post by abid_iut » Thu Dec 04, 2008 9:19 am

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
Last edited by abid_iut on Thu Dec 04, 2008 8:21 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 612 - DNA Sorting

Post by mf » Thu Dec 04, 2008 4:21 pm

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
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 612 - DNA Sorting

Post by abid_iut » Thu Dec 04, 2008 8:19 pm

I solved that problem but still WA
is there any other mistake
pls anyone check the code again and help :(
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 612 - DNA Sorting

Post by mf » Thu Dec 04, 2008 8:40 pm

abid_iut wrote:I solved that problem
No, you didn't. Try again.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 612 - DNA Sorting

Post by abid_iut » Fri Dec 05, 2008 9:51 am

Sorry and Thankx
I made a silly mistake, now AC
anyway thankx again
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 612 - DNA Sorting

Post by Obaida » Tue Feb 17, 2009 7:39 am

I got Acc.. :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

george3456
New poster
Posts: 5
Joined: Tue Sep 15, 2009 11:16 am

Re: 612 - DNA Sorting without SORTING

Post by george3456 » Sat Oct 31, 2009 12:36 am

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;
}
The most important thing is never stop questioning ~ Albert Einstein

Post Reply

Return to “Volume 6 (600-699)”