DESTCELL - Editorial

editorial
, , , ,
21

Why I am getting TLE (Java)… Can anyone help me out ?? @taran_1407

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

Update:

I have improved my java code :slightly_smiling_face:
huge lol :weary: got 100 now only 2-3 line changes
https://www.codechef.com/viewsolution/26195050

22

Can you please explain line no. 22.?

23

I was actually thinking that this sieve based method will have {{(n*m)}^{2}*{log(n*m)}} complexity, should have submitted it during the contest :cry:

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

25

You are declaring and initializing a large array (of size nm ) for every value of “k”, therefore your solution is working in n^2m^2log(nm), you can reduce this by factor of nm if you initialize the array once per test case, instead of initializing it nm times per test case.

1 Like
26

This question taught me the importance of global declaration and how maps can be very bad if number of elements >=10^5 :slight_smile:

1 Like
27

Thanks a lot. I didn’t now it also consumes time to create a vector. I thought it to be O(1) operation.

28

basically if u understood the editorial he used 2d visited array for x and y, [1000][1000] but we could also use 1d array of size >=1000000, in this solution tomsyd used bitset of that size which also acts as boolean array. there are at most 10^6 unique coordinates right,so 1000*x+y will act as your hash function to give unique mapping for storing coordinates.its not necessary though u could always use 2d visited array, this trick sometimes is very helpful though.

1 Like
29

elaborate the optimisation in short words please.

30

How this question taught you this?

1 Like
31

Thanks man.! Really cool trick.

32

Can you please explain why global declaration is important here? Thank you very much. :slightly_smiling_face:

1 Like
33

Ok, listen carefully. If you want a[1000][1000] matrix in C++, declare it globally or else you will get RE.

Initially, I was storing the values of positions in a map which gives TLE due to log(n) factor, then I stored those positions in A[I][J](MATRIX), log(n) factor removed hence no tle!!

2 Likes
34

I’m just guessing you used a matrix of integers, am I right? I have used one of boolean type and didn’t face any problems.
About the second one, if you make a hash function for pairs, the log N factor goes away, but that would be overkill.
Thanks for the response. :slightly_smiling_face:

35

Yes, I never make any hash functions because I don’t trust my hashing functions + 2nd problem of div-2 is tougher than this one for me as its too much implementation intensive.

1 Like
36

https://www.codechef.com/viewsolution/26199556
Here I used global array now what can I do to optimize further?!

37

How did you get full score? The time for the last test case is 3.52s for your code, however the limit is 2.5s!

38

there is no need of set, bitset or map it can be done without these
check my sol: CodeChef: Practical coding for everyone

39

Java has a Multiplier of 2x… So, 2*2.5 = 5s

They have changed the Multiplier for python and now I think its 2.5x.(Not sure)

40

There is a fault in line-107.
Listen, you are filling 10^6 elements=0 for each ‘k’ , total time complexity :- O(10^6.k) , where k=10^6 , which is truly terrible,
keep track of places where you put a[i][j]=1, after you have solved it for a particular ‘k’ , make those particular indices (i,j) , i.e , a[i][j]=0; this will save lots of wasted time!

1 Like
41

https://www.codechef.com/viewsolution/26210572
solved in nmlog(n*m) still getting tle in 1 subtask.
Can anyone tell why.