মোরসালিনের সিপি ব্লগ: Atcoder

Showing posts with label Atcoder. Show all posts

Sunday, 6 June 2021

Atcoder Beginner Contest 204 (A to D) Explanation with code

Contest Link

Problem A:

There are three players playing rock, paper, scissors. Given first two players hand thrown. What will be the last player hand shape if they have a draw.

Explanation:

1.If the two players has same type of hand shape, then the last player must have the same hand shape too.

2. If the two players has different type of hand shape, then the last player must have a hand shape other than the each of the players.

Code of A:

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);

///solution
void solution(){
    int x,y;
    cin>>x>>y;
    if(x==y){
    	cout << x << endl;
    }
    else cout << (3-(x+y)) << endl;
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

Problem B:

Explanation: We had to calculate the sum of max(tree[i]-10,0) for every tree i from 1 to n.

Code of B:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define IOS ios::sync_with_stdio(false);
///solution
void solution(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=0;i<n;i++){
    	int x;
    	cin>>x;
    	if(x>10){
    		ans+= (x-10);
    	}
    }
    cout << ans << endl;
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

Problem C:

This problem asks that how many ways we can choose two cities as one as origin and one as destination.

Explanation: We can go a city x from a city y iff the city x is connected to y. For this purpose we just need to check how many cities are connected to city y. where y will be every city from 1 to n.

Code of C:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define IOS ios::sync_with_stdio(false);
const int maxn=2005;
int ans=0;
vector<int>adj[maxn];
void bfs(int u){
	int vis[maxn];
	ms(vis);
	vis[u]=1;
	int cnt=0;
	queue<int>q;
	q.push(u);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<adj[x].size();i++){
			int v=adj[x][i];
			if(vis[v]==0){
				q.push(v);
				vis[v]=1;
				cnt++;
			}
		}
	}
	ans+=cnt;
}
///solution
void solution(){
    int n,m;
    cin>>n>>m;
    ans=n;
    int mark[n+1];
    ms(mark);
    for(int i=0;i<m;i++){
    	int u,v;
    	cin>>u>>v;
    	adj[u].pb(v);
    }
    for(int i=1;i<=n;i++){
    	bfs(i);
    }
    cout << ans << endl;
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

Problem D:

we have a set. we have to partition it into two sets. Lets say,

S1 = sum of first set

S2 = sum of second set.

then our answer will be maximum of S1 and S2. We had partition this sets such a way that the answer will be minimum.

Explanation:

To do such task in efficient way we have to go with a DP solution.

where,

dp[i][j]==true if some subset has a sum equal to j. for the first i elements. Otherwise 0.

where, (1<=i<=n), (0<=j<=sum)

Then we just check that if we can choose such j where there has an subset. where( 0<=j<=sum/2)

Then this is valid partition where we can partitioned these two sets,

S1 = sum-j;

S2 = j;

Code of D:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);
int Mini(int arr[], int n)
{
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += arr[i];
  bool dp[n+1][sum+1];
  for (int i = 0; i <= n; i++)
    dp[i][0] = true;
  for (int i = 1; i <= sum; i++)
    dp[0][i] = false;
  for (int i=1; i<=n; i++)
  {
    for (int j=1; j<=sum; j++)
    {
      dp[i][j] = dp[i-1][j];
      if (arr[i-1] <= j)
        dp[i][j] |= dp[i-1][j-arr[i-1]];
    }
  }
  int diff = INT_MAX;
  for (int j=sum/2; j>=0; j--)
  {
    if (dp[n][j] == true)
    {
      diff = max(sum-j,j);
      break;
    }
  }
  return diff;
}
///solution
void solution(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    cout << Mini(arr,n);
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}

Tuesday, 16 March 2021

F - Coprime Present :: Panasonic Programming Contest (AtCoder Beginner Contest 195)

The main observations of this problem is if two number is not coprime, there largest prime factors of their greatest common divisors will not exceed 72.

So, we just check all possible pairs of numbers from a to b. hence there will be atmost 20 primes, upto 72. we can apply a bitmask dp approach to check which numbers will benefits us most.

Problem link

Official Editorial

Code:

/// Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);
///solution
void solution(){
    ll primes[20]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,31, 37, 41, 43, 47, 53, 59, 61, 67, 71};
    vector<ll>dp((1<<20));
    ll a,b;
    cin>>a>>b;
    dp[0]=1;
    for(ll i=a;i<=b;i++){
        int bit=0;
        for(int j=0;j<20;j++){
            if(i%primes[j]==0) bit|=(1<<j);
            }
        for(int j=0;j<(1<<20);j++){
               if((j&bit)==0)dp[j|bit] += dp[j];
            }
    }
    ll ans=0;
    for(int i=0;i<(1<<20);i++){
        ans+=dp[i];
    }
    cout << ans << endl;
}
signed main()
{
    IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
    solution();
    }
    return 0;
}

Monday, 8 February 2021

C - Digital Graffiti Atcoder Beginner Contest 191 Code with Explanation

Problem Link

Explanation: We need to find number of sides, if all '#' creates a polygon itself. For this purpose we need to find number of sides of this shape. Lets find if a cell is a side or not.

    1   2   3   4
1   .   .   .   .

2   .   #   #   .

3   .   #   #   .

4   .   .   .   .

Observations: If 4 adjacent cells has odd number of '#' it will contain a side of polygon. If a cell is (i,j) we will count '#' in cells (i,j),(i+1,j),(i+1,j+1),(i,j+1) for cell i,j.

for (1,1) >> Number of # is 1 at(2,2)

for(1,2)>> Number of # is 2 at(2,2 and 2,3)

for(1,3)>> Number of # is 1 at(2,3)

...

In this way we will get the number of sides of the polygon.

Code

void solution(){
    int h,w;
    cin>>h>>w;
    string s[h];
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    int ans=0;
    for(int i=0;i<h-1;i++){
        for(int j=0;j<w-1;j++){
            int cnt=0;
            if(s[i][j]=='#')cnt++;
            if(s[i+1][j]=='#')cnt++;
            if(s[i+1][j+1]=='#')cnt++;
            if(s[i][j+1]=='#')cnt++;
            if(cnt%2!=0)ans++;
        }
    }
    cout << ans << endl;
}

মোরসালিনের সিপি ব্লগ