→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
43:19:33
Зарегистрироваться »

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Sahilamin219

Google Question Asked Onsite

Автор Sahilamin219, история, 9 месяцев назад, По-английски

count array : for a given array it stores, for each ith element number of element greater than it's value from the left.

For a given number N , there exits an permutation array (1,N) such that it gives you same count array. You are given an count array and you have to find original array.

Example : count array => 0 0 0 1 2 0

then original array would be => 1 2 5 4 3 6

Required Solution was Nlog(N).

Hope the question is clear, if there's any doubt plz comment.

For my person experience click here

Sahilamin219
9 месяцев назад
18

Комментарии (18)

Написать комментарий?

philikote

9 месяцев назад, # |

← Rev. 4 →

var1

// Variant 1
#include <iostream>
#include <vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, tmp;
	cin >> n;

	vector <int> a(n);
	vector <int> abc(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		abc[i] = (i + 1);
	}
	for (int i = n - 1; i >= 0; i--) {
		tmp = a[i];
		a[i] = abc[abc.size() - 1 - tmp];
		abc.erase(abc.begin() + abc.size() - 1 - tmp);
	}

	for (int i = 0; i < n; i++)
		cout << a[i] << ' ';
}

var2

// Variant 2
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, tmp;
	cin >> n;

	vector <int> a(n);
	unordered_set <int> abc;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		abc.insert(n - i);
	}
	for (int i = n - 1; i >= 0; i--) {
		auto itr = abc.begin();

		for (int j = 0; j < a[i]; j++)
			++itr;

		a[i] = *(itr);
		abc.erase(a[i]);
	}

	for (int i = 0; i < n; i++)
		cout << a[i] << ' ';
}

→ Ответить

Kefrov

9 месяцев назад, # |

← Rev. 2 →

+13

Initialise an ordered_set containing integers from 1 to N. You'll be constructing the original array in reverse, because we can make this observation: Consider the element with index N, we know that all the other numbers of the permutation are to the left of it, we can now deduce which number it is thanks to count_array[N]. The log(N) part of the complexity comes from searching in the ordered_set using find_by_order() and removing every element we find so far.

Solution

#include <iostream>
using namespace std;

// Including ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

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

    int N;
    cin >> N;
    int count_arr[N];
    for (int i = 0; i < N; i++) cin >> count_arr[i];

    int oset_size = N;
    ordered_set remaining;
    for (int i = 1; i <= N; i++) remaining.insert(i);

    int original_arr[N];
    int order;
    for (int i = N - 1; i >= 0; i--) {
        order = oset_size - count_arr[i] - 1;
        original_arr[i] = *remaining.find_by_order(order);
        remaining.erase(original_arr[i]);
        oset_size--;
    }

    for (int i = 0; i < N; i++) cout << original_arr[i] << " ";

    return 0;
}

→ Ответить

not_ahmed_hamed

9 месяцев назад, # |

First of all, only the order of the elements does matter, the values themselves don't, so this array 1 2 3 4 is equivalent to this 1 3 4 6.

if cnt[i] = x means that we can shift the subarray (i, i-x) by 1. For example

Permu : 1 2 3 4 5 6

Count : x x x x 2 x

Permu :1 2 4 5 3 6

The subarray $$$[1,i-1]$$$ still has the same sorted order (only order does matter).

So how to do this shifting efficiently? Because the subarray is still sorted, and let k be $$$count[i]$$$, then $$$Permu[i] =$$$ the $$$k_{th}$$$ largest value in the current subarray which can be found using ordered_set (PBDS).

Code

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), p(n + 1);
    orderd_set s;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s.insert(i);
    }
    for (int i = n; i >= 1; i--)
    {
        int k = s.size() - a[i] - 1;
        if (k < 0)
            return cout << "No solution\n", void();
        auto it = s.find_by_order(k); // Kth largest
        p[i] = *it;
        s.erase(it);
    }
    for (int i = 1; i <= n; i++)
        cout << p[i] << " ";
}

→ Ответить

CrackInTheSky

9 месяцев назад, # ^ |

How about doing something like this : finding first zero from right, the element at this index(suppose ith) is bound to be current_max available. Then we can decrease array[i+1,n] by 1. And now current_max available will be decreased by 1 and also replace ith element by INF. Range update of (i,n) can be done by lazy seg trees and rightmost 0 can also be found using seg tree. TC : O(nlogn) Is there a better way to do update of (i,n) by -1 ?

