WarpSpeed's blog

By WarpSpeed, history, 3 years ago, In English,

I have gone through sorting of simple 2-D arrays. And there are ample ways to do this efficiently. But lately, I'm facing some issues in sorting 2-D arrays with the following conditions:

Suppose there's a 2-D array with 2 rows and n columns. (Here n can vary from 1 upto 10^6) . All the entries are integer entries with the upper bound being 2 * 10^9 . The task here is to sort the elements in the first row in ascending order, preferably ( although, ascending/descending doesn't make much of a difference anyway ) and the elements of second row should occupy their new positions corresponding to their previous row-1 elements ( irrespective of their relations among other row-2 elements ).

A sample:

Suppose the array is as follows:

5 6 4 8 7 3

4 9 5 1 0 2

Then after sorting the final array should become:

3 4 5 6 7 8

2 5 4 9 0 1

With the conditions of n's upper bound going as high as 10^6, trivial methods of sorting this serve useless and lead to TLE message. How can the aforementioned task be achieved in the most efficient manner?

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A nlogn sorting shouldn't give TLE even with 10**6 elements. Maybe there's some other problem? How many test cases are there? Also make sure you are using scanf/printf instead of cin/cout

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is cin/cout slower than scanf/printf? Pardon me for being a little naive as I'm just transitioning from C to C++.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes it is. Please read this: http://codeforces.com/blog/entry/5217 I generally use cin/cout and it works fine but if the input size is large and includes number of the order more then 10**5 then it is always better to use scanf/printf.

      In this problem, you should use pair<int, int> array and then sort it.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You need something better than O(NlogN) ?

P.S : O(NlogN) should be fine for N<=10^6

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I rely on the STL sort or the qsort in C when I have to sort a 2-D array normally, i.e, sort individual rows or columns.

    But here if I apply the STL sort to the row 1, then (since it being an in-place sort) how do I place the row-2 elements correspondingly?

    If possible, can you also post a code snippet showing the right way?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You need something better than O(NlogN) ?

P.S : O(NlogN) should be fine for N <  = 106

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can do this by using pair or struct keyword in C++.

Using pair

Using struct

Problem related to this