Blog entries - Codeforces

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	146
8	orz	146
10	pajenegod	145

samadeep's blog

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

By samadeep, history, 6 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
6 months ago
5

An Interesting Dyanmic Programming + Binary Search Problem

By samadeep, history, 6 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
6 months ago
17

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

By samadeep, history, 8 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
8 months ago
1

Maximum Tasks done in a Video Game :

By samadeep, history, 9 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
9 months ago
2

Eulerian Subgraph Count : Explanation for Calculation

By samadeep, history, 11 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
11 months ago
1

Least Amount Required for Stone Removal

By samadeep, history, 11 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
11 months ago
5