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]: fekete | CodeChef User Profile for Ivan Fekete | CodeChef

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

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

6

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

7

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

8

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.

9

@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.

10

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

11

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

12

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

13

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.

14

Here is a different approach for an online solution - (solved in Java btw):

Needed info:

  1. persistent segment tree
  2. “sparse” segment tree - if an interval has no value > 0 then the no need for the subtrees
  3. reuse the memory allocated in previous tests

So basically keep a persistent “sparse” segment tree of numbers 0 … 10^9 to keep track of all the numbers present from the root to the specific node. When a query is done we just have to ask in the persistent seg tree of the node the xor value for the interval [0, K].
The query time is O(log(M)) where M is the 10^9.

First implementation gave TLE and after some debugging I’ve noticed that queries where “peanuts” compared to the build of the date structure. As we all know Java is “good” that you do not have to handle the memory but unfortunately the allocation and GC internally could be a pain in the ass.

So the thing done in order to pass was to allocated from the beginning the maximum nodes that can be used for a test case = O(Nlog(M)* which is at most - 30 * 100 000 → 3 * 10^6.
Also in the following tests will reuse the same nodes.

Hope this will save to others the time I’ve lost investigating.

Link to my solution.

15

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

16

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

17

yes using reader class
here is more about it Fast I/O in Java in Competitive Programming - GeeksforGeeks

18

Thanks bro got an AC…

19

your welcome

20

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