### Xy9px's blog

By Xy9px, 4 weeks ago, ,

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



• +1

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Xy9px (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 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.
•  » » 4 weeks ago, # ^ |   0 last index of what
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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".
•  » » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 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
•  » » » » 4 weeks ago, # ^ |   0 using namespace std; void FindMinimumSwaps(vector&v) { vectorcopy=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; vector > mat(100, vector(100)); for(int i=0;i>mat[i][j]; } } vectorv; for(int i=0;i=0;j--) { if(mat[i][j]=='R'){ v.push_back(j); break; } } } FindMinimumSwaps(v); return 0; } this is wt i came up with
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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;xar[y+1]) { ans++; int t=ar[y]; ar[y]=ar[y+1]; ar[y+1]=t; } } } boolean found=true; for(int x=0;xx) { found=false; break; } } System.out.println(found?ans:-1); } } ~~~~~
 » 4 weeks ago, # |   0 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)
•  » » 4 weeks ago, # ^ |   0 sry for that test case. its was a practice problem not an ongoing contest
•  » » 4 weeks ago, # ^ |   0 5 GGRRG GRRRG RGGGG RGGGG RRRGG here is the test case.