Xy9px's blog

By Xy9px, 3 weeks ago, In English,

this was a practice question for Ajira Tech. can anyone solve this question --------------------------------------------------------------------------------

Red and Green Balls You have a square grid (NxN). Each cell of the grid has either a red ball or a green ball. Your job is to arrange the balls in such a way that all the red balls are either on or below the main diagonal. The main diagonal starts from cell 1x1 and ends at cell NxN. You have only one move which is to swap adjacent rows. You need to achieve the final arrangement in minimal number of moves. If it is not possible to come to a resolution by swapping then print -1 Input: First line of input is the number of rows in grid. Rest are the lines in the grid Ouput: Minimum number of moves

Input
2
RG
RR
Output
0
Input 2
GR
RG
Output
1

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Xy9px (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just store the last index in every row in an array and perform bubble sort on the array and count number of swaps. If after sorting value of index is greater than index then output -1 otherwise number of swaps.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    last index of what

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Last index of occurrence of 'R' in each row. For example, for input such as:

      R
      GR
      GRR
      RGRG
      GRGGG
      

      we will store values as {0,1,2,2,1} now we will perform bubble sort on this array to count number of swaps. The idea of bubble sort comes from "swap adjacent rows".

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        If after sorting value of index is greater than index then output -1 how to do this i dnt understand this

        5
        GGRRG
        GRRRG
        RGGGG
        RRRGG
        

        this gives 4 but the answer should be 6

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        using namespace std;
        void  FindMinimumSwaps(vector<int>&v) {
            vector<int>copy=v;
            int i, j,n=v.size(),s=0,temp;  
            for (i = 0; i < n-1; i++) {
                for (j = 0; j < n-i-1; j++) {
                    if (v[j] > v[j+1]) {
                        temp = v[j+1];
                        v[j+1] = v[j];
                        v[j] = temp;
                        s++;
                    } 
                } 
            }  
            for(int i=0;i<n;i++) {
                cout<<copy[i]<<" ";
            }
            cout<<endl;
            for(int i=0;i<n;i++) {
                cout<<v[i]<<" ";
            }
            cout<<endl;
            if(v==copy) {
                cout<< -1;
            }
            else {
                cout<< s;
            }
        }
          
        
        int main()
        {
            int n;
            cin>>n;
            vector<vector<char> > mat(100, vector<char>(100));
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    cin>>mat[i][j];
                }
            }
            vector<int>v;
            for(int i=0;i<mat.size();i++) {
                for(int j=mat[0].size()-1;j>=0;j--) {
                    if(mat[i][j]=='R'){
                        v.push_back(j);
                        break;
                    }
                }
            }
            FindMinimumSwaps(v);
          return 0;
        }
        

        this is wt i came up with

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          This is my program. It got accepted. ~~~~~

          import java.io.*;
          import java.util.*;
          class code {
            public static void main(String[] args) throws Exception {
              Scanner sc=new Scanner(System.in);
              int n=sc.nextInt();
              int ar[]=new int[n];
              for(int x=0;x<n;x++)
              {
                  String s=sc.next();
                  int p=-1;
                  for(int y=0;y<n;y++)
                  {
                      if(s.charAt(y)=='R')
                      {
                          p=y;
                      }
                  }
                  ar[x]=p;
              }
              int ans=0;
              for(int x=0;x<n;x++)
              {
                  for(int y=0;y<n-1;y++)
                  {
                      if(ar[y]>ar[y+1])
                      {
                          ans++;
                          int t=ar[y];
                          ar[y]=ar[y+1];
                          ar[y+1]=t;
                      }
                  }
              }
              boolean found=true;
              for(int x=0;x<n;x++)
              {
                  if(ar[x]>x)        
                  {
                      found=false;
                      break;
                  }
              }
              System.out.println(found?ans:-1);
            }
          }
          

          ~~~~~

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Xy9px First of all you should always put a link of the task, so people could know if it's from an ongoing contest (since Goku submitted it somewhere, and already gave you a solution, I'll assume it's ok). The example you gave us was 5x4 instead of 5x5 so I don't know what's problem with that either. Your code lacks checking whether it's impossible to arrange in such a way (checking whether there's v[I]>I after sorting should suffice)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sry for that test case. its was a practice problem not an ongoing contest

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    5
    GGRRG
    GRRRG
    RGGGG
    RGGGG
    RRRGG
    

    here is the test case.