You are not logged in. Please login at www.codechef.com to post your questions!

×

Getting TLE - Please Help!!!

Problem:- DIGJUMP

Please help me in optimizing this code which uses BFS to find the shortest distance between start and end vertices.

My code:- Solution

asked 22 Nov '17, 15:48

ramini's gravatar image

2★ramini
615
accept rate: 8%

edited 23 Nov '17, 02:40


I think your graph construction is wrong . Lets say 2 2 2 2

So dig[2]={1,2,3,4} So you do this: For i=1: Adj[1]=2,3,4 Adj[2]=1 Adj[3]=1 Adj[4]=1

For i=2 Adj[1]={2,3,4,2} Adj[2]={1,1,3,4} ...

Hope it helps.correct me if i am wrong.

link

answered 23 Nov '17, 10:46

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

But it is giving correct output for all the test cases. Any test cases where it fails?

(23 Nov '17, 21:13) ramini2★

I am not saying it wont pass.

I am saying that due to this u might be getting tle. Consider 2 2 2... 10^5 times

So your building graph itself takes O(N^2)

I would suggest try to build the graph properly

(23 Nov '17, 21:45) vivek_19982996★

Ohh Okay. I will try to implement it differently.

(24 Nov '17, 00:42) ramini2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×22
×7

question asked: 22 Nov '17, 15:48

question was seen: 269 times

last updated: 24 Nov '17, 00:42