We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I used markov chains. It can pass 46/47 of the test cases. Can't do the 5th test case because of the time limit.
5th test case n*m*25 markov chains = 0,462033
5th test case n*m*70 markov chains = 0,462102
but the second one takes too much time. n*m*25 is enough for the other test cases.
I don't think the code would be able to do it fast enough even if I change all of the lists to arrays (first did all of the code using arraylists than afterwards changed only the matrices multiplying part to arrays to make it faster) and then destroy the redundant methods. Probably needs a faster way to multiply matrices.
importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.*;importjava.util.stream.IntStream;publicclassMarkovChains{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbufferedReader=newBufferedReader(newInputStreamReader(System.in));String[]firstMultipleInput=bufferedReader.readLine().replaceAll("\\s+$","").split(" ");intn=Integer.parseInt(firstMultipleInput[0]);intm=Integer.parseInt(firstMultipleInput[1]);intk=Integer.parseInt(firstMultipleInput[2]);/* This is the only place I wrote code except those places marked for us to write code and the four methods I created. */List<List<String>>game=newArrayList<>();List<List<Double>>initalState=newArrayList<>();initalState.add(newArrayList<>(Collections.nCopies(n*m,0d)));HashMap<List<Integer>,List<Integer>>tunnelIndexes=newHashMap<>();IntStream.range(0,n).forEach(nItr->{try{Stringrow=bufferedReader.readLine();// Write your code hereList<String>rowList=newArrayList<>(Arrays.asList(row.split("")));if(rowList.contains("A")){initalState.get(0).set(nItr*m+rowList.indexOf("A"),1d);rowList.set(rowList.indexOf("A"),"O");}game.add(rowList);}catch(IOExceptionex){thrownewRuntimeException(ex);}});IntStream.range(0,k).forEach(kItr->{try{String[]secondMultipleInput=bufferedReader.readLine().replaceAll("\\s+$","").split(" ");inti1=Integer.parseInt(secondMultipleInput[0]);intj1=Integer.parseInt(secondMultipleInput[1]);inti2=Integer.parseInt(secondMultipleInput[2]);intj2=Integer.parseInt(secondMultipleInput[3]);// Write your code heregame.get(i1-1).set(j1-1,"T");game.get(i2-1).set(j2-1,"T");List<Integer>tunnelIndex1=newArrayList<>(Arrays.asList(i1-1,j1-1));List<Integer>tunnelIndex2=newArrayList<>(Arrays.asList(i2-1,j2-1));tunnelIndexes.put(tunnelIndex1,tunnelIndex2);tunnelIndexes.put(tunnelIndex2,tunnelIndex1);}catch(IOExceptionex){thrownewRuntimeException(ex);}});// Write your code hereList<List<Double>>matrix=createMatrix(game,tunnelIndexes);System.out.printf("%.6f",markovChain(matrix,initalState));bufferedReader.close();}publicstaticdoublemarkovChain(List<List<Double>>transitionMatrix,List<List<Double>>initalState){List<Double>absorbingStates=transitionMatrix.remove(transitionMatrix.size()-1);/* We have to do the markov chain until the change on our initalState is less than 10^-6. I thought instead of checking it at the end of every loop, it would be just faster to do it according to the size of the game. *//* For the code I used ArrayList instead of Arrays. When I finished doing it I realized it needed to be faster because of the time limit on the site. I changed it only here because I'm too lazy to change all lists to arrays. convertArrayToList() && convertListTo2DArray() has no other purpose.*/double[][]initalStateArray=convertListTo2DArray(initalState);double[][]transitionMatrixArray=convertListTo2DArray(transitionMatrix);for(inti=0;i<initalState.get(0).size()*25;i++){initalStateArray=multiplyMatrices(initalStateArray,transitionMatrixArray);}initalState=convertArrayToList(initalStateArray);doublechanceWinning=0,chanceAbsorbing=0;for(doubleindex:absorbingStates){if(index>0){chanceWinning+=initalState.get(0).get((int)index);chanceAbsorbing+=initalState.get(0).get((int)index);}else{chanceAbsorbing+=initalState.get(0).get((int)-index);}}returnchanceWinning/(chanceAbsorbing==0?1:chanceAbsorbing);}publicstaticList<List<Double>>createMatrix(List<List<String>>game,HashMap<List<Integer>,List<Integer>>tunnelIndexes){intn=game.size(),m=game.get(0).size();List<List<Double>>matrix=newArrayList<>();List<Double>absorbingStates=newArrayList<>();for(inti=0;i<n;i++){for(intj=0;j<m;j++){Stringcell=game.get(i).get(j);List<Double>rowVector=newArrayList<>(Collections.nCopies(n*m,0d));List<Integer>pathIndexes1D=newArrayList<>();if(cell.equals("%")){rowVector.set(i*m+j,1d);absorbingStates.add((double)(i*m+j));}elseif(cell.equals("*")){rowVector.set(i*m+j,1d);absorbingStates.add((double)-(i*m+j));}elseif(!(cell.equals("#"))){if(j+1<m&&!game.get(i).get(j+1).equals("#")){if(game.get(i).get(j+1).equals("T")){List<Integer>endOfTunnel=tunnelIndexes.get(Arrays.asList(i,j+1));pathIndexes1D.add(endOfTunnel.get(0)*m+endOfTunnel.get(1));}else{pathIndexes1D.add(i*m+j+1);}}if(j-1>=0&&!game.get(i).get(j-1).equals("#")){if(game.get(i).get(j-1).equals("T")){List<Integer>endOfTunnel=tunnelIndexes.get(Arrays.asList(i,j-1));pathIndexes1D.add(endOfTunnel.get(0)*m+endOfTunnel.get(1));}else{pathIndexes1D.add(i*m+j-1);}}if(i+1<game.size()&&!game.get(i+1).get(j).equals("#")){if(game.get(i+1).get(j).equals("T")){List<Integer>endOfTunnel=tunnelIndexes.get(Arrays.asList(i+1,j));pathIndexes1D.add(endOfTunnel.get(0)*m+endOfTunnel.get(1));}else{pathIndexes1D.add((i+1)*m+j);}}if(i-1>=0&&!game.get(i-1).get(j).equals("#")){if(game.get(i-1).get(j).equals("T")){List<Integer>endOfTunnel=tunnelIndexes.get(Arrays.asList(i-1,j));pathIndexes1D.add(endOfTunnel.get(0)*m+endOfTunnel.get(1));}else{pathIndexes1D.add((i-1)*m+j);}}if(cell.equals("T")&&pathIndexes1D.isEmpty()){rowVector.set(i*m+j,1d);absorbingStates.add((double)-(i*m+j));}for(intindex:pathIndexes1D){rowVector.set(index,1d/pathIndexes1D.size());}}matrix.add(rowVector);}}matrix.add(absorbingStates);returnmatrix;}publicstaticdouble[][]multiplyMatrices(double[][]firstMatrix,double[][]secondMatrix){double[][]result=newdouble[firstMatrix.length][secondMatrix[0].length];for(introw=0;row<result.length;row++){for(intcol=0;col<result[row].length;col++){result[row][col]=multiplyMatricesCell(firstMatrix,secondMatrix,row,col);}}returnresult;}publicstaticdoublemultiplyMatricesCell(double[][]firstMatrix,double[][]secondMatrix,introw,intcol){doublecell=0;for(inti=0;i<secondMatrix.length;i++){cell+=firstMatrix[row][i]*secondMatrix[i][col];}returncell;}publicstaticdouble[][]convertListTo2DArray(List<List<Double>>list2D){intnumRows=list2D.size();intnumCols=list2D.get(0).size();double[][]array2D=newdouble[numRows][numCols];for(inti=0;i<numRows;i++){for(intj=0;j<numCols;j++){array2D[i][j]=list2D.get(i).get(j);}}returnarray2D;}publicstaticList<List<Double>>convertArrayToList(double[][]array2D){List<List<Double>>list2D=newArrayList<>();for(double[]row:array2D){List<Double>rowList=newArrayList<>();for(doublevalue:row){rowList.add(value);}list2D.add(rowList);}returnlist2D;}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Frog in Maze
You are viewing a single comment's thread. Return to all comments →
I used markov chains. It can pass 46/47 of the test cases. Can't do the 5th test case because of the time limit.
5th test case n*m*25 markov chains = 0,462033 5th test case n*m*70 markov chains = 0,462102
but the second one takes too much time. n*m*25 is enough for the other test cases.
I don't think the code would be able to do it fast enough even if I change all of the lists to arrays (first did all of the code using arraylists than afterwards changed only the matrices multiplying part to arrays to make it faster) and then destroy the redundant methods. Probably needs a faster way to multiply matrices.