Showing posts with label Graph. Show all posts
Showing posts with label Graph. 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}
Posted by at No comments:
Labels: , ,

Tuesday, 4 May 2021

A simple Cycle detection Problem using DFS :: Codeforces 977E

 Problem Link

In this problem several connected components are given, we need to find number of such components with cycle.

A components is contain a cycle if and only if all of its vertices has degree exactly 2.

To find connected components of the graph, we will use  a simple dfs through unvisited nodes. You can learn dfs from here

After that we will check if all the vertices has degree exactly 2 or not.

Official Editorial

Code:

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
///the connected component is a cycle iff the degree of each its vertex equals to 2
const int maxn=200005;
vector<int>edge[maxn],connected;
int vis[maxn],degree[maxn];
int cnt=0;
void dfs(int u){
    vis[u]=1;
    connected.pb(u);
    for(auto it:edge[u]){
        if(vis[it]==0){
            dfs(it);
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        edge[u].pb(v);
        edge[v].pb(u);
        degree[u]++;
        degree[v]++;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            connected.clear();
            dfs(i);
            bool ok=1;
            for(auto it:connected){
                if(degree[it]!=2){
                    ok=0;
                }
            }
            if(ok){
                cnt++;
            }
        }
    }
    cout << cnt << endl;
}
Posted by at No comments:
Labels: , , ,

Friday, 2 April 2021

Guilty Prince Lightoj-1012

Problem link

This problem is straightforward implementation of floodfill algorithm.

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(false);
int dx4[] = {0, 0, 1, -1}; ///direction arrays
int dy4[] = {1, -1, 0, 0};
const int maxn=25;
char s[maxn][maxn];
map<pair<int,int>,int>vis;
int w,h;
int ans;
void init(){
    ans=0;
    vis.clear();
}
void bfs(int posi,int posj){
    pair<int,int>x={posi,posj};
    queue<pair<int,int> > q;
    q.push(x);
    vis[x]=1;
    while(!q.empty()){
        pair<int,int>u=q.front();
        q.pop();
        int x=u.first;
        int y=u.second;
        for(int i=0;i<4;i++){
            int nx=x+dx4[i];
            int ny=y+dy4[i];
            if(nx>=0 && nx<h && ny>=0 && ny<w && s[nx][ny]=='.' && vis[mp(nx,ny)]==0){
                ans++;
                vis[mp(nx,ny)]++;
                q.push(mp(nx,ny));           
            }
        }
    }
}
int tc=0;
///solution
void solution(){
    cin>>w>>h;
    int posi,posj;
    init();
    for(int i=0;i<h;i++){
          for(int j=0;j<w;j++){
        cin>>s[i][j];
              if(s[i][j]=='@'){
                  posi=i;
                  posj=j;
              }
          }
    }
    bfs(posi,posj);
    cout<< "Case "<< ++tc <<": "<< ans+1 << endl;
}
signed main()
{
    IOS
    int t;
    t=1;
    cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
Posted by at No comments:
Labels: , ,

Thursday, 1 April 2021

Back to Underworld Lightoj 1009 | An Easy Bfs/Dfs Problem

Problem link

Lets put a node is vampire, then all the nodes adjacent with it will be lykans.

Thats why we just need to traverse all the node by a simple bfs or dfs, by toggling nodes states( if parents is vampire then it will be lykans)

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define f0(n) for(int i=0;i<n;i++)
#define pb push_back
#define IOS ios::sync_with_stdio(false);
const int maxn=20004;
vector<int>adj[maxn];
int vis[maxn];
///solution
void init(){
    f0(maxn){
        adj[i].clear();
        vis[i]=0;
    }
}
int bfs(int x){
    queue<int>q;
    int va=0,ly=0;
    q.push(x);
    vis[x]=1;
    va++;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto v:adj[u]){
            if(vis[v]==0){
                if(vis[u]==1){
                    vis[v]=2;
                    ly++;
                }
                else {vis[v]=1;va++;}
                q.push(v);
            }
        }
    }
    return max(va,ly);
}
int tc=0;
void solution(){
    init();
    int n;
    cin>>n;
    f0(n){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int ans=0;
    for(int i=1;i<=20000;i++){
        if(vis[i]==0 && !adj[i].empty()){
            ans+=bfs(i);
        }
    }
    cout << "Case "<<++tc << ": " << ans << endl;
}
signed main()
{
    IOS
    int t;
    t=1;
    cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
Posted by at No comments:
Labels: , ,
Subscribe to: Posts (Atom)

Monkey Banana Problem lightoj 1004

  In this problem we will check which adjacent cell will benefits the monkey best. For this, we will check all possible solution of this pro...