maity_amit_2003's blog

By maity_amit_2003, history, 2 months ago, In English

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;
   int i = 0;
   	 if(pi[i]!=st[i]) break;

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;
   cout<<s-r<<" ";
   vector<int> arr(n-1,0);
   int idx = 0;
   	  idx = (idx+1)%(n-1);
   for(auto it:arr) cout<<it<<" ";

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);
            int node = q.front();
            for(auto it:adj[node]){
                if(in[it]==0) q.push(it);
        return ans;
void solve()
   int 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++){
    vector<int> ans = helper(n+1,adj);
    for(auto it:ans) cout<<it<<" ";

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;
   map<int,int> mp;
   for(int i=0;i<n;i++){
   	  int temp; cin>>temp;
   int cnt = 0;
   	  int start = mp.begin()->first;
   	  	 if(mp[start]==0) mp.erase(start);

If you like, please upvote

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

2 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I think your implementation of Problem C is Quite Complex.

Hint 1
Some More observation?
Got it? No? Here we go!
2 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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

like this

This 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

2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's my solution for problem C. link