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++){
for(auto it:adj[i]) in[it]++;
}
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);
for(auto it:adj[node]){
in[it]--;
if(in[it]==0) q.push(it);
}
}
return ans;
}
void solve()
int n;
cin>>n;
vector<vector<int>> arr;
vector<int> adj[n+1];
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++){
adj[temp[i-1]].push_back(temp[i]);
}
}
vector<int> ans = helper(n+1,adj);
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`

I think your implementation of

Problem Cis 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.

Hi, for a large constraint of r(~1e9) in Problem B, your code will give TLE. Instead, you can code

like thisThis will do the operation of r is O(1).

Problem C

Your implementation is quite complex, I saw a small observation, the first and last element of the array has its occurrence in only one column while the rest have two columns. So, our first and last elements are found, since they have only one occurrence. For others, the highest(of the two) will be the answer.

Code for better understanding

Here's my solution for problem C. link