I came across the following problem :

There is an array of size n and you are currently located at the starting point of the array, you want to go to the ending point of the array by only using steps of +3 and -1.

like if you are at x you can either go to x+3 or x-1.

The total cost of this work will be equal to the sum of the values at the indices you go through to reach the end of the array. Find the minimum cost incurred.

ex.
[4 2 1 5 6]
here the best way is 4 -> 1 -> 2 -> 6
cost = 13.

size of array <= 1e3
1 <= a[i] <= 1e3

Approach :

There is a DP solution for this problem, but I was wondering can it be solved by dijkshtra algorithm where we assume that index x is connect to index x+3 and x-1, taking source as 0th index and target as (n-1)th index. The magnitude of edges being the value of the node it is leading to.

Given a directed graph, suppose we want to find the number of reachable nodes from each node of the graph then what is the best way to solve this problem ??

One obvious way to solve it is doing dfs from every node of the graph and counting how many nodes are getting visited, but the problem with this approach is that it is O(n^2) where n is the number of nodes in the graph

Then i thought of maybe if we can store at each node how many nodes are reachable and when queried give the answer based on the values of the neighbouring nodes but this will not be able to handle the case of overcounting as in the graph below.

So how to solve this ?

This recent problem Bank Cooperation, from a codechef contest is solved using bit manipulation in editorial but i think it is solvable by this graph approach too.

All 8 items can be thought as nodes in graph, where the paired up elements will form one component, now in components we cannot take neighbouring nodes, as they can`t be put together.So I found the maximum value that we can take from a component by doing modified dfs, and then added the maximum values of all the components.

I have thought of many cases but cant figure out why its wrong, please help…

My Code

 #include<bits/stdc++.h>
 using namespace std;

 vector<vector<int>>gr(8);
 bool vs[8];
 int A[8];

 void dfs(int v,vector<int>& tmp){
	if(vs[v]){
	   return;
	}
	vs[v] = true;
	tmp.pb(v);
	for(auto i:gr[v]){
	    dfs(i,tmp);
	}
	return;
 }

 void spdfs(int v, int f, int& s){
	if(vs[v]){
		return;
	}
	vs[v] = true;
	if(f){
	        s += A[v];
	}
	for(auto i:gr[v]){
		spdfs(i,1-f,s);
	}
	return;
 }
 
int main(){

	// int t = 1;
	int t;
	cin>>t;

	while(t--){
		
		for(int i=0;i<8;i++){
			cin>>A[i];
			gr[i].clear();		
		}
		int p;
		cin>>p;
		for(int i=0;i<p;i++){
			int a,b;
			cin>>a>>b;
			if(a == b){
				continue;
			}
			a--;
			b--;
			gr[a].pb(b);
			gr[b].pb(a);
		}
		memset(vs, false , sizeof vs);
		vector<vector<int>>cmp;
		for(int i=0;i<8;i++){
			if(vs[i]){
				continue;
			}else{
				vector<int>tmp;
				dfs(i,tmp);
				cmp.pb(tmp);
			}
		}
			
		ll ttl = 0;
		for(int i=0;i<cmp.size();i++){
			int toadd = INT_MIN;
			for(int j=0;j<cmp[i].size();j++){
				memset(vs, false,sizeof vs);
				int tmp = 0;
				spdfs(cmp[i][j], 1, tmp);
				toadd = max(toadd,tmp);	
			}
			ttl += toadd;
		}

		cout<<ttl<<endl;

	  }

		return 0;
	}
	

I recently came across the following question.

Given a matrix representing which child likes which toy. matrix[i][j]=1 represents that child i likes toy j. One child can get only 1 toy and one toy can be assigned to only 1 child.Find maximum number of children who can get the toy they wished.

One approach i can think of is going through all possible ways of distributing the toys but it wont work if the constraints are high, what can be a better approach.

Recently I gave Amazon coding test, in which i got the following question

Given n, find all numbers from 1 to n, which are coprime with n.
ex.
Input: n = 5
Output: 4
Explanation — The numbers coprime with n = 5 are (1,5), (2,5), (3,5), (4,5)

Input: n = 10
Output: 4
Explanation — (1,10), (3,10), (7,10), (9,10)

Constraints 1 <= n <= 10^9.

I wrote a brute force solution, where i took each numebr from 1 to n and tried to find its gcd with n. Which apparently gave a TLE on most of the test cases.

Can anyone kindly guide me how to solve this problem ?