Entering edit mode

Question 1

Computer Lab

In the computer lab, there are N tables numbered O to N-1. In each of the tables, either a student is seated or it is empty. The students will use computers to work on their assignments. A student can use a computer if it is placed to its immediate left or tots immediate right.

Find the minimum number of computers that need to be allotted to the lab to serve all students .

Determine if it is impossible for all students to work on assignments.

Notes

The computers can only be placed in empty tables.
Two students can share one computer
If lab[i]"S", there is a student seated. If lab[i]=" ", it is empty.

Parameters description

N: Represents the number of tables
lab:Represents the state of tables

Input format

The first line contains N denoting the number of tables.
The second line contains lab denoting the string explaining the state of lab

Output format

Print the number of computers needed or -1 in case all students cannot be served

Constraints:

0<=n<=10⁵,contains only English lowercase letters

SAMPLE INPUT:
6
I apple 2
I google 1
I sprinklr 10
I spring 2
Q apple
Q spr


SAMPLE OUTPUT
2 
12

Explanation

1. Frequency for apple is 2

2. spr prefix comes in 2 terms: sprinkir & spring, so frequency of prefix=10-2-12

Note: Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement. Limits

Time Limit 5.0 sec(s) for each input file

Memory Limit: 256 MB

Source Limit 1024 KB

Question 2

Prime Pairs

Given a tree with N nodes and N-1 edges at node 1.We need to find the number of pairs of vertices (i,j) such that there exists exactly one prime number on the path between vertex i and j.

Parameters desciption

N Represent the number of nodes in the tree
edge: Represent the edges present in the tree

Input format

The first line contains N denoting the number of vertices in the tree.
The next N-1 lines contain two space-separated integers uv denoting an edge between vertex u and v

Output format

Print a single integer, denoting the number of valid pairs (i,j).

Constraints

1≤ N ≤ 10⁵

1≤ u,v≤ N

SAMPLE INPUT
7
1 2
1 3
2 6
3 4 
3 5
4 7
 
SAMPLE OUTPUT:
7

Search Engine

Prof. Arnab Bhattacharya has asked you to implement a basic search engine which gives you term frequencies for his course Information Retrieval. This search engine will have these functionalities:-

1. Index i.e. store a given term & it's frequency

2. Prefix query L.e. frequency of terms with given prefix (upto this point)

3. Update i.e. update frequency of given term

Input:

First line: Integer n denoting number of operations. Next n lines containing space seperated operation, string (say op_i 8_i f_i) & integer only if it's index/update operation Where op_i== 'Q' denotes prefix query, op_i =='I' (capital i) denotes index operation, op_i== 'U' denotes update operation, s_i is string to be queried or indexed & f_i is frequency of terms (present only if op,='I' or op_i ='U').

Output: Term frequency for every prefix query in newline.

Constraints:

0≤ n ≤ 106 s, contains only English lowercase letters

10⁴>= f_i≥ 1 Length of s_i≤ 30

Sample Input:
6 
I apple 2
I google 1
I sprinklr 10
I spring 2
Q apple
Q spr

Sample Output:
2
12

Explanation:

1.Frequecny for appleis 2.

2.spr prefix comes in 2 terms:sprinklr & spring so frequency of prefix = 10+2=12

ADD COMMENT • link

Entering edit mode

0

/**************************************PRIME PAIRS - without dsu************************************************/

#include<bits/stdc++.h>

#define endl "\n"

#define ff first

#define ss second

#define int long long

typedef long long ll;

typedef long double ld;

using namespace std;

#ifndef ONLINE_JUDGE

#include "include/debug.h"

#else

#define debugarr(a, n) 42

#define debug(...) 42

#endif

void code(int TC){

int n; cin >> n;

vector<vector<int>> T(n + 5);

for(int i = 0; i < n - 1; i += 1){

int u, v; cin >> u >> v;

T[u].push_back(v);

T[v].push_back(u);

}

vector<int> is(n + 5), done(n + 5);

for(int i = 2; i <= n; i += 1){

if(done[i]) continue;

is[i] = 1;

for(long long j = (long long)i * i; j <= n; j += i) done[j] = 1;

}

vector<long long> op(n + 5), cl(n + 5);

long long ans = 0;

function<void(int, int)> dfs = [&](int u, int p){

vector<long long> o, c;

for(auto v : T[u]){

if(v == p) continue;

dfs(v, u);

o.push_back(op[v]);

c.push_back(cl[v]);

}

long long all = accumulate(o.begin(), o.end(), 0ll);

if(is[u]){

ans += all;

op[u] = 0;

cl[u] = all + 1;

for(auto i : o) ans += (all -= i) * i;

}

else{

long long ops = accumulate(c.begin(), c.end(), 0ll);

int sz = o.size();

ans += ops;

for(int i = 0; i < sz; i += 1){

ans += c[i] * (all - o[i]);

}

op[u] = all + 1;

cl[u] = ops;

}

};

dfs(1, 0);

cout << ans << endl;

}

