Blog entries - Codeforces

#	User	Rating
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

#	User	Contrib.
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's blog

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

By samadeep, history, 7 weeks ago, In English

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

Full text and comments »

combinations, dynamic programming, interview

samadeep
7 weeks ago
4

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

By samadeep, history, 13 months ago, In English

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)

Full text and comments »

permutations, strings, combinations

samadeep
13 months ago
5

An Interesting Dyanmic Programming + Binary Search Problem

By samadeep, history, 13 months ago, In English

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.

Full text and comments »

dp, binary search, problem

samadeep
13 months ago
17

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

By samadeep, history, 14 months ago, In English

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;

} ~~~~~ ...

Full text and comments »

cses, multisource bfs

samadeep
14 months ago
1

Maximum Tasks done in a Video Game :

By samadeep, history, 16 months ago, In English

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

Full text and comments »

problem, sorting, dynamic programming, solve

samadeep
16 months ago
2

Eulerian Subgraph Count : Explanation for Calculation

By samadeep, history, 17 months ago, In English

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.

Full text and comments »

eulerian graph, combinatorics, dsu

samadeep
17 months ago
1

Least Amount Required for Stone Removal

By samadeep, history, 17 months ago, In English

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

Full text and comments »

samadeep
17 months ago
5