HELP IN MARLA

help
1

PROBLEM
This problem comes under graph theory. I didn’t get any approach to it using graphs (the editorial said to use DFS but I didn’t understand how to). That’s why I used a different method.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector <pair <int, int>> h(0);
    while (n--)
    {
        vector <int> s(m);
        for (int i = 0; i < m; ++i) cin >> s[i];
        int prev = 0, size = 0;
        for (int i = 0; i < m; ++i)
        {
            if (prev == 0)
            {
                size = 1;
                prev = s[i];
            } else {
                if (s[i] == prev) ++size;
                else {
                    h.push_back(make_pair(s[i], size));
                    size = 1;
                }
            }
            if (i == m-1)
            {
                h.push_back(make_pair(s[i], size));
                size = 1;
            }
        }
    }
    int max = -1, bank = 0;
    sort(h.begin(), h.end());
    for (auto i : h)
    {
        if (i.second > max)
        {
            max = i.second;
            bank = i.first;
        }
    }
    cout << bank << " " << max << '\n';
}

I go through all values in a line and store their count (i.e., if they are consecutive) in a vector of pairs. I do this for all n lines in a single vector (because I need the maximum number of banks I can hack from all given values). I sort the vector according to the bank type so that I only have to check if the current max value is greater than the second value of a pair and I need to make that the current max.

This approach works fine for a few cases but I fail to understand why I get a WA verdict for the others.

This is the verdict:

Screenshot (88)
Screenshot (88)822×583 9.11 KB

Please help me understand what is wrong in my code. Any help is appreciated.

2

@everule1 please help :pray:

4

You can’t just do every row independently. For example

3 2 1
3 4 1
2 3 1

You would print

1 1

But the answer is

1 3
1 Like
5

Thanks :slight_smile:

6

I used BFS instead of DFS, pushing the adjacent unexplored cells in queue till it’s empty. I’m getting WA for 2 test cases 1 in each subtask. What am I doing wrong?

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m; cin>>n>>m;
    int grid[n][m];
    int vis[n][m];
    memset(vis,0,sizeof(vis));
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++)
            cin>>grid[i][j];
    }
    int count=0,s=1e9+1;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (vis[i][j]==0) {
                queue<pair<int,int>> Q;
                Q.push({i,j});
                int c=0;
                while (!Q.empty()) {
                    auto x=Q.front();
                    int a=x.first,b=x.second;
                    c++;Q.pop();
                    vis[a][b]=1;
                    int type=grid[a][b];
                    if (a!=0 && type==grid[a-1][b] && vis[a-1][b]==0)
                        Q.push({a-1,b});
                    if (a!=n-1 && type==grid[a+1][b] && vis[a+1][b]==0)
                        Q.push({a+1,b});
                    if (b!=0 && type==grid[a][b-1] && vis[a][b-1]==0)
                        Q.push({a,b-1});
                    if (b!=m-1 && type==grid[a][b+1] && vis[a][b+1]==0)
                        Q.push({a,b+1});
                }
                if (count<c)
                    count=c,s=grid[i][j];
                else if (count==c) {
                    if (grid[i][j]<s)
                        s=grid[i][j];
                }
                else {}
            }
        }
    }
    cout<<s<<" "<<count<<"\n";
    return 0;
}
7

Your BFS implementation is wrong. You should set vis to 1 as soon as you push it in the queue.

1 Like
8

Thank you soo much, that did it!