Codeforces Round #847 (Div. 3) | Tutorial of 4 Questions

Revision en1, by _maityamit, 2023-01-27 22:05:25

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

1790A - Polycarp and the Day of Pi

Idea: _maityamit
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: _maityamit
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: _maityamit
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: _maityamit
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

Tags contest, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English _maityamit 2023-01-27 22:05:25 4162 Initial revision (published)