612 - DNA Sorting

[IRA]

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

typedef struct _node
{
char s1[101];
int ex;
}NODE;

NODE data[1000];
NODE temp;

int main()
{
int num,len,row;
int i,j,m,n,count;
string s2;
char te;
while( cin>>num )
{
for(j=0;j<num;j++)
{
cin>>len>>row;
for(i=0;i<row;i++)
{
cin>>data.s1;
s2=data.s1;
count=0;
for(m=0;m<len-1;m++)
for(n=0;n<len-m-1;n++)
if(s2[n]>s2[n+1])
{
te=s2[n];
s2[n]=s2[n+1];
s2[n+1]=te;
count++;
}
data.ex=count;
}

for(m=0;m<row-1;m++)
for(n=0;n<row-m-1;n++)
if(data[n].ex>data[n+1].ex)
{
temp=data[n];
data[n]=data[n+1];
data[n+1]=temp;
}

for(i=0;i<row;i++)
cout<<data.s1<<endl;
cout<<endl;

}
}





return 0;
}

Code: Select all

How could i speed up my program!?
Please give me a hint!
I always got TLE!

[IRA]

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

typedef struct _node
{
	char s1[101];
	int ex;
}NODE;

NODE data[1000];
NODE temp;

int main()
{
	int num,len,row;
	int i,j,m,n,count;
	string s2;
	char te;
	while( cin>>num )
	{
		for(j=0;j<num;j++)
		{
			cin>>len>>row;
			for(i=0;i<row;i++)
			{
			 cin>>data[i].s1;
			 s2=data[i].s1;
			 count=0;
		     for(m=0;m<len-1;m++)
				 for(n=0;n<len-m-1;n++)
					 if(s2[n]>s2[n+1])
					 {
						te=s2[n];
						s2[n]=s2[n+1];
						s2[n+1]=te;
						count++;
					 }
			 data[i].ex=count;
			}

		     for(m=0;m<row-1;m++)
				 for(n=0;n<row-m-1;n++)
					 if(data[n].ex>data[n+1].ex)
					 {
						temp=data[n];
						data[n]=data[n+1];
						data[n+1]=temp;
					 }

			for(i=0;i<row;i++)
				cout<<data[i].s1<<endl;
			    cout<<endl;

		}
	}





	return 0;
}

How could i speed up my program!?
Please give me a hint!
I always got TLE!

[mamun]

The first line of the input is an integer M, then a blank line followed by M datasets.

So don't wait for EOF. Read num just once and read for num number of input sets.
You can use quicksort for the second sorting.

[IRA]

The first line of the input is an integer M, then a blank line followed by M datasets.

So don't wait for EOF. Read num just once and read for num number of input sets.
You can use quicksort for the second sorting.

I read num just once!
Ans I use quicksort for the second sorting.
But,I still got TLE!!
Who can give me a hint!
Thanks in advanced!!

Code: Select all

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

using namespace std;

typedef struct _node
{
	int ex;
	char s1[101];
}NODE;

NODE data[1000];
NODE temp;

bool cmp(struct _node a,struct _node b)
{
	return a.ex<b.ex;
}


int main()
{
	int num,len,row;
	int i,j,m,n,count;
	string s2;
	char te;
    cin>>num;
	
		for(j=0;j<num;j++)
		{
			cin>>len>>row;
			for(i=0;i<row;i++)
			{
			 cin>>data[i].s1;
			 s2=data[i].s1;
			 count=0;
		     for(m=0;m<len-1;m++)
				 for(n=0;n<len-m-1;n++)
					 if(s2[n]>s2[n+1])
					 {
						te=s2[n];
						s2[n]=s2[n+1];
						s2[n+1]=te;
						count++;
					 }
			 data[i].ex=count;
			}

			sort(data,data+row,cmp);
		     //for(m=0;m<row-1;m++)
			//	 for(n=0;n<row-m-1;n++)
			//		 if(data[n].ex>data[n+1].ex)
			//		 {
			///			temp=data[n];
			//			data[n]=data[n+1];
			//			data[n+1]=temp;
			//		 }

			for(i=0;i<row;i++)
				cout<<data[i].s1<<endl;
			    cout<<endl;

		}
	





	return 0;
}

