Question: Media.Net | DTU | FTE | Orange Tax | Omega Primes | Hungry Policemen | 2023

Entering edit mode

Hungry Policemen

You are given a graph G of N nodes and M edges and each edge has some time associated with it.

There is a policeman standing on each node except Node N.

All of them get a report that there is thief on Node N and the policemen start moving towards it, but all of them have been hungry for days, so they are looking to visit a few restaurants as well, before reaching the node N.

There are K restaurants present on some nodes, and each restaurant has some satisfaction. Now, a policeman will only go to a restaurant if and only if the satisfaction he receives by reaching the restaurant is greater than the time he has invested in reaching there and then going to the Node N.

Find and return the number of policemen who will have a meal at a restaurant.

Input Format:

The first argument contains an integer A, representing the number of nodes.

The second argument of input contains a 2 d matrix of size M x 3, B, where Node B[i][0] and Node B[i][1] are bidirectionally connected with an edge that takes B[1][2] time to go through it.

The third argument of input contains a 2-d matrix of size K x 2, C, where Node C[i][0] has a restaurant that has C[i][1] satisfaction.

Output Format: Return an integer representing the number of people who will have a dinner at the restaurant.

Constraints:

2 <- N <- 50000

1 <= M <= 100000

Output Format:

Return an integer representing the number of people who will have a dinner at the restaurant.

Constraints:

2 < N <- 50000

1 <= M <= 100000

1 <= K, B[i][e], 8[i][1] <= N

1 <= B[i][2] <= 1e4

1 <= C[i][1] <= 1e9

Example:

Input 1: A=4 B = [ [1, 2, 2], [2, 4, 1], [4, 3, 10], [3, 1, 1] ] C = [ [1, 1] ]

Output 1: 2

Explanation 1: Policemen at Node 1 and Node 3 will have a meal at node 1 without wasting any time.

Omega Primes

Carl is bored of playing with ordinary prime numbers . Thus he comes up woth pecial numbers called Omega Primes. A number X is called Omega Prime , if there exists no perfect square Y (Y>1) such that Y divides X

For example 6 is an Omega Prime because there is no perfect square 1 that divides 6 . On the other hand ,12 is not Omega Prime as 4 (which is a perfect square ) is divisor of 12

Carl decides to play a bot more with Omga primes . He has an Array A of integers . Carl wants to find the number of different subsets such that the product of elements for each subset , results in an Omega Prime . Help Carl find this number .

since this number can be large , output the answer modulo 10^9 + 7

Problem Constraints

1<= Length of A <= 2 * 10 ^4

1 <= A[i] <= 30

Input

The first argument is the integer array A

Output

Return an integer denoting the number of dieffernt desired subsets modulo 10^9 + 7

Input 1:

A = [2,4,3]

Input 2

A= [2 ,2, 2]

Example Output

Output 1 :

Output 2:

Explanation 1:

The different subsets are [0,2] , [0] , [2]. (the numbers denote the number of indcies n the array of elements )

Explanation 2:

The different subsets are : [0], [1] , [2]

Orange Tax

You live in Orange town. There are a lot of markets around that are connected with roads. These markets sell oranges at some prices. The town is not very well developed and they still use carts to transport goods from one place to the other. The roads connect two markets together and have one attribute associated with them. The attribute is the price to go from one market to the other in an empty cart. The town also has a tax factor, the tax factor is the number by which the price associated with a road needs to be multiplied, so it can go from one market to the other IF you are carrying oranges in your cart. So if a road's original price was 5 coins and tax factor of the town was 6 then in an empty cart it would take 5 coins to travel the road but if the cart contained oranges, it would cost 5 x 6 = 30 coins.

You wonder what would be the cheapest way to buy oranges if you were initially at each market. You can either buy at the market you're at or travel to some other market, buy oranges there, and travel back to the original market.

You are given an integer A denoting the number of total markets in orange town.

An integer array B denoting the price of purchasing oranges at each market.

A 2-D array C containing the information about the roads where each row contains three values.

The first two values denote the market numbers that are bi-directionally connected via a road and the third value is the price.

You are also given an integer D, this is the tax factor for the Orange town.

Find and return the required array where each element is the minimum cost to buy oranges at each market such that the starting and ending point is that market.

Problem Constraints

2 <= A <= 105

