Guys please share your approaches for the problems you solved. How many did you guys solve?
Problem 1
There are N cities numbered from 1 to N connected by M bidirectional roads. A concert is going to be held in each city and i_th city concert costs A[i] amount. Travelling through the roads also costs some amount given.
For each city i from 1 to N : find the minimum amount a person from city i has to spend to visit a concert in any of the city and come back to own city.
It may not be guarenteed that each city is reachable from other city.
N,M<=10^5
=====================================
Problem 2
Given rooted tree of N vertices from 1 to N. Every vertex must not have same color as it's p-th ancestor. Every vertex must have either red or green color. Calculate the number of ways to color the tree.
N,p<=10^5
=====================================
Problem 3
You are going to make a necklace of N beads using K different colored beads.
There are unlimited beads of each color.
You need to find the expected value of number of distinct colors used, if every necklace is equiprobable to be made.
Two necklaces are considered same if after some rotation they are identical.
You need to find this value for each N from 1 to M, modulo 1e9+7.
K,M<=10^5
=====================================
Problem 4
Find lexicographically smallest permutation of 1 to N where there are exactly B good indices.
A good index i is one where the element at this index is greater than all it's previous elements(at indices<i).
N,B<=10^5
=====================================
Problem 5
Given an array of length N. You can change any number to anything else. Calculate the minimum number of changes needed to make the array such that every subarray of size K will have Bitwise Xor = 0.
N,K<=10000
A[i]<=2^10-1
=====================================
Problem 6
Indumati has been given an array of A ones and B zeroes.
One operation is:
-> Select any C elements from the array and delete them from the array and append their average (in irreducable fraction from) to the array.
It's guarenteed that A+B-C is multiple of C-1.
Indumati repeats this operation until only 1 number is remaining.
Your task is to calculate the number of distinct values the fraction can take, modulo 1e9+7.
A,B<=2000
2<=C<=2000
=====================================