[IRA]

This code too slow.
I change this code and got AC!
Thanks!

Code: Select all

           for(m=0;m<len-1;m++) 
             for(n=0;n<len-m-1;n++) 
                if(s2[n]>s2[n+1]) 
                { 
                  te=s2[n]; 
                  s2[n]=s2[n+1]; 
                  s2[n+1]=te; 
                  count++; 
                } 

[plankton97330]

Can anyone tell me why i got TLE?

Code: Select all

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
bool f(pair<int,string> a , pair<int,string> b)
{
  return a.first < b.first;
}
int main(){
  int N,n,l,c;
  vector< pair<int,string> > m;
  string s;
  cin >> N;
  while(N--){
    m.clear();
    cin>>l>>n;
    for(int k=0; k<n; k++){
      cin>>s;
      c = 0;
      for(int i=0; i<l-1; i++){
        for(int j=i+1; j<l; j++){
          if(s.at(i)>s.at(j))
            c++;
        }
      }
      m.push_back(make_pair(c,s));
    }
    stable_sort(m.begin(), m.end(), f);
    for(int i=0;i<n; i++)
      {
        cout<<m[i].second<<endl;
      }
    cout<<endl;
  }
  return 0;
}

[ranban282]

Your sorting method is plain and simple O(n^2). Insertion sort is O(number of inversions). There are probably many test cases where the inversions is much less than n^2.

[jojo]

Can anyone help me ? I tried all inputs from board for this program and it gets everything right. I don't know what is wrong with it.
heeelp plx
here is my code

Code: Select all

#include<cstdio> 
 #include<algorithm> 
 #define MAXAMOUNT 105 
 #define MAXLENGHT 55 
 using namespace std; 
 char array[MAXAMOUNT][MAXLENGHT]; 
 int lenght,amount; 
 struct DNA 
 { 
         int Which; 
         int HowMany; 
 }; 
 DNA unsortednesses[MAXAMOUNT]; 
 void unsortedness(int level) 
 { 
         int counter=0; 
         for(int i=0; i<lenght; i++) 
         { 
                 char letter=array[level][i]; 
                 for(int j=i+1;j<lenght; j++) 
                         if(array[level][j]<letter) 
                                 counter++; 
         } 
         unsortednesses[level].HowMany=counter; 
         unsortednesses[level].Which=level; 
 } 
 bool cmp(DNA a, DNA b) 
 { 
         return a.HowMany<b.HowMany; 
 } 
 void input() 
 { 
         int cases; 
         scanf("%d\n",&cases); 
         for(int i=1; i<=cases; i++) 
         { 
                 scanf("%d%d\n",&lenght,&amount); 
                 for(int k=0; k<amount; k++) 
                 { 
                         scanf("%s",array[k]); 
                         unsortedness(k); 
                 } 
                 sort(unsortednesses,unsortednesses+amount,cmp); 
                 for(int k=0; k<amount; k++) 
                 { 
                         int level=unsortednesses[k].Which; 
                         for(int j=0; j<lenght; j++) 
                                 printf("%c",array[level][j]); 
                         printf("\n"); 
                 } 
                 scanf("\n"); 
                 if(i<cases) 
                         printf("\n"); 
         } 
 } 
 main() 
 { 
         input(); 
         return 0; 
 } 

[brahle]

Hi! I tried to solve problem 612 (DNA Sorting), but I got OLE. Can someone help me?
This is my code:

Code: Select all

CUT AFTER ACC

sorry, i'm just stupid .

[Donotalo]

I'm getting presentation error. My output code looks like this:

Code: Select all

for (i = 0; i < size; i++)
	cout << array[i].str << endl;

