Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Блог пользователя samadeep

Ways to color Houses with fixed ends and no adjacent same colors

Автор samadeep, история, 7 недель назад, По-английски

Given a line of n houses where the color of the first house and nth house is fixed, find the number of ways to color the houses if given k colors in total where no adjacent houses can have same color.

One approach could be ways[i][color] is the number of ways to color ith index with a color. where 1 <= color <= k

Transition would be :

ways[i][color] += ways[i-1][color_prev] where 1 <= color , color_prev <= k and color_prev != color

What is a more optimised approach for O(n) probably ???

Полный текст и комментарии »

combinations, dynamic programming, interview

samadeep
7 недель назад
4

CF Blogs | Permutations on String | Number of Strings with no K consequetive equal letters

Автор samadeep, история, 13 месяцев назад, По-английски

Permuation Question : Number of Strings with no K consequetive equal letters given the string is made of lower case alphabets

Read here : Explanation It has beautiful solution using recurrence formulaes.

Basically the Recurrence is :
if k == n:    ways[n] = (power(26,k) - 26)
if n <= k - 1:   ways[n] = power(26,n)
else ways[n] = (countValid(n-1,k) + countValid(n-k,k))

You need to take care of modular arithmetic of course as the numbers get really large BTW it was there in Atlassain OA — best OA ever

C++

int64_t modularPower(int64_t b , int64_t e ) {
	
	int64_t MOD = 1e9 + 7;
	
    if ( MOD == 1) return 0; // Handling edge case

    int64_t r = 1;
    
    b = b % MOD;

    while (e > 0) {
        // If exponent is odd, multiply base with result
        if ( e % 2 == 1) {
            r = (r * b) % MOD;
        }

        // exponent must be even now
        e = e >> 1; // Equivalent to exponent /= 2
        b = (b * b) % MOD;
    }

    return r;
}

const int64_t MOD = 1e9 + 7;
void solve()
{
    int64_t N , K ;
    
    cin >> N >> K ;
    
    vector<int64_t> dp(N+1,-1);
    
    function< int64_t (int64_t)> dfs = [&]( int64_t n )
    {
    	if( dp[n] != -1 )
    	{
    		return dp[n];
    	}
    	
    	if( n == K ) return dp[n] = ( modularPower( 26 , K  ) - 26 );

    	if( n <= K - 1 ) return dp[n] =  modularPower( 26 , n); 
    	
    	if( dp[n-1] != -1 && dp[n-K] != -1  )
    	{
    		return dp[n] = dp[n-1] + dp[n-K];
    	}
    	else
    	{
    		return dp[n] = dfs( n-1 ) + dfs( n - K );
    	}
    };
    
    for( int i = 1 ; i < K ; i++ )
    {
    	dp[i] = modularPower( 26 , i ); 
    	dp[i] %= MOD ;
    } 
    
    dp[K] = modularPower( 26 , K  ) - 26;
    
    dp[K] %= MOD ;
    
    for( int i = K + 1 ; i <= N ; i++ )
    {
    	dp[i] = (dp[i-1] % MOD + dp[i-K] % MOD) % MOD  ;
    	dp[i] %= MOD ;
    }
    
    cout << dp[N] << endl;
    	
    
    
    cout << dfs( N ) << endl;
    
}


signed main()
{
    fastio;
    int t=1;
    cin >> t ;
    while(t--) solve();
    return 0;
}

python

import math
from functools import lru_cache

# Initialize a dictionary to store computed results
dp = [-1] * 100005 
def power(a, k, p = 10**9 + 7):
    res = 1
    a = a % p
    while k > 0:
        if k % 2 == 1:
            res = (res * a) % p
        k = k // 2
        a = (a * a) % p
    return res

def countValid(n, k):
    MOD = 10**9 + 7

    if dp[n] != -1:
        return dp[n]
    
    if k == n: 
        dp[n] = (power(26,k) - 26) % MOD
        return dp[n]
    
    if n <= k - 1:
        dp[n] = power(26,n)% MOD
        return dp[n]
    
    if dp[n-k] != -1 and dp[n-1] != -1:
        dp[n] = (dp[n-1]%MOD + dp[n-k]%MOD)%MOD
    else:
        dp[n] = (countValid(n-1,k)% MOD + countValid(n-k,k)% MOD)% MOD
    
    return dp[n]

countValid(1000,10)

Полный текст и комментарии »

permutations, strings, combinations

samadeep
13 месяцев назад
5

An Interesting Dyanmic Programming + Binary Search Problem

Автор samadeep, история, 13 месяцев назад, По-английски

