Sunday 7 November 2021

Leetcode 118.Pascal's Triangle

 Problem Link: Click

This is a simple pascal triangle problem. One matter we have to keep in mind is we may have resize the vector size and allocate them carefully. Hence we have to return the vector.

Code:


class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > vec(numRows);
        for(int i=0;i<numRows;i++){
            vec[i].resize(i+1);
            vec[i][0]=1;
            vec[i][i]=1;
        }
        for(int i=2;i<numRows;i++){
            for(int j=1;j<i;j++){
                vec[i][j]=vec[i-1][j]+vec[i-1][j-1];
            }
        }
        return vec;
    }
};
Posted by at No comments:
Labels: , ,

Leetcode 73. Set Matrix Zeroes

 Problem link:click

This is very easy problem. In this problem you have to make all elements of a row or a column to zero if any element of the matrix of the specific row or column is zero. For this purpose we can take the first row and the first column as a flag of the row and column. If any element of a row or column is zero we will make the flag of first row and columns as zero.

For making all elements of the row and column zero we just have to check if matrix[i][0]==0 or matrix[0][j]==0.

Code: 

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int col=matrix[0].size(),row=matrix.size(),col0=1;
        for(int i=0;i<row;i++){
            if(matrix[i][0]==0)col0=0;
            for(int j=1;j<col;j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        for(int i=row-1;i>=0;i--){
            for(int j=col-1;j>=1;j--){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j]=0;
                }
            }
            if(col0==0)matrix[i][0]=0;
        }
    }
};
Posted by at No comments:
Labels: , ,

Friday 11 June 2021

Another Problem About Dividing Numbers :: Codeforces Round 725 D

Problem link

In this problem you will be given two integer number a and b. You need to make a and b equal in exactly k operation(s).  In one operation you can either,

  • Take an integer ( and should be divisible by ) and replace with
  • Take an integer
    • (and should be divisible by ) and replace with .

Observations: If we at least  need x moves to make a and b equal and we have at most y moves which is total number of moves we can make in total. A move is choosing such a C discussing above. Then we can also make a and b equal by x+1,x+2,x+3.......y-2,y-1,y moves. [for better understanding a paperwork may help]

Explanation:

For finding the minimum number of moves to make a and b (if a!=b) are equal will be 1 or 2. 

>>if gcd(a,b)==min(a,b) then it will be 1.

lets say, a=36 and b=12;

gcd(36,12) = min(36,12) = 12 

we can make a=12 by dividing 36 by 3 in one move.

>>if gcd(a,b)!=min(a,b) then it will be 2. Because we need to divide both a and b to make equal to its gcd.

For finding the at most moves we have, we had to find number of prime factors both for a and b. because at most we can divide them until they left any prime factors.

For calculating the Number of prime factors. we will be needed prime numbers. For this purpose a simple sieve will work fine.

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
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define int long long
#define IOS ios::sync_with_stdio(false);
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
const int maxn=100005;
bitset<maxn+5>bs;
vector<int> prime;
void seive(){
  bs.set();
  bs[0]=0;
  bs[1]=0;
  for(int i=2;i<maxn;i++){
    if(bs[i]){
      prime.pb(i);
      for(int j = i*i; j<maxn;j+=i)bs[j]=0;
    }
  }
}
///solution
void solution(){
    int a,b,k;
    cin>>a>>b>>k;
    if(a==b && k==1){
        cout << "NO\n";
        return;
    }
    int cnta=0,cntb=0,now=a;
    for(auto it:prime){
      if(it*it>now){
        break;
      }
      while(now%it == 0){
        now/=it;
        cnta++;
      }
    }
    if(now>1)cnta++;
    now=b;
    for(auto it:prime){
      if(it*it>now )break;
      while(now%it == 0){
        now/=it;
        cntb++;
      }
    }
    if(now>1)cntb++;

    int x=gcd(a,b);
    int atmost=cnta+cntb,least=0;
    if(x==min(a,b))least=1;
    else least=2;
    if(least<=k && atmost>=k){
      cout << "YES\n";
    }
    else cout << "NO\n";
}
signed main()
{
  IOS
    int t;
    t=1;
    seive();
    cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
Posted by at 2 comments:
Labels: ,

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: , ,

Wednesday 2 June 2021

Solving a BigInteger problem UVA 10523 - Very Easy !!!

Problem link

This is a straightforward problem of of java BigInteger . Learn it frome here .

Code:

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.math.BigInteger;
import java.util.Scanner;
public class Main{

	public static void main(String[] args){
		Scanner scn = new Scanner(System.in);
		BigInteger tot,temp;
		int n,a;
		while(scn.hasNextInt()){
			n=scn.nextInt();
			a=scn.nextInt();

			tot=new BigInteger("0");
			temp=BigInteger.valueOf(a);

			for(int i=1;i<=n;i++){
				tot=tot.add(BigInteger.valueOf(i).multiply(temp.pow(i)));
			}
			System.out.println(tot);
		} 
	}
}
Posted by at No comments:
Labels: , ,

Tuesday 4 May 2021

UVA 10110 - Light, more light

In this problem there will be a number given.

we had to find if the n'th light is on or off? if a light is toggle odd number of time than it is on otherwise its off.

Observations: a number has odd number of factors if and only if it is a perfect square.

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n;
    while(1){
        cin>>n;
        if(n==0){
            break;
        }
        ///just has to check n is a perfect square or not? because all of the perfect square only
        ///has odd number of factors. and if number of factors is odd then it will be on.
        ll xx= sqrt(n);
        if(xx*xx==n){
            cout << "yes\n";
        }
        else cout << "no\n";
    }
    return 0;
}
Posted by at No comments:
Labels: ,

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: , ,

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:

 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
