Hi community, I've come across this problem: https://www.geeksforgeeks.org/problems/find-shortest-safe-route-in-a-matrix/1

Below is my AC Java solution

Issue: This code must not be AC according to me.

I have memoized the results, dp[i][j] = length of shortest path from i,j to reach the last col but here we're reaching i,j through different paths and the cells which could be further visited starting from i,j depend upon the cells already visited in the current path, hence dp[i][j] should be different when we reach i,j through different paths, hence we cannot memoize its result

Please correct me if I'm wrong,

private static int[] DI = {-1,1,0,0};
private static int[] DJ = {0,0,-1,1};
private boolean isInMat(int i, int j, int n, int m) {
    return 0<=i && i<n && 0<=j && j<m;
}

int[][] dp;

int dfs(int i, int j, int[][] mat) {
    int n = mat.length;
    int m = mat[0].length;
    
    if(j == m-1) return 1;
    if(dp[i][j] != -1) return dp[i][j];
    
    mat[i][j] = 0;
    
    int ans = Integer.MAX_VALUE;
    for(int a=0; a<4; a++) {
        int ni = i+DI[a];
        int nj = j+DJ[a];
        if(!isInMat(ni, nj, n, m)) continue;
        if(mat[ni][nj] != 1) continue;
        ans = Math.min(ans, dfs(ni, nj, mat));
    }
    
    mat[i][j] = 1;
    return dp[i][j] =  (ans == Integer.MAX_VALUE ? ans : 1+ans);
}

public int findShortestPath(int[][] mat) {
    int n = mat.length;
    int m = mat[0].length;
    dp = new int[n][m];
    for(int i=0; i<n; i++) Arrays.fill(dp[i],-1);
    
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++) {
        if(mat[i][j] != 0) continue;
        for(int a=0; a<4; a++) {
            int ni = i+DI[a];
            int nj = j+DJ[a];
            if(isInMat(ni, nj, n, m) && mat[ni][nj] == 1)
            mat[ni][nj] = -1;
        }
    }
    
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
    if(mat[i][j] == -1) mat[i][j] = 0;
    
    int ans = Integer.MAX_VALUE;
    for(int i=0; i<n; i++) {
        if(mat[i][0] == 1)
        ans = Math.min(ans, dfs(i, 0, mat));
    }
    
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

Problem link: https://www.geeksforgeeks.org/problems/maximum-bipartite-matching--170646/1

Problem Statement: There are M job applicants and N jobs. Each applicant has a subset of jobs that he/she is interested in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Given a matrix G with M rows and N columns where G(i,j) denotes ith applicant is interested in the jth job. Find the maximum number of applicants who can get the job.

Input: M = 3, N = 5 G = {{1,1,0,1,1},{0,1,0,0,1}, {1,1,0,1,1}} Output: 3

Explanation:

There is one of the possible assignment- First applicant gets the 1st job. Second applicant gets the 2nd job. Third applicant gets the 4th job.

Constraints: 1 ≤ N, M ≤ 100

Help needed: I got to know about the solution which used maximum bipartite matching. However, I'm still unable to build an intuition about how that algo is working

I'll be grateful if someone can help me with some explanation/leads/articles ?

My Java Accepted code:

    private static final int NONE_SELECTED = -1;
    boolean rec(int p, int[][] interested, boolean[] explored, int[] selected) {
        int totalJobs =  interested[0].length;
        for(int j=0; j<totalJobs; j++) {
            if(interested[p][j] == 1 && !explored[j]) {
                explored[j] = true;
                if(selected[j] == NONE_SELECTED ||
                rec(selected[j], interested, explored, selected)) {
                    selected[j] = p;
                    return true;
                }
            }
        }
        
        return false;
    } 
    
    public int maximumMatch(int[][] g) {
        int totalJobs = g[0].length;
        int totalApplicants = g.length;
        int ans = 0;
        
        int[] selected = new int[totalJobs];
        Arrays.fill(selected, NONE_SELECTED);
        
        for(int p=0; p<totalApplicants; p++) {
            boolean[] explored = new boolean[totalJobs];
            Arrays.fill(explored, false); 
            if(rec(p, g, explored, selected) == true) ans++;
        }
        
        return ans;
    }

Problem Name: Planets

Problem link: https://mirror.codeforces.com/contest/229/problem/B

