### maity_amit_2003's blog

By maity_amit_2003, history, 2 months ago,

Hi, This side, Amit Maity.
Codeforces Round #847 (Div. 3) | Codeforces Round 847 (Div. 3)

### 1790A - Polycarp and the Day of Pi

Idea: maity_amit_2003
Hola, You know the value of PI, right?
Then why not write this PI value as a string form PI = "314159265358979323846264338327950288419716939937510"
also in the question, they mentioned that it will be a maximum length of 30.
so, then just iterate over the given input and found the maximum match.

#### Submission: 190774194

void solve(){
string pi = "314159265358979323846264338327950288419716939937510";
string st;
cin>>st;
int i = 0;
for(;i<st.length();i++){
if(pi[i]!=st[i]) break;
}
cout<<i<<endl;
}


### 1790B - Taisia and Dice

Idea: maity_amit_2003
They give nth term sum as s and n-1 th term sum as r. so, one term must be s-r.
After printing s-r we have now the n-1 place to fill, right? also we need to keep in mind that at every remaining n-1 box we need to fill at least one. so, why not fill that first by one and then increase by one up to the r not reaches zero?

#### Submission: 190785474

void solve(){
int n,s,r;
cin>>n>>s>>r;
cout<<s-r<<" ";
vector<int> arr(n-1,0);
int idx = 0;
while(r!=0){
arr[idx]+=1;
idx = (idx+1)%(n-1);
r--;
}
for(auto it:arr) cout<<it<<" ";
cout<<endl;
}


### 1790C - Premutation

Idea: maity_amit_2003
As the question states that there will be given permutations but one element will be missing. You need to find the exact permutation that we can make. So, from this, we can say, that this question is like one after another, which means it depends one after another, sequence matter,s and some sequence is already given, we just need to connect.
So, we can apply here Topo Sort for calculating the final answer.
This question is generally based on one famous question Alien Dictionary.

#### Submission: 190843361

vector<int> helper(int V,vector<int> adj[]){
vector<int> ans;
vector<int> in(V,0);
for(int i=1;i<V;i++){
}
queue<int> q;
for(int i=1;i<V;i++) if(in[i]==0) q.push(i);
while(q.size()!=0){
int node = q.front();
q.pop();
ans.push_back(node);
in[it]--;
if(in[it]==0) q.push(it);
}
}
return ans;
}
void solve()

int n;
cin>>n;
vector<vector<int>> arr;
for(int i=0;i<n;i++){
vector<int> temp(n);
for(int j=1;j<n;j++) cin>>temp[j];
for(int i=2;i<n;i++){
}
}
for(auto it:ans) cout<<it<<" ";
cout<<endl;
}


### 1790D - Matryoshkas

Idea: maity_amit_2003
This question basically states that to find a set of consecutive positive integers, how many we can make this set?
This will contain consecutive no same element will exist.
So, why are you waiting just use Map and store all the elements, once again use Map not Unordered Map, here ordered matters, which means the array will be increasing, so.
And iterate over the map up to the map not empty and try to find the next consecutive element.

#### Submission: 190855892

void solve(){
int n;
cin>>n;
map<int,int> mp;
for(int i=0;i<n;i++){
int temp; cin>>temp;
mp[temp]++;
}
int cnt = 0;
while(mp.size()!=0){
int start = mp.begin()->first;
while(mp.count(start)>0){
mp[start]--;
if(mp[start]==0) mp.erase(start);
start++;
}
cnt++;
}
cout<<cnt<<endl;
}


If you like, please upvote

• +10

 » 2 months ago, # | ← Rev. 3 →   +1 I think your implementation of Problem C is Quite Complex. Hint 1Try to traverse the array column-wise for 1st column. Some More observation?The number with the highest frequency in the first column will be the First Number.cout << first_num << " "; Got it? No? Here we go!Save the first_num number as prev = first_numNow traverse the array column-wise from the 2nd column itself. for(int j= 0;j
 » 2 months ago, # | ← Rev. 3 →   +11 Hi, for a large constraint of r(~1e9) in Problem B, your code will give TLE. Instead, you can code like this int z=r/(n-1),y=r%(n-1); fi(n-1) { if(y) { cout<
 » 2 months ago, # | ← Rev. 2 →   0 Here's my solution for problem C. link