/// 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;
}
Posted by at No comments:
Labels: , ,

Friday 26 February 2021

Solving a Problem With Bitmask DP Codeforces 550B

 Problem Link

In this problem the constraints is very low it can only be 15, that's why it gives a hints that it could be solve with bitmask.

Bitmask is a masking technique, by which we can have the all possible combination in 2^n complexity rather than n! complexity. To learn more about bitmask click here 

In this problem we have to calculate number of ways to choose a sum where number of elements in the sum is greater than 1 and the sum itself is at least l and at most r. And difference between maximum and minimum element which are contributed to the sum is at least x.

To do that we will check all possible subset of the set and check the requirements satisfies or not.

Code:

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define highest(x) numeric_limits<x>::max()
#define IOS ios::sync_with_stdio(false);
///solution
void solution(){
    ll n,l,r,x;
    cin>>n>>l>>r>>x;
    ll arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    ll ans=0;
    for(int i=0;i<=pow(2,n);i++){
        int cnt=0;
        ll sum=0,mini=highest(ll),maxx=0;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                cnt++;
                sum+=arr[j];
                mini=min(mini,arr[j]);
                maxx=max(maxx,arr[j]);
            }
        }
        if(sum>=l && sum<=r && cnt>=2 && maxx-mini>=x){
            ans++;
        }
    }
    cout << ans << endl;
}
signed main()
{
    IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah
  


Posted by at No comments:
Labels: , ,

Thursday 18 February 2021

Solving An Interactive Problem CF Round 700 Div2 C

First of all, what is an interactive problem?

read it from here

The blog says all about it, still i am showing it roughly and practically.

In interactive problem we have to grab input data from the problem on our demand. we have to make queries and if our query stand valid then the problem (interactor) give us some input and based on these inputs of some limited number of query we have to answer a valid result of this problem.

Lets see a problem,

problem link  

Problem statement:






 

 

Okay, Our hero Homer has an array which is a permutation, but hidden. We have to find any local minimum of the array in at most 100 queries. Wants to know more about local minimum click here









In each query we can get a value of any index we asks for. For finding local minimum we will run a binary search.

For every printf() function or cout << we have to flush

in C++, we can use cout.flush() or fflush(stdout)

Here is the official Editorial of this problem.

Code:

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int arr[maxn];
int n;
///solution
void take(int w){
    if(1<=w && w<=n){
        printf("? %d\n",w);
        fflush(stdout);
        scanf("%d",&arr[w]);
    }
}
void solution(){

   //cin>>n;
    scanf("%d",&n);
    int ans;
    arr[0]=n+1;
    arr[n+1]=n+1;
    int left=1, right=n;
    while(left<right){
        int mid=(left+right)/2;
        take(mid);
        take(mid+1);
        if(arr[mid+1]>arr[mid]){
            right=mid;
        }
        else left=mid+1;
    }
    printf("! %d\n",left);
    fflush(stdout);
}
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
    #endif
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

 





Posted by at No comments:
Labels: , ,

Tuesday 9 February 2021

Shortest Path? Toph Criterion 2021 Round 9 Explanation with code

Problem link

First of all we need to find the shortest paths from a source node S to destination node T of the given graph.

And secondly a node will be given say X and we need to find the minimum distance from node X to any node of the shortest paths.



For find that a node belongs to the shortest path or not? here is the observations,

we will run a bfs from source node and find the distances of all node from source. And again we will run another bfs from destination node and find the distance of all node from destination. If you have any doubt on bfs check the link

A node will be belong to any shortest path of the graph if distance from source + distance from destination of the node equal to the shortest path distance, in another word,

source_distance[i]+destination_distance[i] == source_distance[destination]

Now we had to find distance from any shortest path to the asking node. We can precalculate all the distances by running a bfs one more time. In this case we will push the nodes into the queue which are belong to the shortest paths and initialize the distance of these nodes as 0. This is also called Multisource bfs .

Code:

Read Full Editorial
Posted by at No comments:
Labels: , ,

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

Posted by at No comments:
Labels: ,

Friday 5 February 2021

All Possible Increasing Subsequences Lightoj 1085

First of all we will sort all A by non decreasing order and then we can find how many subsequence we can have by building a Binary indexed tree in the base of respective index.

To learn Binary indexed tree : BIT

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define CLR(x) memset(x, -1, sizeof(x))
#define CLR2d(x,m,n) memset(x, -1, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);

///for debug
vector<string> vec_splitter(string s) {    s += ',';vector<string> res;while(!s.empty()) {res.push_back(s.substr(0, s.find(',')));s = s.substr(s.find(',') + 1);}return res;}
void debug_out( vector<string> __attribute__ ((unused)) args,__attribute__ ((unused)) int idx,__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) { if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";stringstream ss; ss << H;cerr << args[idx] << " = " << ss.str();debug_out(args, idx + 1, LINE_NUM, T...);}
#define XOX
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
///debug template ends


int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
///modular arithmetic
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }  /// When MOD is prime.
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
///modular arithmetic template ends

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
        if(a.fi==b.fi)return a.se>b.se;
       return (a.first < b.first);
}
const int maxn=100005;
int BIT[maxn+5];
int n;
void update(int pos,int val){
    while(pos<=n){
        BIT[pos]+=val;
        BIT[pos]%=MOD;
        pos+=(pos& -pos);
    }
}
int query(int pos){
    int res=0;
    while(pos>0){
        res+=BIT[pos];
        res%=MOD;
        pos-=(pos & -pos);
    }
    return res;
}
///solution
int cs=0;
void solution(){
    ms(BIT);
    scanf("%lld",&n);
    vector<pair<int,int> > vp;
    for(int i=0;i<n;i++){
        int x;
        scanf("%lld",&x);
        vp.pb(mp(x,i+1));
    }
    sort(ALL(vp),sortinrev);
    for(int i=0;i<(int)vp.size();i++){
        int sum =1+query(vp[i].se-1);
        //debug(sum,vp[i].se);
        update(vp[i].se,sum);
    }
    printf("Case %lld: %lld\n",++cs,query(n));
}
signed main()
{
    IOS
    int t;
    t=1;
    //cin>>t;
    scanf("%lld",&t);
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah



Posted by at No comments:
Labels: ,

Binary Simulation Lightoj 1080

This is a pretty basic problem of range update and point query, we are solving this problem by Binary Indexed Tree data structure. Learn it from here: BIT

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define CLR(x) memset(x, -1, sizeof(x))
#define CLR2d(x,m,n) memset(x, -1, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);

///for debug
vector<string> vec_splitter(string s) {    s += ',';vector<string> res;while(!s.empty()) {res.push_back(s.substr(0, s.find(',')));s = s.substr(s.find(',') + 1);}return res;}
void debug_out( vector<string> __attribute__ ((unused)) args,__attribute__ ((unused)) int idx,__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) { if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";stringstream ss; ss << H;cerr << args[idx] << " = " << ss.str();debug_out(args, idx + 1, LINE_NUM, T...);}
#define XOX
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
///debug template ends


int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
///modular arithmetic
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }  /// When MOD is prime.
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
///modular arithmetic template ends

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}