My approach and doubt: If we apply the modified Dijkstra like said in the editorial, and if the same vertex is visited many times in the min heap, then due to this then the same list of travelers may be traversed multiple times, which may result into a TLE. but the editorial says that the same list of travelers wont be traversed multiple times, Can somebody explain me why and where I am going wrong ?

Thanks in advance.

My Accepted Code:

#include <bits/stdc++.h>
using namespace std;
#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define lli long long int
#define ll long long
#define pll pair<long,long>

ll n,m;
ll N=1e5+100;
ll INF=1e18+1000;
vector<vector<pll>> adj(N,vector<pll>());
vector<vector<ll>> trv(N,vector<ll>());
vector<ll> dist(N,INF);

void dijkstra(ll src)
{
    priority_queue<pll,vector<pll>,greater<pll>> min_heap;
    dist[src]=0;
    min_heap.push({dist[src],src});
    while(!min_heap.empty())
    {
        ll curr_n=min_heap.top().second;
        ll curr_d=min_heap.top().first;
        min_heap.pop();
        
        ll nn=trv[curr_n].size();
        ll act_d=-1;
        
        if(nn==0) act_d=curr_d;
        else if(curr_d<trv[curr_n][0]) act_d=curr_d;
        else 
        {
            for(ll i=0;i<nn-1;i++)
            {
                if(trv[curr_n][i]+1<trv[curr_n][i+1] && curr_d<trv[curr_n][i+1])
                { act_d=max(trv[curr_n][i]+1,curr_d); break; }
            }
        }
        
        if(act_d==-1) act_d=max(trv[curr_n].back()+1,curr_d);
        
        for(auto opt:adj[curr_n])
        {
            ll next_n=opt.first;
            ll next_d=opt.second;
            
            if(act_d+next_d<dist[next_n])
            {
                dist[next_n]=act_d+next_d;
                min_heap.push({dist[next_n],next_n});
            }
        }
    }
    
    return;
}

void solve()
{
    cin>>n>>m;
    for(ll i=0;i<m;i++)
    {
        ll u,v,w; cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    
    for(ll i=1;i<=n;i++)
    {
        ll cnt; cin>>cnt;
        
        while(cnt--)
        { ll x; cin>>x; trv[i].push_back(x); }
    }
    
    dijkstra(1);
    
    cout<<(dist[n]==INF ? -1 : dist[n])<<'\n';
    
    return;
}

int main()
{
    fastio();
    int t=1;
    // cin>>t;
    while(t--) solve();

    return 0;
}

Problem name: Chef and Reversing

Problem link: https://www.codechef.com/problems/REVERSE

Problem statement: Sometimes mysteries happen. Chef found a directed graph with N vertices and M edges in his kitchen! The evening was boring and chef has nothing else to do, so to entertain himself, Chef thought about a question "What is the minimum number of edges he needs to reverse in order to have at least one path from vertex 1 to vertex N, where the vertices are numbered from 1 to N.

Doubt: Greetings everyone, I am trying to solve this problem, I got all the logic and i have coded the problem too, but I have come across a situation in the given code, this code gives a WA, but if I uncomment Line '1' and comment the Line '2', it gives a an AC, can anybody please help me understand the issue

My logic for this is to firstly mark all given edges u->v as true in the map, and then traverse the entire map then I add the every edge u->v with a weight of 0, but if v->u is not present in the map, then I add v->u with a weight of 1

My code:

#include <bits/stdc++.h>
using namespace std;
#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define lli long long int
#define ll long long
#define pii pair<int,int>

int INF=1e9+1000;
int N=1e5+100;
vector<vector<pii>> adj(N,vector<pii>());
vector<int> dist(N);
int n,m; 

void add_edge(int u,int v,int w)
{
    adj[u].push_back({v,w});
}

void dijsktra(int src)
{
    for(int i=1;i<=n;i++) dist[i]=INF;
    priority_queue<pii,vector<pii>,greater<pii>> min_heap;
    dist[src]=0;
    min_heap.push({dist[src],src});
    
    while(!min_heap.empty())
    {
        int curr_node=min_heap.top().second;
        int curr_dist=min_heap.top().first;
        min_heap.pop();
        for(auto opt:adj[curr_node])
        {
            int next_node=opt.first;
            int next_dist=opt.second;
            
            if(curr_dist+next_dist<dist[next_node])
            {
                dist[next_node]=curr_dist+next_dist;
                min_heap.push({dist[next_node],next_node});
            }
        }
    }
    
    return;
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) adj[i].clear();
    
    map<pii,bool> present;
    for(int i=0;i<m;i++)
    {
        int u,v; cin>>u>>v;
        if(u==v) continue;
        present[{u,v}]=true;
        //add_edge(u,v,0); // Line 1  ***********************************
    }
    
    for(auto x:present)
    {
        pii p=x.first;
        add_edge(p.first,p.second,0); // Line 2  ************************
        if(!present[{p.second,p.first}]) add_edge(p.second,p.first,1);
    }
    
    dijsktra(1);
    
    cout<<(dist[n]>=INF ? -1 : dist[n])<<'\n';
    
    return;
}

