getting TLE on problem on H1 of begginer section first problem in java.. plz help ?

general
, , ,
1

[problem link][1]

getting TLE exceed on problem H1… found no editorial for above H1 problem(editoal link page showing 404 error)
i am using BFS to traverse states… but bfs is giving tle error how to optimise code to not get tle error

on seeing submitted solution of H1 problem, i found nothing different from mine solution which is giving can error… plz help someONe

    /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package PracticeBeginner.Easy;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

/**
 *
 * @author Hemant Dhanuka
 */
public class H1solutionseQuestionValiString {

    public static void main(String[] args) {
        HashMap<Integer, Boolean> primeCheck = new HashMap<Integer, Boolean>();
        primeCheck.put(3, true);
        primeCheck.put(4, false);
        primeCheck.put(5, true);
        primeCheck.put(6, false);
        primeCheck.put(7, true);
        primeCheck.put(8, false);
        primeCheck.put(9, false);
        primeCheck.put(10, false);
        primeCheck.put(11, true);
        primeCheck.put(12, false);
        primeCheck.put(13, true);
        primeCheck.put(14, false);
        primeCheck.put(15, false);
        primeCheck.put(16, false);
        primeCheck.put(17, true);

        HashMap<String, Integer> visitedStateAndCount;
        visitedStateAndCount = new HashMap<String, Integer>();

        LinkedList<String> queue = new LinkedList<>();
        queue.addLast("123456789");
        visitedStateAndCount.put("123456789", 0);

        outside:
        while (!queue.isEmpty()) {
            String str = queue.removeFirst();
            int stepCount = visitedStateAndCount.get(str);
            for (int k = 1; k <= 9; k++) {
                if (k % 3 != 0) {
                    String c1 = str.charAt(k - 1) + "";
                    String c2 = str.charAt(k) + "";
                    int c11 = Integer.parseInt(c1);
                    int c22 = Integer.parseInt(c2);

                    if (primeCheck.get(c11 + c22)) {
                        //swap and make new String
                        String newString = str.substring(0, k - 1) + str.charAt(k) + str.charAt(k - 1) + str.substring(k + 1);

                        if (!visitedStateAndCount.containsKey(newString)) {
                            queue.add(newString);
                            visitedStateAndCount.put(newString, stepCount + 1);

                        }

                    }

                }
            }

            for (int k = 1; k <= 6; k++) {
                int p = k + 3;
                String c1 = str.charAt(k - 1) + "";
                String c2 = str.charAt(p - 1) + "";
                int c11 = Integer.parseInt(c1);
                int c22 = Integer.parseInt(c2);

                if (primeCheck.get(c11 + c22)) {
                    //swap and make new String
                    String newString = str.substring(0, k - 1) + str.charAt(p - 1) + str.substring(k, p - 1) + str.charAt(k - 1) + str.substring(p);

                    if (!visitedStateAndCount.containsKey(newString)) {
                        queue.add(newString);
                        visitedStateAndCount.put(newString, stepCount + 1);

                    }

                }

            }
        }

        Scanner s = new Scanner(System.in);
        int T = s.nextInt();
        for (int i = 0; i < T; i++) {
            String givenMatrix = "";
            for (int j = 0; j < 9; j++) {
                int no = s.nextInt();
                givenMatrix += no;
            }

            if (!visitedStateAndCount.containsKey(givenMatrix)) {
                System.out.println(-1);
            } else {
                System.out.println(visitedStateAndCount.get(givenMatrix));
            }
        }

    }
}

or [my solution link which is giving TLE][2]

plz help someOne
[1]: https://www.codechef.com/problems/H1
[2]: https://www.codechef.com/viewsolution/17451207

2

Avoid useless operations.

For example, your code takes 4.98 seconds to pass sample input-output. Now, I just change this part-

              if (k % 3 != 0) {
                    String c1 = str.charAt(k - 1) + "";
                    String c2 = str.charAt(k) + "";
                    int c11 = Integer.parseInt(c1);
                    int c22 = Integer.parseInt(c2);

to-

         if (k % 3 != 0) {
                //String c1=str.charAt(k-1)+"";
                //String c2=str.charAt(k)+"";
                int c11=(str.charAt(k-1))-'0';
                int c22=(str.charAt(k))-'0';

Running time reduced from 4.98 to 3.65. Full 1.3 seconds. And this was just one of them. See where ever you used the slow operations, and try to optimise them yourself first. If that fails, I will be happy to help.

BTW: If you are providing the link, dont copy paste the code. Keep question short, as long/lengthy questions seem repulsive (especially a wall of code XD)

1 Like