I_LOVE_ROMANIA's blog

Need help with a classic nice problem
By I_LOVE_ROMANIA, history, 2 years ago, In English

Hey! Is someone who can help me solve this faster than O(N^2)? The problem: initially we have an array V1 of size N with the numbers from 1 to N ordered.

Example: N = 4; V1 = {1, 2, 3, 4}.

We have a second array of N numbers, let's say V2 = {3, 2, 0, 1}. For each position 'i' from right to left, we will apply the operation "move right the element V1[i] with V2[i] positions.

We have 4 operations {3, 2, 0, 1}. Apply i = 3, so V1 will be {1, 2, 3, 4}; further we apply i = 2 (V2[2] = 0 so V1[2] stays); we apply i = 1, so we move the element '2' with 2 positions right in V1 (the array becomes {1, 3, 4, 2}. Finally we apply i = 0 so V1 becomes {3, 4, 2, 1}.

Any idea? Thank you!

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

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

Auto comment: topic has been updated by I_LOVE_ROMANIA (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As this problem is essentially asking you to delete and insert an element at particular positions, it can be done with implicit treap (or any other BBST I guess) in O(nlogn)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe something like this will work:

#include <bits/stdc++.h>

using namespace std;

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> v1(n), v2(n);

    for ( auto& el : v1 )
        cin >> el;
    for ( auto& el : v2 )
        cin >> el;

    vector<int> minima_not_used_pos( n ); // [ n*i; n*i+n-1 ] - area of the i-th position

    for ( int i=0; i<n; i++ )
        minima_not_used_pos[i] = n*i;

    vector<int> res_pos( n );

    for ( int i=0; i<n; i++ )
        res_pos[i] = minima_not_used_pos[i]++;

    for ( int i=n-1; i>=0; i-- )
    {
        int next_pos = min( n-1, i+v2[i] );

        res_pos[i] = minima_not_used_pos[next_pos]++;
    }

    vector< pair<int,int> > vec_to_sort;

    for ( int i=0; i<n; i++ )
        vec_to_sort.push_back({ res_pos[i], v1[i] });

    sort( vec_to_sort.begin(), vec_to_sort.end() );

    for ( auto& el : vec_to_sort )
        cout << el.second << ' ';

    return 0;
}
→ Reply