nipul1's blog

By nipul1, history, 4 years ago, In English

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.

Full text and comments »

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

By nipul1, history, 4 years ago, In English

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

code

Please Help I am unable to find the mistake

Full text and comments »

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

By nipul1, history, 4 years ago, In English

Problem My submission

I am getting wrong answer on test 40. Please help me to figure out my mistake with this submission

Full text and comments »

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

By nipul1, history, 4 years ago, In English

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);
        }
    }
}

Full text and comments »

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

By nipul1, history, 4 years ago, In English

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

Full text and comments »

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

By nipul1, history, 4 years ago, In English

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

Full text and comments »

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

By nipul1, history, 4 years ago, In English

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 .

Full text and comments »

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

By nipul1, history, 5 years ago, In English

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

Full text and comments »

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

By nipul1, history, 5 years ago, In English

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

Thanks in advanced.

Full text and comments »

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

By nipul1, history, 5 years ago, In English

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

Thanks in Advanced.

Full text and comments »

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

By nipul1, history, 5 years ago, In English

I am trying forgot password option on atcoder and a mail with a link to reset password comes. but when I open this link it shows page not found error

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 .

Thanks in advance

Full text and comments »

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

By nipul1, history, 5 years ago, In English

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;
}

Full text and comments »

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