size is the number of strings and array is sorted according to the problem. please help me to get rid from this presentation error. i also tried:

Code: Select all

for (i = 0; i < size; i++)
	cout << array[i].str << endl;
cout << endl;

but still presentation error.

[Hackson]

The last case should not have blank line at the end. Try it.

[Donotalo]

this solves the problem. thanks.

[Uttam Dwivedi]

I run this program for all type of input and it is giving correct answer,
but on submition it shows WA.

i tried several times ... but cant find out the bug...
plzz help me ...

the code is.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

struct data{string sa;
int counti;
};

bool operator < (const data& a, const data& b)
{return a.counti<b.counti;
}

int main()
{
int n,i=0;
cin>>n;
cout<<endl;
while(i++<n)
{int m,b;
cin>>m>>b;
vector<data> a;
int j=0;
while(j<b)
{string s(m,'a');
int count=0;
cin>>s;
for(int g=0;g<s.size()-1;g++)
{for(int h=g+1;h<s.size();h++)
{if(s[h]<s[g])
count++;
}
}
data sb;
sb.sa=s;
sb.counti=count;
a.push_back(sb);

j++;
}
sort(a.begin(),a.end());
for(int g=0;g<b;g++)
cout<<a[g].sa<<endl;
if(i!=n)
cout<<endl;
}


return 0;


}


[/b]

[pankaj trivedi]

You did not empty the vector a . You need to erase the vector when it is of no use . so at the end of loop you can use

Code: Select all

a.erase(a.begin() ,a.end())

Even if you overcome with the wrong answer you code will result in TLE because of n^2 bubble sort so think of some other efficient method for sorting like quick sort or insertion sort in this case [;)]

[m2lajoo]

hi please help me my problem is good in my computer but it got TLE
here is mycode:





type
st100=array[1..100]of string;
arr100=array[1..100]of integer;
var
test:integer;
counter:integer;
j,i,tedad,len:integer;
strings,strings2:st100;
number:arr100;
function translate_number(st:string):string;
var
i:integer;
javab:string;
begin
javab:='';
for i:=1 to length(st) do
begin
if st='A' then
javab:=javab+'1';
if st='C' then
javab:=javab+'2';
if st='G' then
javab:=javab+'3';
if st='T' then
javab:=javab+'4';
end;
translate_number:=javab;
end;
procedure sort(var st:string);
var
b,i,j:integer;
mystr:string;
temp:char;
error,x,y:integer;
begin
b:=1;
mystr:=st;
while b=1 do
begin
b:=0;
for i:=1 to length(st)-1 do
begin
val(mystr,x,error);
val(mystr[i+1],y,error);
if x>y then
begin
b:=1;
temp:=mystr;
mystr:=mystr[i+1];
mystr[i+1]:=temp;
counter:=counter+1;
end;
end;
end;
st:=mystr;
end;
procedure sort2(var x:arr100;left,right:integer);
var
i,j,item,temp:integer;
tempstr:string;
begin
i:=left;
j:=right;
item:=x[(left+right) div 2];
repeat
while (x<item)and(i<right) do
i:=i+1;
while (item<x[j])and(j>left) do
j:=j-1;
if i<=j then
begin
temp:=x;
x:=x[j];
x[j]:=temp;
tempstr:=strings[i];
strings[i]:=strings[j];
strings[j]:=tempstr;
i:=i+1;
j:=j-1;
end;
until i > j;
if left<j then
sort2(x,left,j);
if i<right then
sort2(x,i,right);
end;
begin
readln(test);
writeln;
for i:=1 to test do
begin
readln(len,tedad);
for j:=1 to tedad do
begin
readln(strings[j]);
strings2[j]:=translate_number(strings[j]);
end;
for j:=1 to tedad do
begin
counter:=0;
sort(strings2[j]);
number[j]:=counter;
end;
sort2(number,1,tedad);
for j:=1 to tedad do
writeln(strings[j]);
end;
end.

if anybody knows any solutions please....
thanks
m2lajoo