A non-dp solution:-

#include<bits/stdc++.h>using namespace std;int main(){int N,i,u,v,j,count,max_count;bool chosen[5005];string A;cin>>N;cin>>A;max_count=0;for(i=0;i<N;i++){u=i-1;

Active In

Competitive Programming

International Olympiad in Informatics

Indian Computing Olympiad (ICO)

CP noobs

Bitcoin and Blockchain

Algorithms and Data Structures

Web Development

Featured Contributions

reply in this discussion

HR

Himanshu RanjanJust started solving problems! ·

A non-dp solution:-

#include<bits/stdc++.h>using namespace std;int main(){int N,i,u,v,j,count,max_count;bool chosen[5005];string A;cin>>N;cin>>A;max_count=0;for(i=0;i<N;i++){u=i-1;

Read more… (50 words)

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 1w

For a more mathematically oriented solution for checking if a cell is valid or not, try to solve the in-equation:-

**| i - i' | + | j - j' | ≤ k**

We can't solve it until the mod sign is removed and it can only be removed if we are able to decide the sign of (i - i') and (j - j').

There are four cases:-

**i ≥ i' & j ≥ j'**(The cells below and to the right of the special cell) :

The in-equation reduces to :- **i - i' + j - j' ≤ k**

2. **i ≤ i' & j ≤ j'** (The cells above and to the left of the special cell) :

The in-equation reduces to :- **- ( i - i' ) - (j - j') ≤ k**

3.** i ≤ i' & j ≥ j'** (The cells above and to the ...

Read more… (239 words)

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 1w

Can you or some other moderator prepare a few test cases and upload it somewhere?

Read more… (15 words)

reply in this discussion

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 4w

Thanks for advice. I am in class 11 now.

Read more… (9 words)

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 4w

It basically checks for a cycle. Here, p represents parent.

DFS categorizes all edges into tree edges and back edges. So, whenever we get a vertex which has already been discovered and is not the parent of the current vertex, we have found a back edge which means we have found a cycle.

Read more… (53 words)

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 4w

The only reason I could think of why this problem is here is that the technique used in solving this problem is similar to BFS.

Read more… (25 words)

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 6w

Another way to use min_heap would be to multiply all your entries by -1 before inserting it into the priority queue.

Read more… (21 words)

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 6w

Talking about the complexity ... is it log N * log N or log N * log S where S is the search space and may lie between 1 and 10^9 - 1. Tell me if I am wrong somewhere ?

Read more… (41 words)

reply in this discussion

HR

Himanshu RanjanJust started solving problems! · 7w

The cutoff is justified as the questions were a bit tougher.

Read more… (11 words)