B.size() == A

1 <= B[i] <= 10^7

1 <= C.size() <=2*10^5

1 <= C[0], C[1] <= A

1 <= C[2] <= 10^3

1 <=D <= 5

Input Format

The first argument is the integer A.

The second argument is the integer array B.

The third argument is the 2-D integer array C.

The fourth argument is the integer D.

Output Format

Return an integer array as per the given problem.

Example Input

Input 1:

A = 4

B = [3, 1, 10, 11

C = [[2, 1, 2], [3, 1, 2], [4, 1, 4], [3, 2, 1], [4, 2, 2], [4, 3, 1]]

D = 1

Input 2:

A = 2

B = [1, 3]

C = [[2, 1, 3]]

D = 1

Example Output

Output 1:

[3, 1, 3, 1]

Output 2:

[1, 3]

Example Explanation

Explanation 1:

For 1st, 2nd, and 4th market, there is no better way. For the third market, since 3 and 2 are connected with a road that costs only 1. We can use that road to travel to 2 for cost 1 and buy oranges from market 2 for cost 1, and travel back for cost 11 for a final cost of 3. Explanation 2:

1 and 3 are already their respective minimum costs.

ADD COMMENT • link

Entering edit mode

// OMEGA_PRIME
#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i, n) for (i = 0; i < n; i++)
#define Fo(i, k, n) for (i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
#define ll long long
#define si(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define ss(s) scanf("%s", s)
#define pi(x) printf("%d\n", x)
#define pl(x) printf("%lld\n", x)
#define ps(s) printf("%s\n", s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
void cout_v(vector<int> &v)
{
    for (auto it : v)
        cout << it << " ";
}
int rng(int lim)
{
    uniform_int_distribution<int> uid(0, lim - 1);
    return uid(rang);
}
const int mod = 1000000007;
ll inv(ll i)
{
    if (i == 1)
        return 1;
    return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;
}

ll mod_mul(ll a, ll b)
{
    a = a % mod;
    b = b % mod;
    return (((a * b) % mod) + mod) % mod;
}

ll mod_add(ll a, ll b)
{
    a = a % mod;
    b = b % mod;
    return (((a + b) % mod) + mod) % mod;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll ceil_div(ll a, ll b) { return a % b == 0 ? a / b : a / b + 1; }

int mpow(int base, int exp)
{
    base %= mod;
    int result = 1;
    while (exp > 0)
    {
        if (exp & 1)
            result = ((ll)result * base) % mod;
        base = ((ll)base * base) % mod;
        exp >>= 1;
    }
    return result;
}

/*

1. Think Greedy
2. Think Brute Force
3. Think solution in reverse order
4. Think DP [ check constraints carefully ]
5. Check base cases for DP and prove solution for Greedy
6. Think Graph

*/
// #@copyrightMUKESH
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////*

void solve()
{

    vi primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    vector<bool> is_omega_prime(31, true);
    for (int i = 1; i <= 30; i++)
    {
        for (auto it : primes)
        {

            if (i % (it * it) == 0)
            {
                is_omega_prime[i] = false;
                break;
            }
        }
    }
    vi masks;
    int n;
    cin >> n;
    vi a(n);
    int i;
    fo(i, n) cin >> a[i];
    fo(i, n)
    {
        if (!is_omega_prime[a[i]])
            continue;
        int mask = 0;
        for (int j = 0; j < 10; j++)
        {
            if ((a[i] % primes[j]) == 0)
                mask += 1 << j;
        }

        masks.pb(mask);
    }
    int m = masks.size();

    vvi dp(m + 1, vector<int>((1 << 10), -1));
    function<int(int, int)> helper = [&](int ind, int mask)
    {
        if (ind == m)
            return (mask != 0) ? 1 : 0;
        if (dp[ind][mask] != -1)
            return dp[ind][mask];
        int ans = 0;
        if (!(mask & masks[ind]))
        {
            ans = mod_add(ans, helper(ind + 1, mask | masks[ind]));
        }
        ans = mod_add(ans, helper(ind + 1, mask));
        return dp[ind][mask] = ans;
    };
    cout << helper(0, 0) << "\n";
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t = 1;

    while (t--)
    {
        solve();
    }

    return 0;
}

ADD REPLY • link 15 months ago

mk390270 • 50