Solution UVA: 1368 - DNA Consensus String

 

Last Submissions
Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss1368 - DNA Consensus String	Accepted	C++11	0.000	0.000	2409	7 mins ago

Problem: 1368

- Find a string such that it is most similar to the input strings and print the total number of positions that differ from the found string.

Suggest:

-For the given input, which consists of various types of genes in a 2-dimensional array, we will begin by examining each column. We identify the gene that appears the most frequently, and print that gene. The remaining genes will have their occurrence count added to the variable 'es'. After iterating through all the columns, we print the value of 'es'.

-You can find the most frequently appearing gene by using the conventional method of finding the maximum count, or you can utilize two data structures, an unordered_map and a priority_queue, as i mentioned (although this approach may seem like using a sledgehammer to crack a nut =)).

      | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

------------------------------------

1  | T | A | T | G | A | T | A | C |

2  | T | A | A | G | C | T | A | C |

3  | A | A | A | G | A | T | C | C |

4  | T | G | A | G | A | T | A | C |

5  | T | A | A | G | A | T | G | T |

Consensus String: TAAGATAC

Consensus Error: 1 + 1 + 1 + 0 + 1 + 0 + 2 + 1 = 7

#include<bits/stdc++.h>

using namespace std;

int t, n, m;

char a[1001][1001];

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    cin >> t;

    while(t--){

        cin >> n >> m;

        for(int i=1; i<=n; i++)

        for(int j=1; j<=m; j++)

            cin >> a[i][j];

           

        int es= 0;

        for(int j=1; j<=m; j++){

           

            unordered_map<char, int> cnt;

            priority_queue<pair<int, int>> pq;

           

            for(int i=1; i<=n; i++)

                cnt[a[i][j]]++;

           

            for(auto it=cnt.begin(); it!=cnt.end(); it++)

                pq.push({it->second, -1*it->first});    

           

            cout<<char(-1*pq.top().second);

            pq.pop();

           

            while(!pq.empty()){

                es += pq.top().first;

                pq.pop();

            }

        }

        cout<<"\n"<<es<<"\n";

    }

}