///solution
int BIT[100005];
int n;
void update(int i,int val){
    while(i<=n){
        BIT[i]+=val;
        i+=(i&-i);
    }
}
int query(int i){
    int sum=0;
    while(i>0){
        sum+=BIT[i];
        i-=(i&-i);
    }
    return sum;
}
int cs=0;
void solution(){
    char s[100005];
    int q;
    scanf("%s%lld",s,&q);
    //cout << s << endl;
    n=strlen(s);
    ms(BIT);
    //cout << "Case "<< ++cs << ":\n";
    printf("Case %lld:\n",++cs);
    while(q--){
        getchar();
        char ch;
        //cin>>ch;
        scanf("%c",&ch);
        if(ch=='I'){
            int i,j;
            //cin>>i>>j;
            scanf("%lld%lld",&i,&j);
            update(i,1);
            update(j+1,-1);
        }
        else if(ch=='Q'){
            int i;
            //cin>>i;
            scanf("%lld",&i);
            int x=query(i);
            char ans;
            if(x%2==0){
                ans=s[i-1];
            }
            else{
                if(s[i-1]=='0')ans='1';
                else ans='0';
            }
            printf("%c\n",ans);
        }
    }
}
signed main()
{
    //IOS
    int t;
    t=1;
    //cin>>t;
    scanf("%lld",&t);
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah


Posted by at No comments:
Labels: ,

Sum of Factorials Lightoj 1189

 In this problem we will pre calculate all the factorial values upto 20(because the constraint). Then greedily we will just check can we take the value of factorial of any number.

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ins insert
#define IOS ios::sync_with_stdio(false);
using namespace std;
int main()
{
    IOS
    int t;
    cin>>t;
    ll fact[21];
    fact[0] = 1;
    for(int i=1;i<=20;i++)
    {
        fact[i] = fact[i-1]*i;
        //cout << fact[i] << endl;
    }
    for(int tc=1;tc<=t;tc++)
    {
        ll n;
        cin>>n;
        vector<int>vec;
        for(int i=20;i>=0;i--)
        {
            if(fact[i]<=n)
            {
                n-=fact[i];
                vec.pb(i);
            }
            if(n==0) break;
        }
        sort(vec.begin(),vec.end());
        cout << "Case "<< tc << ": ";
        if(n!=0) {cout <<"impossible\n";continue;}
        for(int i=0;i<vec.size();i++)
        {
            if(i>0 && i<vec.size())
                cout << "+";
            cout << vec[i] << "!";
        }
        cout << endl;
    }
    return 0;
}

Posted by at No comments:
Labels: ,

Conquering Keokradong Lightoj 1048

 we will check which value is most satisfied in the given number of nights k. For this purpose we will do binary search from highest distance of two campsites to sum of distance.

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define mp make_pair
//#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define tc(t) int t;scanf("%lld",&t);while(t--)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);
using namespace std;
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
signed main()
{
    IOS
    int tn=0;
    tc(t){
        int n,k;
        scanf("%lld%lld",&n,&k);
        int arr[n+1];
        int sum=0,max_val=0;
        f0(n+1){
            scanf("%lld",&arr[i]);
            sum+=arr[i];
            max_val=max(max_val,arr[i]);
            //cout << arr[i]<< endl;
        }
        int low=max_val;
        int high=sum;
        int mid;
        int ans=high;
        while(low<=high){
            mid=(low+high)/2;
            int time=0,pre=0;
           // cout << mid;
            for(int i=0;i<n+1;i++){
                pre+=arr[i];
                if(pre>mid){
                    time++;
                    pre=arr[i];
                }
            }
           // cout << " "<< time << endl;
            if(time<=k){
                high=mid-1;
                ans=mid;
            }
            else{
                low=mid+1;
            }
        }
        printf("Case %lld: %lld\n",++tn,ans);
        int pre=0;
        int nt=0;
        for(int i=0;i<n+1;i++){
            if(pre+arr[i]>ans){
                printf("%lld\n",pre);
                pre=0;
                i--;
                nt++;
            }
            else if(pre+arr[i]==ans){
                printf("%lld\n",pre+arr[i]);
                pre=0;
                nt++;
            }
            else if(k-nt==(n-i)){
                printf("%lld\n",pre+arr[i]);
                pre=0;
                nt++;
            }
            else pre+=arr[i];
        }
    }
    return 0;
}
///Alhamdulillah


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...