Time limit exceeded java

Avoid CPU time limit exceeded (core dumped) or Terminated due to timeout

Hi recently while trying to solve a core Java algorithm question I got trapped into a problem. Let me explain the puzzle.

There is a series of numbers. where difference between any consecutive
numbers is either a or b. The 1st number of the series is 0. Our code
should compute the last possible numbers given the total count of
elements say n and values of a and b. Constraints: 1 ≤ n, a, b ≤ 1000

0, 10, 20, 30 0, 10, 20, 120 0, 10, 110, 120 0, 10, 110, 210 0, 100, 110, 120 0, 100, 110, 210 0, 100, 200, 210 0, 100, 200, 300 

hence the answer 30 120 210 300 Now the actual bugger. My code computes desired output for less value of n. But when n exceeds say 50 I get

CPU time limit exceeded (core dumped) Terminated due to timeout 

import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Solution < private static ListlistPossibleValues; private static int maxStone; public static void main(String[] args) < Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); if (1 0) getPossibleLastValue(scanner.nextInt(), scanner.nextInt(), scanner.nextInt()); > > private static void getPossibleLastValue(int n, int a, int b) < maxStone = n; listPossibleValues = new ArrayList(); int stone = 0; getNextStone(stone,0, a, b); Collections.sort(listPossibleValues); System.out.println(listPossibleValues.toString().replace("[", "").replace("]", "").replace(",", "")); > private static void getNextStone(int stone, int lastValue, int a, int b) < int newLastA = lastValue + a; int newLastB = lastValue + b; stone++; if (stone < maxStone -1)< getNextStone(stone,newLastA,a,b); getNextStone(stone,newLastB,a,b); >else < if(!listPossibleValues.contains(newLastA))< listPossibleValues.add(newLastA); >if(!listPossibleValues.contains(newLastB)) < listPossibleValues.add(newLastB); >> > > 

n = 3 a = 1 b = 2 2 3 4 n = 4 a = 10 b = 100 30 120 210 300 n = 9 a = 25 b = 59 200 234 268 302 336 370 404 438 472 n = 18 a = 28 b = 28 476 n = 12 a = 26 b = 35 286 295 304 313 322 331 340 349 358 367 376 385 

• 3 Contributors
• 5 Replies
• 1K Views
• 5 Days Discussion Span
• Latest Post 8 Years Ago Latest Post by JeffGrigg

Recommended Answers Collapse Answers

All 5 Replies

Contains check on a List data structure is expensive due to its O(n) nature and should be avoided; prefer using a Set variant like HashSet .

The needless computation aspect of this problem is very similar to when you are recursively computing factorials. If you want 5! and you are using the naive approach, you end up computing stuff needlessly an exponential number of times. Try tracing the recursive call 10! on a piece of paper to understand more.

If you log the values passed to the method getNextStone , you’ll see it getting called countless times for the same set of inputs. The solution here is to use memoization and remember the result of the computations instead of getting into the recursive death spiral. A small change to your code and it now runs pretty fast IMO.

// Java 8 specific code; you might have to change it class Solution < private static HashSetlistPossibleValues; private static HashSet alreadyComputed = new HashSet<>(); private static int maxStone; private static int cnt = 0; public static void main(int n, int a, int b) < long start = System.nanoTime(); getPossibleLastValue(n, a, b); System.out.printf("It took %s milliseconds for naive approach%n%n", TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - start)); >private static void getPossibleLastValue(int n, int a, int b) < maxStone = n; listPossibleValues = new HashSet(); int stone = 0; getNextStone(stone, 0, a, b); System.out.println(listPossibleValues.stream().sorted().collect(Collectors.toList())); System.out.printf("Count=%s%n", cnt); > private static void getNextStone(int stone, int lastValue, int a, int b) < String key = stone + "|" + lastValue; if (alreadyComputed.contains(key)) < return; >cnt++; int newLastA = lastValue + a; int newLastB = lastValue + b; stone++; if (stone < maxStone - 1) < getNextStone(stone, newLastA, a, b); getNextStone(stone, newLastB, a, b); >else < if (!listPossibleValues.contains(newLastA)) < listPossibleValues.add(newLastA); >if (!listPossibleValues.contains(newLastB)) < listPossibleValues.add(newLastB); >> alreadyComputed.add(key); > > 

Источник

Time limit exceeded

Уже все перепробовал, и всегда возникает ошибка «Time limit exceeded» на 8-м тесте.
Кто-нибудь подскажите исходный код решения.