signed main(){

ios_base::sync_with_stdio(0);

cin.tie(0);cout.tie(0);cerr.tie(0);

cout.precision(30);

int TT = 1;

for (int TC = 1; TC <= TT; TC++)

code(TC);

return 0;

}

ADD REPLY • link 14 months ago

__Beginner__ • 0

5

Entering edit mode

Q2. Computer Lab

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define vll vector<ll>

#define vpr vector<pair<ll, ll>>

#define vvl vector<vector<ll>>

string s;

vll a;

ll n;

int main() {

cin >> n >> s;

vll alot(n);

a = vll(n);

ll ans = 0;

vll vis(n + 2);

vll cnt(n);

for(ll i = 0; i < n; i++) {

if(s[i] == '.') {

if(i > 0 && s[i - 1] == 'S' && !cnt[i] && !vis[i - 1]) {

ans++;

cnt[i] = 1;

vis[i - 1] = 1;

}

else {

if(i + 2 < n && s[i + 2] == '.' && i + 3 < n && s[i + 3] == 'S' && !cnt[i + 2] && !vis[i + 3]) {

ans++;

cnt[i + 2] = 1;

vis[i + 3] = 1;

}

else if(i + 1 < n && s[i + 1] == 'S' && !cnt[i] && !vis[i + 1]) {

ans++;

cnt[i] = 1;

vis[i + 1] = 1;

}

cout << ((ans == 0)?-1:ans) << endl;

}

Q3. Prime Pairs

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define vll vector<ll>

#define vvl vector<vector<ll>>

ll n;

vll par, sz;

vvl tree;

ll find(ll u) {

if(par[u] == u) return u;

return par[u] = find(par[u]);

}

void Union(ll a, ll b) {

a = find(a);

b = find(b);

if(a != b) {

if(sz[a] < sz[b]) swap(a, b);

sz[a] += sz[b];

par[b] = a;

}

int main() {

cin >> n;

tree = vvl(n + 1);

sz = vll(n + 1, 1);

par = vll(n + 1);

for(ll i = 0; i < n; i++) par[i] = i;

vll vis(n + 1), primes;

vis[0] = vis[1] = 1;

ll ans = 0;

for(ll i = 2; i <= n; i++) {

if(!vis[i]) {

primes.push_back(i);

for(ll j = i * i; j <= n; j += i) {

vis[j] = 1;

}

for(ll i = 0; i < n - 1; i++) {

ll u, v; cin >> u >> v;

if(!vis[u] && !vis[v]) continue;

else if(!vis[u]) {

tree[u].push_back(v);

}

else if(!vis[v]) {

tree[v].push_back(u);

}

else {

Union(u, v);

}

for(ll i = 0; i < primes.size(); i++) {

ll in = 1LL;

for(auto& child: tree[primes[i]]) {

in += sz[find(child)];

}

for(auto& child: tree[primes[i]]) {

ans += (1LL * sz[find(child)] * (in - sz[find(child)]));

in -= sz[find(child)];

}

cout << ans << "\n";

return 0;

}

ADD COMMENT • link 16 months ago Mayank • 90

Entering edit mode

0

I want some clarification. Can I get your no.?

ADD REPLY • link 17 months ago

ADARSH RANJAN • 0

Entering edit mode

0

Yes you can contact me at bharatim1221@gmail.com

ADD REPLY • link 16 months ago

Mayank • 90

Entering edit mode

0

i think summation of last second loop "in" variable will give the answer, why did u use last loop could u pls explain?

ADD REPLY • link 14 months ago

asdd • 0

Entering edit mode

0

ohh got it all possible combination great idea

ADD REPLY • link 14 months ago

asdd • 0

Login before adding your answer.