Help needed! Where is my Java code wrong in RISK problem?

pranav_4 · April 28, 2021, 8:03am

I tried to solve the RISK problem of the April Starters contest using the following approach :

We iterate through every element of the 2d world map matrix, and if it is a land element, we count THAT ELEMENT as well as its NEIGHBORING ELEMENTS which are also land elements using a recursive approach, thus returning count of connected elements.

The solution is giving Runtime Error on most of the hidden test cases and I am unable to understand where am I going wrong here. Can anyone help in pointing that out ?

Here 's my submission :

https://www.codechef.com/viewsolution/45425456

suman_18733097 · April 28, 2021, 8:19am

Dude!!!

for( int i = 0; i<n; i++ ){
		        int num = scn.nextInt();
		        for( int j = 1; j <= m; j++ ){
		            map[i][m-j] = (int)( ( num% Math.pow(10, j) ) / Math.pow(10, j-1));
		        }
		    }

You are taking string into Integer. Note that strings can be very huge. Take them into strings instead of Integers.

pranav_4 · April 28, 2021, 8:41am

Okay, that makes sense. But then, converting it into a character array is still producing Runtime as well as Time Limit Errors.

https://www.codechef.com/viewsolution/45499049

suman_18733097 · April 28, 2021, 12:00pm

I added some stuff and executed it.

The Code

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static int matching(char[][] array, boolean[][] check, int n, int m, int x, int y ){
        System.err.println(x + " " + y);
        if( array[x][y] == '0' || check[x][y] == true ){
            check[x][y] = true;
            return 0;
        }
        
        int sum = 1;
        check[x][y] = true;
        if( x-1 >= 0  ){ sum += matching(array,check, n, m, x-1, y); }
        if( x+1 < m  ){ sum += matching(array,check, n, m, x+1, y); }
        if( y-1 >= 0  ){ sum += matching(array,check, n, m, x, y-1); }
        if( y+1 < n ){ sum += matching(array,check, n, m, x, y+1); }
        
        return sum;
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner scn = new Scanner(System.in);
		int T = scn.nextInt();
		
		while( T-- > 0 ){
		    int n = scn.nextInt();
		    int m = scn.nextInt();
		    char[][] map = new char[n][m];
		    boolean[][] check = new boolean[n][m];
		    
		    for( int i = 0; i<n; i++ ){
		        String num = scn.next();
		        map[i] = num.toCharArray();
		    }
		    
		    LinkedList<Integer> sums = new LinkedList<>();
		    for( int i = 0; i < n; i++ ){
		        for( int j = 0; j < m; j++ ){
		            if( !check[i][j] && map[i][j] == '1'){
		                int nsum = matching(map, check, n, m, i, j);
		                if( nsum != 0 ){ sums.add(nsum); }
		            }
		        }
		    }
		    
		    Collections.sort( sums, Collections.reverseOrder() );
		    int res = 0;
		    for( int i = 1; i < sums.size(); i = i+2 ){
		        res += sums.get(i);
		    }
		    System.out.println(res);
            System.err.println();
		}
	}
}

STDIN

STDOUT

2
0
1

STDERR

What do you infer from this?
You are visiting the same node again and again. For strong test cases, the recursion depth is so huge causing RTE. You need to visit a cell only if the following conditions hold true.

You have not visited the cell
The cell you are gonna visit is ‘1’.

Make these changes and try again.

pranav_4 · April 28, 2021, 2:25pm

I really appreciate your effort. However, I made the changes and still that doesn’t seem to be the case. It’s still showing the same errors :

https://www.codechef.com/viewsolution/45505231

suman_18733097 · April 28, 2021, 4:31pm

You didn’t. I made the changes and here’s ACfied Code.

ACfied Code

/*
Author: Chitturi Sai Suman
Created: 2021-04-28 21:42:16
*/
// 57:69:74:68:20:4C:4F:56:45

import java.io.*;
import java.util.*;

public class Main {

    static Scanner io;
    static int dc[] = {1, 0, 0, -1, -1, -1, 1, 1};
    static int dr[] = {0, 1, -1, 0, -1, 1, -1, 1};

    public static int visit(char s[][], boolean visited[][], int i, int j, int n, int m) {
        int score = 1;
        visited[i][j] = true;
        for(int k = 0; k < 4; k++) {
            if(i + dc[k] >= 0 && i + dc[k] < n && j + dr[k] >= 0 && j + dr[k] < m) {
                if(!visited[i + dc[k]][j + dr[k]] && s[i + dc[k]][j + dr[k]] == '1') {
                    score += visit(s, visited, i + dc[k], j + dr[k], n, m);
                }
            }
        }
        return score;
    }

    public static void solve() {
        // Solve Test Cases here
        // 
        int n = io.nextInt();
        int m = io.nextInt();
        char s[][] = new char[n][m];
        for(int i = 0; i < n; i++) {
            s[i] = io.next().toCharArray();
        }
        boolean visited[][] = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            Arrays.fill(visited[i], false);
        }
        ArrayList<Integer> scores = new ArrayList<Integer>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!visited[i][j] && s[i][j] == '1') {
                    scores.add(visit(s, visited, i, j, n, m));
                }
            }
        }
        Collections.sort(scores, Collections.reverseOrder());
        int ans = 0;
        for(int i = 1; i < scores.size(); i += 2) {
            ans += scores.get(i);
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {

        io = new Scanner(System.in);
        int testcases = 0;

        // testcases++;

        if(testcases == 0)
            testcases = io.nextInt();
        
        for(int test = 0; test < testcases; test++) {

            // io.print("Case #" + (test + 1) + ": ");

            solve();

        }
    }
}

pranav_4 · April 29, 2021, 6:34am

That’s great ! I had to finally change my approach and make it similar to yours to arrive at an accepted code. One thing I learned was that the use of LinkedList instead of an ArrayList was heavily responsible for the TLE. Wasn’t noticing that earlier.

Thanks a lot for helping me out with this . Here’s my version of the ACfied code :

https://www.codechef.com/viewsolution/45515081