def min_cost_to_make_strongly_connected(N, tracks):
from collections import defaultdict, deque
import heapq
def kosaraju_scc(N, adj_list, rev_adj_list):
def dfs(node, adj_list, visited, stack):
visited[node] = True
for neighbor, _ in adj_list[node]:
if not visited[neighbor]:
dfs(neighbor, adj_list, visited, stack)
stack.append(node)
def reverse_dfs(node, rev_adj_list, visited, scc):
visited[node] = True
scc.append(node)
for neighbor in rev_adj_list[node]:
if not visited[neighbor]:
reverse_dfs(neighbor, rev_adj_list, visited, scc)
stack = []
visited = [False] * (N + 1)
for i in range(1, N + 1):
if not visited[i]:
dfs(i, adj_list, visited, stack)
visited = [False] * (N + 1)
sccs = []
while stack:
node = stack.pop()
if not visited[node]:
scc = []
reverse_dfs(node, rev_adj_list, visited, scc)
sccs.append(scc)
return sccs
adj_list = defaultdict(list)
rev_adj_list = defaultdict(list)
for A, B, C in tracks:
adj_list[A].append((B, C))
rev_adj_list[B].append(A)
sccs = kosaraju_scc(N, adj_list, rev_adj_list)
node_to_scc = {}
for i, scc in enumerate(sccs):
for node in scc:
node_to_scc[node] = i
component_graph = defaultdict(list)
component_cost = {}
for A, B, C in tracks:
compA = node_to_scc[A]
compB = node_to_scc[B]
if compA != compB:
if (compA, compB) not in component_cost or component_cost[(compA, compB)] > C:
component_cost[(compA, compB)] = C
pq = []
for (u, v), cost in component_cost.items():
heapq.heappush(pq, (cost, u, v))
parent = list(range(len(sccs)))
rank = [0] * len(sccs)
def find(u):
if parent[u] != u:
parent[u] = find(parent[u])
return parent[u]
def union(u, v):
root_u = find(u)
root_v = find(v)
if root_u != root_v:
if rank[root_u] > rank[root_v]:
parent[root_v] = root_u
elif rank[root_u] < rank[root_v]:
parent[root_u] = root_v
else:
parent[root_v] = root_u
rank[root_u] += 1
min_cost = 0
edges_used = 0
while pq and edges_used < len(sccs) - 1:
cost, u, v = heapq.heappop(pq)
if find(u) != find(v):
union(u, v)
min_cost += cost
edges_used += 1
return min_cost//2
Phonepe โ
from collections import defaultdict, deque
import heapq
def kosaraju_scc(N, adj_list, rev_adj_list):
def dfs(node, adj_list, visited, stack):
visited[node] = True
for neighbor, _ in adj_list[node]:
if not visited[neighbor]:
dfs(neighbor, adj_list, visited, stack)
stack.append(node)
def reverse_dfs(node, rev_adj_list, visited, scc):
visited[node] = True
scc.append(node)
for neighbor in rev_adj_list[node]:
if not visited[neighbor]:
reverse_dfs(neighbor, rev_adj_list, visited, scc)
stack = []
visited = [False] * (N + 1)
for i in range(1, N + 1):
if not visited[i]:
dfs(i, adj_list, visited, stack)
visited = [False] * (N + 1)
sccs = []
while stack:
node = stack.pop()
if not visited[node]:
scc = []
reverse_dfs(node, rev_adj_list, visited, scc)
sccs.append(scc)
return sccs
adj_list = defaultdict(list)
rev_adj_list = defaultdict(list)
for A, B, C in tracks:
adj_list[A].append((B, C))
rev_adj_list[B].append(A)
sccs = kosaraju_scc(N, adj_list, rev_adj_list)
node_to_scc = {}
for i, scc in enumerate(sccs):
for node in scc:
node_to_scc[node] = i
component_graph = defaultdict(list)
component_cost = {}
for A, B, C in tracks:
compA = node_to_scc[A]
compB = node_to_scc[B]
if compA != compB:
if (compA, compB) not in component_cost or component_cost[(compA, compB)] > C:
component_cost[(compA, compB)] = C
pq = []
for (u, v), cost in component_cost.items():
heapq.heappush(pq, (cost, u, v))
parent = list(range(len(sccs)))
rank = [0] * len(sccs)
def find(u):
if parent[u] != u:
parent[u] = find(parent[u])
return parent[u]
def union(u, v):
root_u = find(u)
root_v = find(v)
if root_u != root_v:
if rank[root_u] > rank[root_v]:
parent[root_v] = root_u
elif rank[root_u] < rank[root_v]:
parent[root_u] = root_v
else:
parent[root_v] = root_u
rank[root_u] += 1
min_cost = 0
edges_used = 0
while pq and edges_used < len(sccs) - 1:
cost, u, v = heapq.heappop(pq)
if find(u) != find(v):
union(u, v)
min_cost += cost
edges_used += 1
return min_cost//2
Phonepe โ
def reverse_substrings(word):
possible_strings = set()
for i in range(1, len(word) + 1):
reversed_prefix = word[:i][::-1] + word[i:]
possible_strings.add(reversed_prefix)
for i in range(1, len(word) + 1):
reversed_suffix = word[:-i] + word[-i:][::-1]
possible_strings.add(reversed_suffix)
return min(possible_strings)
possible_strings = set()
for i in range(1, len(word) + 1):
reversed_prefix = word[:i][::-1] + word[i:]
possible_strings.add(reversed_prefix)
for i in range(1, len(word) + 1):
reversed_suffix = word[:-i] + word[-i:][::-1]
possible_strings.add(reversed_suffix)
return min(possible_strings)
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll help(ll n,vector<vector<ll>>&v,vector<ll>&dp,ll i)
{
if(i>=n) return 0;
if(dp[i]!=-1) return dp[i];
ll t=help(n,v,dp,i+1);
ll l=i+1;
ll r=n-1;
ll res=n;
while(l<=r)
{
ll mid=(l+r)/2;
if(v[mid][0]>=v[i][1])
{
res=mid;
r=mid-1;
}
else l=mid+1;
}
ll next=res;
ll sum=v[i][2]+v[i][1]-v[i][0];
t=max(t,sum+help(n,v,dp,next));
return dp[i]=t;
}
ll solve(vector<ll>&pick,vector<ll>&drop,vector<ll>&tip)
{
ll n=pick.size();
vector<vector<ll>>rides(n);
for(ll i=0;i<n;i++)
{
rides[i]={pick[i],drop[i],tip[i]};
}
sort(rides.begin(),rides.end());
vector<ll>dp(n+10,-1);
return help(n,rides,dp,0);
}
signed main()
{
ll n; cin>>n;
vector<ll>pick(n),drop(n),tip(n);
for(ll i=0;i<n;i++) cin>>pick[i];
for(ll i=0;i<n;i++) cin>>drop[i];
for(ll i=0;i<n;i++) cin>>tip[i];
cout<<solve(pick,drop,tip);
return 0;
}
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
public static int[] teamSize(int[] talent, int talentsCount) {
int n = talent.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Map<Integer, Integer> talentFreq = new HashMap<>();
int left = 0, uniqueTalents = 0;
for (int right = 0; right < n; right++) {
talentFreq.put(talent[right], talentFreq.getOrDefault(talent[right], 0) + 1);
if (talentFreq.get(talent[right]) == 1) {
uniqueTalents++;
}
while (uniqueTalents == talentsCount) {
result[left] = (result[left] == -1) ? right - left + 1 : Math.min(result[left], right - left + 1);
talentFreq.put(talent[left], talentFreq.get(talent[left]) - 1);
if (talentFreq.get(talent[left]) == 0) {
uniqueTalents--;
}
left++;
}
}
return result;
}
int n = talent.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Map<Integer, Integer> talentFreq = new HashMap<>();
int left = 0, uniqueTalents = 0;
for (int right = 0; right < n; right++) {
talentFreq.put(talent[right], talentFreq.getOrDefault(talent[right], 0) + 1);
if (talentFreq.get(talent[right]) == 1) {
uniqueTalents++;
}
while (uniqueTalents == talentsCount) {
result[left] = (result[left] == -1) ? right - left + 1 : Math.min(result[left], right - left + 1);
talentFreq.put(talent[left], talentFreq.get(talent[left]) - 1);
if (talentFreq.get(talent[left]) == 0) {
uniqueTalents--;
}
left++;
}
}
return result;
}
int solve(int n, int m, int k, vector<vector<int>>& profit) {
vector<vector<int>> dp(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
dp[i][0] = profit[i][0];
}
for (int j = 1; j < m; j++) {
vector<int> temp(n, 0);
for (int i = 0; i < n; i++) {
for (int x = max(0, i - k); x <= min(n - 1, i + k); x++) {
if (x != i) {
temp[i] = max(temp[i], dp[x][j-1]);
}
}
}
for (int i = 0; i < n; i++) {
dp[i][j] = temp[i] + profit[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, dp[i][m-1]);
}
return ans;
}
//max-profit
vector<vector<int>> dp(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
dp[i][0] = profit[i][0];
}
for (int j = 1; j < m; j++) {
vector<int> temp(n, 0);
for (int i = 0; i < n; i++) {
for (int x = max(0, i - k); x <= min(n - 1, i + k); x++) {
if (x != i) {
temp[i] = max(temp[i], dp[x][j-1]);
}
}
}
for (int i = 0; i < n; i++) {
dp[i][j] = temp[i] + profit[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, dp[i][m-1]);
}
return ans;
}
//max-profit
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll solve(vector<vector<ll>>&a)
{
ll n=a.size();
if(a.empty()) return 0;
ll sz=0,pre;
vector<ll>cur(n);
for(ll i=0;i<n;i++)
{
for(ll j=0;j<n;j++)
{
ll temp=cur[j];
if (!i || !j || a[i][j]==0)
{
cur[j]=a[i][j];
}
else
{
cur[j]=min(pre,min(cur[j],cur[j-1]))+1;
}
sz=max(cur[j],sz);
pre=temp;
}
}
return sz;
}
signed main()
{
ll n; cin>>n;
vector<vector<ll>>a(n,vector<ll>(n));
for(ll i=0;i<n;i++)
for(ll j=0;j<n;j++) cin>>a[i][j];
cout<<solve(a);
return 0;
}
Movelsync cab compliance โ
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
int32_t main() {
string src;cin>>src;
string tar;cin>>tar;
int k;cin>>k;
int gw=0,bw=0;
for(int i=0;i<src.size();i++){
string temp = src.substr(i) + src.substr(0,i);
if(temp == tar) gw++;
else bw++;
}
int dp[k+1][2];
dp[0][0] = (src==tar);
dp[0][1] = !(src==tar);
for(int i=1;i<=k;i++){
dp[i][0] = ((dp[i-1][0]*(gw-1))%MOD + (dp[i-1][1]*gw)%MOD)%MOD;
dp[i][1] = ((dp[i-1][1]*(bw-1))%MOD + (dp[i-1][0]*bw)%MOD)%MOD;
}
cout<<dp[k][0];
return 0;
}
//NLP enthusiasts โ
using namespace std;
#define int long long
const int MOD=1e9+7;
int32_t main() {
string src;cin>>src;
string tar;cin>>tar;
int k;cin>>k;
int gw=0,bw=0;
for(int i=0;i<src.size();i++){
string temp = src.substr(i) + src.substr(0,i);
if(temp == tar) gw++;
else bw++;
}
int dp[k+1][2];
dp[0][0] = (src==tar);
dp[0][1] = !(src==tar);
for(int i=1;i<=k;i++){
dp[i][0] = ((dp[i-1][0]*(gw-1))%MOD + (dp[i-1][1]*gw)%MOD)%MOD;
dp[i][1] = ((dp[i-1][1]*(bw-1))%MOD + (dp[i-1][0]*bw)%MOD)%MOD;
}
cout<<dp[k][0];
return 0;
}
//NLP enthusiasts โ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
#include <bits/stdc++.h> #define ll long long using namespace std; ll solve(vector<vector<ll>>&a) { ll n=a.size(); if(a.empty()) return 0; ll sz=0,pre; vector<ll>cur(n); for(ll i=0;i<n;i++) { for(ll j=0;j<n;j++) โฆ
โ
def doesCircleExist(commands):
def simulate(command):
x, y = 0, 0
dx, dy = 0, 1
for _ in range(4):
for c in command:
if c == 'G':
x += dx
y += dy
elif c == 'L':
dx, dy = -dy, dx
elif c == 'R':
dx, dy = dy, -dx
if x == 0 and y == 0:
return True
if dx == 0 and dy == 1:
return False
return False
results = []
for command in commands:
results.append("YES" if simulate(command) else "NO")
return results
Movie sync Circular route identification โ
๐1
from collections import defaultdict
def maxShared(employees_nodes, employees_from, employees_to, employees_weight):
graph = defaultdict(lambda: defaultdict(int))
for i in range(len(employees_from)):
u, v, w = employees_from[i], employees_to[i], employees_weight[i]
graph[u][v] += 1
graph[v][u] += 1
max_product = 0
for i in range(1, employees_nodes + 1):
for j in graph[i]:
if graph[i][j] > 1:
max_product = max(max_product, i * j)
return max_product
Movelsync Employee shared Interest โ
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxi = 0;
int numWays = 0;
void backtrack(vector<int>& P, vector<vector<int>>& adj, vector<bool>& vis, int curr, int N) {
bool all = true;
for (int i = 0; i < N; ++i) {
if (!vis[i]) {
all = false;
vis[i] = true;
vector<int> prev;
for (int nei : adj[i]) {
if (!vis[nei]) {
vis[nei] = true;
prev.push_back(nei);
}
}
backtrack(P, adj, vis, curr + P[i], N);
for (int nei : prev) {
vis[nei] = false;
}
vis[i] = false;
}
}
if (all) {
if (curr > maxi) {
maxi = curr;
numWays = 1;
} else if (curr == maxi) {
numWays++;
}
}
}
int main() {
int N, M;
cin >> N >> M;
vector<int> P(N);
for (int i = 0; i < N; ++i) {
cin >> P[i];
}
vector<vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
int x, y;
cin >> x >> y;
x--; y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<bool> vis(N, false);
backtrack(P, adj, vis, 0, N);
cout << maxi << " " << numWays << endl;
return 0;
}
//phone pe
Cookie salesโ
Source : Hola
#include <vector>
#include <algorithm>
using namespace std;
int maxi = 0;
int numWays = 0;
void backtrack(vector<int>& P, vector<vector<int>>& adj, vector<bool>& vis, int curr, int N) {
bool all = true;
for (int i = 0; i < N; ++i) {
if (!vis[i]) {
all = false;
vis[i] = true;
vector<int> prev;
for (int nei : adj[i]) {
if (!vis[nei]) {
vis[nei] = true;
prev.push_back(nei);
}
}
backtrack(P, adj, vis, curr + P[i], N);
for (int nei : prev) {
vis[nei] = false;
}
vis[i] = false;
}
}
if (all) {
if (curr > maxi) {
maxi = curr;
numWays = 1;
} else if (curr == maxi) {
numWays++;
}
}
}
int main() {
int N, M;
cin >> N >> M;
vector<int> P(N);
for (int i = 0; i < N; ++i) {
cin >> P[i];
}
vector<vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
int x, y;
cin >> x >> y;
x--; y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<bool> vis(N, false);
backtrack(P, adj, vis, 0, N);
cout << maxi << " " << numWays << endl;
return 0;
}
//phone pe
Cookie salesโ
Source : Hola
โค2
๐๐ฆ ๐๐น๐ด๐ผ ๐ป ๐ ใ๐๐ผ๐บ๐ฝ๐ฒ๐๐ถ๐๐ถ๐๐ฒ ๐ฃ๐ฟ๐ผ๐ด๐ฟ๐ฎ๐บ๐บ๐ถ๐ป๐ดใ
Photo
#include <iostream>
#include <vector>
using namespace std;
long long calc(int base, int times) {
return base * (1LL << (times - 1));
}
int main() {
int n, k;
cin >> n >> k;
vector<int> discounts(n);
for (int i = 0; i < n; ++i) {
cin >> discounts[i];
}
vector<int> times(n, 1);
for (int i = 0; i < k; ++i) {
long long max_increase = -1;
int max_index = -1;
for (int j = 0; j < n; ++j) {
long long curr = calc(discounts[j], times[j]);
long long next = calc(discounts[j], times[j] + 1);
if (next - curr > max_increase) {
max_increase = next - curr;
max_index = j;
}
}
times[max_index]++;
}
long long max_discount = 0;
for (int i = 0; i < n; ++i) {
max_discount |= calc(discounts[i], times[i]);
}
cout << max_discount << endl;
return 0;
}
First trip of Luna โ
Phonepe
Source :Hola
#include <vector>
using namespace std;
long long calc(int base, int times) {
return base * (1LL << (times - 1));
}
int main() {
int n, k;
cin >> n >> k;
vector<int> discounts(n);
for (int i = 0; i < n; ++i) {
cin >> discounts[i];
}
vector<int> times(n, 1);
for (int i = 0; i < k; ++i) {
long long max_increase = -1;
int max_index = -1;
for (int j = 0; j < n; ++j) {
long long curr = calc(discounts[j], times[j]);
long long next = calc(discounts[j], times[j] + 1);
if (next - curr > max_increase) {
max_increase = next - curr;
max_index = j;
}
}
times[max_index]++;
}
long long max_discount = 0;
for (int i = 0; i < n; ++i) {
max_discount |= calc(discounts[i], times[i]);
}
cout << max_discount << endl;
return 0;
}
First trip of Luna โ
Phonepe
Source :Hola