Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### ss_96's blog

By ss_96, history, 2 years ago, ,

I read a heap solution at the following link:link but cannot figure out that solution,can anyone please provide some pseudo-code or some explanation for the solution using heaps.

• 0

By ss_96, history, 2 years ago, ,

Given a corrupted string i.e it’s original string with just the spaces at wrong places, Construct the original string .We are given a dictionary of words.

Ex:-

input string : Com put erengineering

original string(output): Computer Engineering

I am trying to solve this with recursion and read these dictionary involving questions in many interview experiences but couldn't figure out the recursive equation,can anyone please provide some pseudo-code or some reference link for this problem?

• 0

By ss_96, history, 2 years ago, ,

Assuming your budget is N, you need to buy a rectangular land. Give a matrix of land prices and ask what is the largest area available for buying land. Land prices must be non-negative. (Source:https://www.careercup.com/question?id=5519438609645568)

The solution provided uses a O(n^4) solution,but can this problem be solved with BFS?If we apply BFS from every point in the matrix,can we get the correct answer?

Please provide some suggestions on how to solve this question more efficiently? Thank you for your time.

• 0

By ss_96, history, 2 years ago, ,

There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/decreased by M and that too Q number of times.

In case of multiple answers print the first one.

eg:

array:1,2,3,4 and Q=1,M=1

Answer:3 ,as the array can be transformed into 2,2,2,4 (here 2 appears 3 times in this array, adding 1 in 1 and subtracting 1 from 3.)

A hashtable can be used here,but can't understand how to handle the addition and subtraction of each number of the array.

Can anyone please suggest an approach for that part?

Thanks.

• +16

By ss_96, history, 2 years ago, ,

The problem statement:

There is an array given of 1s and -1s and there is a distance K,the output required is the maximum no of pairs such that their sum is 0 and both the numbers are within K distance.

eg: for array:

1 -1 1 -1 and K = 1 answer:2

This can be done with brute force,but i think there would a more efficient algorithm than just brute force.Can anyone please suggest something better,a pseudo code or is there any known algorithm for this?

Edit:A number can be taken only once.

Thanks.

• 0

By ss_96, history, 2 years ago, ,

I was trying to solve the following problem:

You are given a grid of size N×N that has the following specifications:

Each cell in the grid contains either a policeman or a thief.

A policeman can only catch a thief if both of them are in the same row.

Each policeman can only catch one thief.

A policeman cannot catch a thief who is more than K units away from the policeman.

Write a program to find the maximum number of thieves that can be caught in the grid.

My solution:solution

PS:This was a question of question and I have completed the test,couldn't qualify ,that's why asking for guidance here.Please suggest what corner cases are missing with the solution code.

Thanks.

• 0

By ss_96, history, 2 years ago, ,

I was trying to solve this question:link

My solution:solution

The solution is not able to pass all test cases.Please help and suggest what is wrong in the implementation.I have used kruskal algorithm in the 'min_' function of the code.

Thanks.

• 0

By ss_96, history, 2 years ago, ,

I was trying to solve a simple DFS question and my code was not passing 2 test cases.

Question:link The solution is also given in the first comment of the problem. Can anyone please explain why the check variable is used in that code.

Thanks.

• +2

By ss_96, history, 2 years ago, ,

I was trying to solve this question:question link

My solution:solution

The problem is that it does not pass all the test cases.

Please suggest what case am I missing to handle in my code.

Thanks!

• -1

By ss_96, history, 2 years ago, ,

I recently gave an online challenge in which the following question was asked,I was able to pass only 1 test case,just wanted to have some guidance on what would be the right approach for it.

Question: There is grid given of NxM. Each cell value represents a value P,which denotes the number of parking spaces available in that city. A person wants to take his vehicle from city C(1,1) to city C(N,M) such that he parks his vehicle at one of the available parking spaces in any city and then he takes a taxi via which he reaches city C(N,M).He can park his vehicle in any city. We have to output the number of ways in which he can reach his destination.

the first line contains N,M.

In each of N lines,M numbers follow.

sample input:

2 2

1 2

0 1

sample output: 3

I tried to use BFS but that gave wrong answers in every case except 1.Please suggest what should be the approach for this question? Thanks.

• -8

By ss_96, history, 2 years ago, ,

I was trying to solve the following question:

You are playing a game in which you have a rectangular grid of nn cells. Each cell is either empty or has a firework. Empty cells are marked with ".", cells with firework are marked with "" . Two cells are said to be adjacent if they share a side.

If firework in any cell explodes it destroys itself and the empty cells connected to it. Two cells are connected if there is a path of empty adjacent cells between them. You have to find the number of cells that will be destroyed if the fireworks are triggered independently. Input Constraints: 1≤n≤1000 Sample Input 4

* . . *

. . * .

* . . *

* . . *

Sample Output 66(9(for 1st *)+10+10+9+10+9+9(for 7th *)).

I simply applied a BFS and added individual sum.The problem is that it only passed some test cases,wrong answer and time limit exceeded in some.Can some please suggest what test case am I missing in handling? My code: https://gist.github.com/Sharma96/16071e66b0a36828c3566196289f0c92