→ Ответить

not_ahmed_hamed

9 месяцев назад, # ^ |

I didn't understand, why do we care about cur_max?

→ Ответить

CrackInTheSky

9 месяцев назад, # ^ |

because cur_max will be filled at rightmost 0 in every iteration.(i meant in permutaion array)

arr: 0 0 0 1 2 0 0 0 0 1 2 6 0 0 5 0 1 6 0 0 5 4 0 6 0 0 5 4 3 6 0 2 5 4 3 6 1 2 5 4 3 6 by current_max i simply meant unused max.

→ Ответить

not_ahmed_hamed

9 месяцев назад, # ^ |

IDK if it's working, but can you prove this solution?

→ Ответить

CrackInTheSky

9 месяцев назад, # ^ |

suppose currently in count array there r multiple 0s. Then max element available must be placed at rightmost pos, because if we place at any other place, condition for 0s after that index can't be satisfied. Second, once we place the element at ith(rightmost 0), we have placed one greater element to all pos in its right, so decrease (i+1,n) by 1 in count array. If u think it's wrong, a counter case will be highly welcome.

→ Ответить

not_ahmed_hamed

9 месяцев назад, # ^ |

Yup got u. This might work. Write a code and pass it to me

some cases I wrote:

→ Ответить

CrackInTheSky

9 месяцев назад, # ^ |

https://ideone.com/72yjBz

→ Ответить

pokeland157

9 месяцев назад, # ^ |

+10

are data structures like ordered set permitted to use in interviews?

→ Ответить

Sahilamin219

9 месяцев назад, # ^ |

No, but i guess its better to say something instead of being blank !

→ Ответить

not_ahmed_hamed

9 месяцев назад, # ^ |

No I guess, but you can implement the ordered set with binary indexed tree and use it

→ Ответить

Astroflexx

9 месяцев назад, # |

It's just an observation/constructive problem. Start with a sorted array from 1 to N, and update the array from right to left, whenever count[i] is not 0, take the count[i]th number on the left from the index i and put it at index i and put the current number at i in i — 1 (to maintain the sorted behavior).

→ Ответить

gitgudmonsta

9 месяцев назад, # |

← Rev. 2 →

I think Kefrov's solution is pretty neat.

However, if you can't usePBDSin an interview, you can usestd::nextfor this specific problem as std::set is sorted by default. Not sure about something similar in other languages.

*(std::next(set.begin(), index)is equivalent to*(__gnu_pbds::ordered_set.find_by_order(order))

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> //.

using i64 = long long;

void solve() {
    int n; std::cin >> n;
    
    std::vector<int> count(n);
    for(int& i: count) std::cin >> i;
        
    std::set<int> st;
    for(int i = 1; i <= n; i++) st.insert(i);
    
    std::vector<int> permutation(n);
    int sz = n;
    
    for(int i = n - 1; i >= 0; i--) {
        int pos = sz - count[i] - 1;
        int ele = *(std::next(st.begin(), pos));
        permutation[i] = ele;
        st.erase(ele);
        --sz;
    }
    
    for(int i: permutation) std::cout << i << ' ';
    std::cout << '\n';
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    
    #ifndef ONLINE_JUDGE
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #endif
    
    solve();
    return 0;
}

// g++ -std=c++20 <filename>.cpp

→ Ответить

TheBhediyaOfDalalStreet

9 месяцев назад, # ^ |

Thanks so much for applying with us

Hi gitgudmonsta,

Following up on your recent interview with Google, we have decided not to proceed with your application at this time. Although this role didn't work out, we may contact you if we come across another opening that we think could interest you and that matches your skills and experience.

Also, if you applied for any other roles with us recently, look for an update on them soon.

→ Ответить

AKMalice

9 месяцев назад, # |

https://codeforces.net/edu/course/2/lesson/4/3/practice/contest/274545/problem/B

→ Ответить

SNX03

9 месяцев назад, # |

It’s a standard segment tree problem of generating the permutation using inversion array.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.12.2024 22:15:28 (j2).

Десктопная версия, переключиться на мобильную.

При поддержке