Time Limit should be increased by 0.5 sec for Pishty and tree (JULY17)

general
, ,
1

My code is running in O(nlogn) but still getting TLE…only hardware level optimisation required.I am wasting my time to optimise it for more 0.5 sec…so please increase its Time limit by 0.5 sec because in java object takes more time than struct in cpp.

Why so strict Time limit O(n^2) solution won’t even run in 10 sec?

[author of the problem][1]
[1]: https://www.codechef.com/users/fekete

7 Likes
2

Gentle reminder of no discussions on live contests. Besides, Java’s execution time is normalised. So, don’t have to compare with c++.

3

I agree, My logn solution was barely able to pass at 1.46 Secs.

4

I agree with you . My solution without fast IO could not pass the 2nd subtask. However you have a double time limit in java right? So are you using fast IO or not because i think it should solve the problem.

Although I agree with you I would suggest you write this request in in the comment section of the problem rather posting in the forum

Also it’s better if you don’t reveal your time complexity during the contest

3 Likes
5

java is slower than cpp thats why they give double time…but still… read the comment below.

6

Yes, I am using buffered reader and writer. Is there any other fast I/O in java?

7

yes using reader class
here is more about it http://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/

8

Thanks bro got an AC…

9

You can solve this within one second, I did it in 0.5 seconds in c++.

10

your welcome

11

My C++ solution passed the 10 points and 20 points task in 0.02 secs … but i m getting TLE in the third subtask.

12

Optimize those constants !! 5nlogn may TLE but 2nlogn may pass !! My java soln passed after such optimization

13

I passed this using:

  1. Heavy-Light decomposition on the tree. This can be done in O(n) time.
  2. Using what I call a merge tree on the heavy segments. That is, for each Segment Tree mode keep a sorted array of elements in that range, binary search for the location of the most expensive magic edge, and use prefix xor sums for finding their xor. This takes O(nlogn) space and uses O(logn) time to answer a query per heavy chain, which comes out to O(log^2n) time per query.
  3. Using fast IO.

So java can pass with O(nlogn) space and O(nlogn + qlog^2n) time solution. Use a better implementation next time.

14

@ureino, I used the exact same concept as you just mentioned but did in c++, no matter how I try to optimize it I was getting TLE for the 5th test case, in the end had to use a different technique altogether to get it to work. It’s insane that, if I had tried the same code in java, I would’ve gotten AC but the same code in c++ gives TLE.

15

@vsr625 What different technique did you use?.Even my O(nlogn +qlog^2n) algorithm exceeded time limit.

16

just fast read added to my O(nlogn +2qlogn) solution.

17

my solution was taking only O(nlogn+2qlogn)…its better than (nlogn+qlog^2n)…It was fast read problem in my solution.

18

Barely got AC with HLD and Merge Sort trees. Used fast IO though :slight_smile:

19

I solved it using offline queries on fenwick tree in 0.7sec.

20

Solved using DFS order property and Segment trees. Initially I used cin and cout for I/O but it gave only 30 points. Then instead of cin and cout I used scanf and printf which gave full 100 points and maximum time taken for test case was only 0.63 seconds.