RahulAhuja2901's blog

By RahulAhuja2901, history, 2 months ago, In English

I am currently solving the problem 1915F Greetings from Codeforces Round 918 (Div 4), which involves efficiently performing operations on a sorted set. The task requires inserting elements into a sorted set and then determining the number of elements greater than each newly inserted element (essentially finding the index of the inserted element in the sorted order). Given that n <= 1e5, an O(n^2) solution is infeasible.

In C++, the Policy-Based Data Structures (PBDS) provide a function order_of_key(key) that facilitates efficient operations for such tasks. However, I am working in Java and need an equivalent approach.

Question -

What is the best way to achieve efficient insertions and retrievals of the number of elements greater than a given element in Java? Specifically, how can I implement a solution that maintains O(log n) complexity for both insertions and queries to handle up to 1e5 elements?

I have attempted using tailSet(num).size() and tailMap(num).size(), but both approaches resulted in a time limit exceeded (TLE). Could you suggest a suitable alternative or data structure in Java to meet these requirements and explain its time complexity and implementation details?

Problem Link — https://codeforces.net/problemset/problem/1915/F

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By RahulAhuja2901, history, 21 month(s) ago, In English

I was solving the problem 1561C Deep Down Below where I was using Binary Search on Answer. Initially I was getting Wrong Answer on Test Case 14 so I double checked my code but was unable to find any error.

Link to my Submission — https://codeforces.net/problemset/submission/1561/193939724

So after a lot of Wrong Submissions I removed the Try-Catch Block and then I got Runtime Error (Exit Code is 11).

Link to my Submission — https://codeforces.net/problemset/submission/1561/193939801

Then I replaced "out.println ()" with "System.out.println ()" and I again got Wrong Answer on Test Case 14 saying "Answer contains longer sequence [length = 1000], but output contains 750 elements" so at some point my code is going through a runtime error but I am not able to figure it out.

Link to my Submission — https://codeforces.net/problemset/submission/1561/193939951

Link to the Problem — https://codeforces.net/problemset/problem/1561/C

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it