samadeep's blog

By samadeep, history, 4 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 »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By samadeep, history, 12 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++
python

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By samadeep, history, 12 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 »

  • Vote: I like it
  • +2
  • Vote: I do not like it

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

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By samadeep, history, 15 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 »

  • Vote: I like it
  • 0
  • Vote: I do not like it

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 »

  • Vote: I like it
  • 0
  • Vote: I do not like it

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 »

Tags dp
  • Vote: I like it
  • +8
  • Vote: I do not like it