Мое вот(так-то все верно, но во время не укладывается на 8 тесте):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class examscheck { public static void main(String[] args) { Scanner in = new Scanner(System.in); ListInteger>teacherlist = new ArrayList(); int countsame = 0; int count1 = in.nextInt(); for(int i=0;icount1;i++){ teacherlist.add(in.nextInt()); } int count2 = in.nextInt(); for(int m=0;mcount2;m++){ if(Collections.binarySearch(teacherlist,in.nextInt())>=0){ countsame++; }; } System.out.println(countsame); } }

Time limit exceeded
Решаю задачки на одном сайте, там есть онлайн компилятор. Моя VS справляется, но компилятор с сайта.

Time limit exceeded
Добрый день. Программа — бинарный поиск правой границы в упорядоченном множестве фраз. Возникает.

Timus Time limit exceeded (Bingo!)
Здравствуйте. Второй день уже пытаюсь решить проблемы "Timus, C#, Time limit exceeded", у меня не.

Матрица инцидентности = Time-limit exceeded
Как переделать программу, чтобы время ее выполнения было <0.250 sec? #include <iostream> using.

Сообщение было отмечено Wolfevg как решение

Решение

Wolfevg, Scanner слишком умный (читай — медленный) для вашей задачи. У вас же точно известно, что будет отдельное число на каждой строке. Можно обойтись обычным BufferedReader + parseInt.
Далее у вас известно количество строк — вы можете сразу выделять массив подходящего размера.

Источник

GSS1 SPOJ problem Time Limit Exceeding

I’m solving the problem by using a segment tree — I am saving the sum, the max ,leftmost max, and the right most max at every node. I then search the graph to find the answer to a specific interval. How could I increase the speed of this code?

import java.util.Scanner; //TLE class GSS1 < static class Node< int max; int MaxL; int MaxR; int sum; public Node(int max, int MaxL, int MaxR, int sum)< this.max=max; this.MaxL=MaxL; this.MaxR=MaxR; this.sum=sum; >public Node() < >> static class SegmentTree < private Node[] tree; private int maxsize; private int height; private final int STARTINDEX = 0; private final int ENDINDEX; private final int ROOT = 0; Node s; public SegmentTree(int size)< height = (int)(Math.ceil(Math.log(size) / Math.log(2))); maxsize = 2 * (int) Math.pow(2, height) - 1; tree = new Node[maxsize]; for(int i=0;iENDINDEX = size - 1; s=new Node(); s.MaxL=Integer.MIN_VALUE; s.MaxR=Integer.MIN_VALUE; s.sum=Integer.MIN_VALUE; s.max=Integer.MIN_VALUE; > private int leftchild(int pos) < return 2 * pos + 1; >private int rightchild(int pos) < return 2 * pos + 2; >private int mid(int start, int end) < return (start + (end - start) / 2); >private Node constructSegmentTreeUtil(int[] elements, int startIndex, int endIndex, int current) < if (startIndex == endIndex) < tree[current].max=tree[current].MaxL=tree[current].MaxR=tree[current].sum=elements[startIndex]; return tree[current]; >int mid = mid(startIndex, endIndex); Node left=constructSegmentTreeUtil(elements, startIndex, mid, leftchild(current)); Node right=constructSegmentTreeUtil(elements, mid + 1, endIndex, rightchild(current)); tree[current].max = Math.max(left.max, right.max); tree[current].MaxL = Math.max(left.MaxL , left.sum+right.MaxL); tree[current].MaxR = Math.max(right.MaxR , right.sum+left.MaxR); tree[current].sum = left.sum+right.sum; return tree[current]; > public void constructSegmentTree(int[] elements) < constructSegmentTreeUtil(elements, STARTINDEX, ENDINDEX, ROOT); >private Node getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current)< if (queryStart = endIndex ) < return tree[current]; >if (endIndex < queryStart || startIndex >queryEnd) < return s; >int mid = mid(startIndex, endIndex); Node left=getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current)); Node right=getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current)); Node current_Node=new Node(); current_Node.max = Math.max(left.max, right.max); current_Node.MaxL = Math.max(left.MaxL , left.sum+right.MaxL); current_Node.MaxR = Math.max(right.MaxR , right.sum+left.MaxR); current_Node.sum = left.sum+right.sum; return current_Node; > public int getMaxSum(int queryStart, int queryEnd) < if(queryStart < 0 || queryEnd >tree.length) return getMax(getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT)); > public int getMax(Node r) < return Math.max(Math.max(r.max, r.MaxL),Math.max(r.MaxR, r.sum)); >public int getFirst() < return tree[0].MaxL; >> public static void main(String[] args) < Scanner input=new Scanner(System.in); int numbers[]=new int [input.nextInt()]; for(int i=0;iSegmentTree tree=new SegmentTree(numbers.length); tree.constructSegmentTree(numbers); int cases=input.nextInt(); int x; int y; int query; for(int i=0;i > > 

Источник