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; }