int main()
{
    fastio();
    int t=1;
    // cin>>t;
    while(t--) solve();

    return 0;
}

Hello everyone. Recently, I came across this problem on Codechef: https://www.codechef.com/LP3TO401/problems/SUBREM

I came across this kind of problem for the first time. It will be really helpful if could get to know the type of this problem. I guess this is a problem in DP on trees. It would be really helpful if I get to know the name of this topic and some beginner to medium level practice problems on this topic.

Problem Statement:

You are given a rooted tree with N nodes (numbered 1 through N); node 1 is the root. Each node has a value; let's denote the value of node i by Ai.

You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.

Let's define the profit as the sum of values of all nodes which currently exist in the tree minus X⋅k, where k denotes the number of times this operation was performed. Find the maximum possible profit.

----------------------------------------------------------------------------------------------------------------------------- Thanking you all in advance.

I am trying to learn about custom comparators in priority queue. however, i am unable to get the expected behaviour. I have wrote two custom comparators in the below code one for a vector and the other for a priority queue and the logic is same for both the comparators. how the output seems to be opposite, can anyone tell me the reason for this, any help will be appreciated.

In my thinking the output given by the priority queue should be same as the vector but it isn't.

Actual Ouput:

Vector: 1 6 2 5 2 4

Priority Queue: 2 4 2 5 1 6

Expected Output:

Vector: 1 6 2 5 2 4

Priority Queue: 1 6 2 5 2 4

struct cmp1 {
    bool operator()(pii const& a,pii const& b)
    {
        if(a.first==b.first) return a.second>b.second;
        return a.first<b.first;
    }
};

bool cmp2(pii const& a,pii const& b)
{
    if(a.first==b.first) return a.second>b.second;
    return a.first<b.first;
}

int main()
{
    priority_queue<pii,vector<pii>,cmp1> cust_heap;
    cust_heap.push({1,6});
    cust_heap.push({2,4});
    cust_heap.push({2,5});
    
    vector<pii> v;
    v.push_back({1,6});
    v.push_back({2,4});
    v.push_back({2,5});
    
    sort(v.begin(),v.end(),cmp2);
    
    cout<<"Vector: "<<'\n';
    
    for(auto x:v) cout<<x.first<<" "<<x.second<<'\n';
    
    cout<<'\n';
    
    cout<<"Priority Queue: "<<'\n';
    
    while(!cust_heap.empty())
    {
        int freq=cust_heap.top().first;
        int element=cust_heap.top().second;
        cust_heap.pop();
        cout<<freq<<" "<<element<<'\n';
    }
    
    cout<<'\n';
    
    return 0;
}

Hi everyone. I tried to approach a question from Infosys contest HackWithInfy but was not able to figure out any solution for it. Please share possible approaches or solutions for these. Any help will be appreciated.

Question: Altaf has recently learned about number bases and is becoming fascinated.

Altaf learned that for bases greater than ten, new digit symbols need to be introduced, and that the convention is to use the first few letters of the English alphabet. For example, in base 16, the digits are 0123456789ABCDEF. Altaf thought that this is unsustainable; the English alphabet only has 26 letters, so this scheme can only work up to base 36. But this is no problem for Altaf, because Altaf is very creative and can just invent new digit symbols when she needs them. (Altaf is very creative.)

Altaf also noticed that in base two, all positive integers start with the digit 1! However, this is the only base where this is true. So naturally, Altaf wonders: Given some integer N, how many bases b are there such that the base-b representation of N starts with a 1?

INPUT FORMAT :

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

Each test case consists of one line containing a single integer N (in base ten).

OUTPUT FORMAT :

For each test case, output a single line containing the number of bases b, or INFINITY if there are an infinite number of them.

CONSTRAINTS :

1 <= T <= 10^5 0 <= N < 10^12

SAMPLE INPUT :

4

6

9

11

24

SAMPLE OUTPUT :

4

7

8

14