An array arr of n integers is to be divided into different groups such that each element belongs to exactly one group and the size of each group is at least m.

The cost of the division is defined as the maximum value of the difference between the maximum and minimum elements of a particular group. For example, if an array [1, 2, 3, 4, 5] is divided into two groups [1, 3], [2, 4, 5], the cost is max(3 — 1, 5 — 2) = 3

Given arr and an integer m, find the minimum possible cost of dividing the array into groups of size greater than or equal to m. Example : Suppose n = 5, arr = [5, 11, 13, 4, 12], and m = 2. It is optimal to divide the array into two groups [5, 4] and [11, 13, 12] with the cost max(5 — 4, 13 — 11) = 2.

Полный текст и комментарии »

dp, binary search, problem

samadeep
13 месяцев назад
17

My Solution for CSES — Monsters — Suggestions for Improvement are highly appreciated

Автор samadeep, история, 14 месяцев назад, По-английски

I have used a map -> to store the time of lowest time when the Monsters can attack the square in the matrix

Parent[x][y] -> used to store where did the prev direction when a thing reached a particular square

X X X X X X X X 
X X X L X R R X 
X X X X X X D X 
X X X X X X D x
X X X X X X X X

like this which will be used later to reconstruct the path string

Suggestions for more Such questions and concepts would be great.

Code : CPP

