### nipul1's blog

By nipul1, history, 2 years ago,

yesterday I had a coding interview in which I was asked the following problem which I was not able to solve. please help me to figure out an approach for this problem.

Problem: Alex has a permutation of first n natural numbers in an array A for this permutation he has calculated another array B which is done as follows

B[i] will contain the number of elements on left of index i which are bigger then a[i], now somehow Array A is lost then we have to regenerate the array A from array B.

• +4

By nipul1, history, 2 years ago,

Problem My approach was to keep the multiplication factors in stack and pop them when a bracket ends

code

• 0

By nipul1, history, 2 years ago,

• +1

By nipul1, history, 2 years ago,

Problem

My Approach
ans = 0
according to me if some node gets broken then all its children will become independent subtree hence , ans +=  number of children of this node;
and for all ancestors number of children -1 should be added to answer

for solving queries I have precalculated answer for each of the node using
following code

vector<int > T[100001];
int vals[100001];
bool visit[100001]={0};
void dfs(int s,int prev){
visit[s]=1;
vals[s]=prev+T[s].size();
if(s!=1) vals[s]--;
for(auto x: T[s]){
if(!visit[x]){
dfs(x,prev+T[s].size()-1);
}
}
}



• +1

By nipul1, history, 2 years ago,

Problem

My Observations 1) among all the people who have same choices at most one could be satisfied. so I removed all except one. 2) now I without proper reasoning I thought that some food groups will form and for each group its size — 1 will be added to answer. 3) I coded this approach using DSU and it worked I got an AC

but the problem is I am not able to justify the reasoning behind point number 2

My Solution Please tell me how my assumption is correct. Thanks and Regards

• 0

By nipul1, history, 3 years ago,

Hi CF community Xenia and Weights I am thinking about this problem past 3 days and not got any approach in my mind reading editorial also didn't helped me (for this problem) please share your approaches and how did you solved it Thanks and regards

• 0

By nipul1, history, 3 years ago,

Problem George and Job

TLE on test 55

TLE on test 58

Accepted but with random fixes based upon test data

I request the community to please suggest some proper fixes if exists in my code so that it can be accepted without using test-case based fixes

Thanks and Regards .

• -17

By nipul1, history, 3 years ago,

Please suggest some problems related to priority queue concept as Codeforces data structure tag is quite bigger . Thanks and regards...

• -11

By nipul1, history, 3 years ago,

I am trying Problem . Please Tell me what's wrong in it Submission

• 0

By nipul1, history, 3 years ago,

I am trying problem Problem using dijkstra algorithm. my submission is submission please tell me where I'm wrong in this .

• +3

By nipul1, history, 3 years ago,

is it a common issue with atcoder or a temporary problem ? I have tried same thing many times but the results were same , please suggest some way to get out of this problem .

• +14

By nipul1, history, 3 years ago,

https://codeforces.com/contest/1181/problem/D

Data Structure used

First ,of all I have calculated number of times a city has hosted olympiad second ,I have associated all cites which have hosted same number of times

//JSD
#include<iostream>
#include<set>
#include<vector>
#define ll long long
#include<map>
using namespace std;
int main(){
int n,m,q,a;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m>>q;
int Freq[m+1]={0};
for(int i=0;i<n;i++){
cin>>a;
Freq[a]++;
}
int maa=0;
for(int i=0;i<=m;i++){
maa=max(maa,Freq[i]);
}
vector<int > mpq[maa+1];
for(int i=1;i<=m;i++){
mpq[Freq[i]].push_back(i);
}
vector<int > ans;
int count=0;
set<int > s;
for(ll i=0;i<=maa;i++){
for(auto x: mpq[i]){
s.insert(x);
}
for(auto x: s){
ans.push_back(x);
}
}
while(q--){
ll p;
cin>>p;
p-=(n+1);
if(p<ans.size()){
cout<<ans[p];
}
else{
cout<<(p-ans.size())%m+1;
}
cout<<"\n";
}
return 0;
}


• -16