``` ~~~~~ void solve() { int N , M ; cin >> N >> M ;

char g[N][M];

pair<int,int> start , reach;

vector<pair<int,int>> monsters ;

vector<vector<int>> map( N , vector<int>( M , 0 ) );


auto print_map = [&]( vector<vector<char>> &map )
{
    FOR( i , N )
    {
       FOR( j , M )
       {
         cout << map[i][j] << " ";

       }
    cout << endl;
    }
};



FOR( i , N )
{
    FOR( j , M )
    {
       cin >> g[i][j];

       if( g[i][j] == 'A' )
       {
         start = { i , j };
         map[i][j] = 1;
       }

       if( g[i][j] == 'M' )
       {
         monsters.push_back({i,j});
         map[i][j] = 1;
       }
       if( g[i][j] == '#' )
       {
         map[i][j] = -1;
       }
       if( g[i][j] == '.' )
       {
         map[i][j] = 2005 ;
       }
    }
}

// print_map();

auto valid = [&]( int x , int y )
{
    return x >= 0 && y >= 0 && x < N && y < M && map[x][y] != -1 ;
};



vector<pair<int,int>> moves = { { 1 , 0 } , { -1 , 0 } , { 0 , 1 } , { 0 , -1 } } ;



function<void(void)> monsters_bfs = [&]()
{
    vector<vector<bool>> vis( N , vector<bool>( M , false ) );

    queue<tuple<int,int,int>> q;

    for( auto [ i , j ] : monsters )
    {
       q.push( { i , j , 1 } );
       vis[i][j] = true ;
    }

    while( !q.empty() )
    {
       auto [x,y,time] = q.front(); q.pop();

       for( auto [ dx , dy ] : moves )
       {
         if( valid(x+dx,y+dy) && !vis[x+dx][y+dy] )
         {
          map[x+dx][y+dy] = time + 1 ;
          vis[x+dx][y+dy] = 1;

          q.push(make_tuple(x+dx,y+dy,time+1));
         }
       }
    }
};

monsters_bfs();

// print_map();


// Source BFS -> sx , sy 

function<char(int,int)> get = [&]( int dx , int dy )
{
    if( dx == -1 ) return 'U';
    if( dx == 1 ) return 'D';
    if( dy == 1 ) return 'R';
    if( dy == -1 ) return 'L';

};



bool done = false;

vector<vector<char>> parent( N , vector<char>( M , 'X' ) );

function<void(void)> src_bfs = [&]()
{
    vector<vector<bool>> vis( N , vector<bool>( M , false ) );





    queue<tuple<int,int,int>> q;

    q.push( { start.f , start.s , 1 } );

    vis[start.f][start.s] = true ;

    while(!q.empty())
    {
       auto [x,y,time] = q.front(); q.pop();

       if( x == N - 1 || y == M - 1 || x == 0 || y == 0 )
       {
         cout << "YES" << endl;
         reach.f = x , reach.s = y ;
         done = true ;
         return; 
       }

       for( auto [ dx , dy ] : moves )
       {
         if( valid( x+dx,y+dy) && map[x+dx][y+dy] > time + 1 && !vis[x+dx][y+dy] )
         {

          char go = get(dx,dy);

          // string path_new = path;

          vis[x+dx][y+dy] = true ;

          parent[x+dx][y+dy] = get(dx,dy);

          // path_new.push_back(go);

          q.push(make_tuple(x+dx,y+dy,time+1));


         }
       }
    }
};

src_bfs();

// print_map(parent);


string ans = "";

function<pair<int,int>(char , pair<int,int>)> go_to = [&]( char g , pair<int,int> to )
{
    if( g == 'D' )        return make_pair(to.f - 1 , to.s);
    else if( g == 'U' ) return make_pair(to.f + 1 , to.s) ;
    else if( g == 'L' ) return make_pair(to.f , to.s + 1 );
    else if( g == 'R' ) return make_pair(to.f , to.s - 1) ;

};


if( done )
{
    pair<int,int> r = reach;

    // cout << r.f << " " << r.s << endl;


    while( r != start )
    {
       // cout << parent[r.f][r.s] << endl;
       ans += parent[r.f][r.s];
       r = go_to(parent[r.f][r.s],r);
       // cout << r.f << " " << r.s << endl;
    }

    cout << ans.size() << endl;

    reverse(ALL(ans));

    cout << ans << endl;


}



if( not done ) cout << "NO" << endl;

} ~~~~~ ...

Полный текст и комментарии »

cses, multisource bfs

samadeep
14 месяцев назад
1

Maximum Tasks done in a Video Game :

Автор samadeep, история, 16 месяцев назад, По-английски

Could someone please suggest a method to solve this problem

Problem Description

You are playing a video game. Your character has two properties Power and Speed. Initially, your character has 1 power and 1 speed. Given N tasks in the game which need to be performed in any order. However, the ith task requires a minimum of A[i] power or B[i] speed. On completing the ith task you get C[i] points which you can use to increase power and speed. 1 point can be redeemed to increase 1 power or 1 speed. Find the maximum number of tasks that you can complete.

Problem Constraints
1<=N<=100 1<=A[i],B[i],C[1]<=1000 Input Format: The first argument is an integer array A. The second argument is an integer array B. The third argument is an integer array C. Return an integer that is the maximum number of tasks that you can complete.

Example Input Input 1:-
A=[1,1,2,7] B=[1,3,4,4] C=[2,3,1,1] Input 2:=
A=[1,2,4,9] B=[1,2,4,9] C=[2,1,2,3] Example Explanation Explanation 1:- Initially Power =1, speed =1 Perform task 1(1,1) required Points gained =2 New Power =1, speed =3 Perform task 2(1,3) Points gained =3 New Power =3, speed =4 Perform task 3(2,4) Points gained =1 New power =4, speed =4 Perform task (7,4) A11 tasks performed. values as specified

Полный текст и комментарии »

problem, sorting, dynamic programming, solve

samadeep
16 месяцев назад
2

Eulerian Subgraph Count : Explanation for Calculation

Автор samadeep, история, 17 месяцев назад, По-английски

CSES Problem : Advanced Techniques Section

Is there a explanation and proof anyone can suggest me.

Link :Eulerian Subgraph

You are given an undirected graph that has n nodes and m edges.

We consider subgraphs that have all nodes of the original graph and some of its edges. A subgraph is called Eulerian if each node has even degree.

Your task is to count the number of Eulerian subgraphs modulo 109+7 .

Input

The first input line has two integers n and m : the number of nodes and edges. The nodes are numbered 1,2,…,n .

After this, there are m lines that describe the edges. Each line has two integers a and b : there is an edge between nodes a and b . There is at most one edge between two nodes, and each edge connects two distinct nodes.

Полный текст и комментарии »

eulerian graph, combinatorics, dsu

samadeep
17 месяцев назад
1

Least Amount Required for Stone Removal

Автор samadeep, история, 17 месяцев назад, По-английски

Recently i came accross this question it would be great if anyone could solve this.

There are 'n' stones in a row from 0 to n-1. For every ith stone , there are 2 values associated with it, a[i] and b[i] . You have to remove all the stones from the row one by one. Removing the ith stone follows the rule :

If (i-1)th and (i+1)th stones are still present , then , cost of removing the ith stone is b[i].

if either (i-1)th or (i+1)th stone is present , then cost of removing the ith stone is a[i].

if neither (i-1)th nor (i+1)th stone is present , the cost of removing the ith stone is 0.

Find the minimum total cost of removing all the stones.

Constraints : 1 <= n <= 50000 1 <= a[i] , b[i] <= 1000

Полный текст и комментарии »

samadeep
17 месяцев назад
5