Contest Link: DAIICT IPC-1 2022
About Intra DA Programming Contest (IPC): These are the short duration contests of 2.5 hours durations with 6-7 problems. The aim of these contests is to create a healthy and competitive environment of coding in the college(DAIICT), increase the problem solving skills and DSA knowledge.
Q-1 Alice Vs. Bob
Hint
Manage two variables, one with score of $$$1^{st}$$$ player and other with score of $$$2^{nd}$$$ player. Traverse the string and if one among two reaches to 11 break the loop and check who is the winner!
Codes
Author: KunalHS
Author's Code
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (int i = 0; i < n; i++)
#define count(n) for (int i = 1; i <= n; i++)
#define ll long long int
#define l long int
#define ld long double
#define ia(arr, n) fo(i, n) cin >> arr[i]
#define mo % 1000000007
#define precise(x) fixed << setprecision(x)
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
string s;
cin >> n >> s;
int alice = 0, bob = 0;
for (int i = 0; i < n; i++)
{
alice += s[i] == 'A';
bob += s[i] == 'B';
if (alice == 11)
{
cout << "Alice" << '\n';
break;
}
if (bob == 11)
{
cout << "Bob" << '\n';
break;
}
}
}
return 0;
}
Tester: zxy0909
Tester's Code
#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
ll add(ll x,ll y) {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y) {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y) {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}
void solve(){
int n; cin>>n;
assert(n>=1 && n<=21);
string s; cin>>s;
assert(l(s) == n);
int cnt = count(all(s),'A');
assert(cnt >=11 || (n-cnt) >= 11);
int cnt1=0,cnt2 = 0;
loop(i,0,n){
if(s[i] == 'A') cnt1++;
else cnt2++;
if(cnt1 == 11 || cnt2 == 11) break;
}
assert(cnt1 == 11 || cnt2 == 11);
if(cnt1 == 11) cout<<"Alice\n";
else cout<<"Bob\n";
}
int main()
{
fast
int t; cin>>t;
while(t--) solve();
return 0;
}
Q-2 Minimum Cost Multiplication
Hints
Hint1
Suppose you have $$$2$$$ variables $$$a$$$ and $$$b$$$.$$$ (a ≤ b)$$$. which value you will decrease such that product will be minimum.
Hint2
If you decrease greater value ($$$b$$$) than now you have $$$a*(b-1)$$$ and if you decrease $$$a$$$ than you have $$$b*(a-1)$$$. which value is smaller?
Hint3
You will decrease smaller value first if possible...
Hint4
Those who were getting TLE in this question, try to use Fast I/O.
Codes
Author: KunalHS
Author's Code
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (ll i = 0; i < n; i++)
#define count(n) for (ll i = 1; i <= n; i++)
#define ll long long int
#define l long int
#define ld long double
#define ia(arr, n) fo(i, n) cin >> arr[i]
#define mo % 1000000007
#define precise(x) fixed << setprecision(x)
int p = 1e9 + 7;
ll add(ll a, ll b)
{
return (((a % p) + (b % p)) % p);
}
ll sub(ll a, ll b)
{
return (((a % p) - (b % p)) % p);
}
ll mul(ll a, ll b)
{
return (((a % p) * (b % p)) % p);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
ll n, m;
cin >> n >> m;
vector<ll> a(n);
fo (i, n) { cin >> a[i]; }
sort(a.begin(), a.end());
ll ans = 1;
fo (i, n)
{
if (m > 0 && a[i] > 1)
{
ll minus = min(m, a[i] - 1);
a[i] = sub(a[i], minus);
m = sub(m, minus);
}
ans = mul(ans, a[i]);
}
cout << ans << "\n";
}
return 0;
}
Tester: zxy0909
Tester's Code
#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
ll add(ll x,ll y) {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y) {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y) {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}
ll N = 0;
void solve(){
int n; cin>>n;
int m; cin>>m;
vector<int> v(n); in(v,n);
assert(n>=1 && n<=1e6);
assert(m>=1 && m<=1e5);
for(auto i:v) assert(i>=1 && (i<=1e8));
N+=n;
sort(all(v));
loop(i,0,n){
if(v[i] == 1) continue; if(v[i]-1 <= m) m-=(v[i]-1),v[i] =1 ;
else v[i]-=m,m=0;
}
ll ans = 1;
loop(i,0,n) ans = mul(ans,v[i]);
cout<<ans<<endl;
}
int main()
{
fast
int t; cin>>t;
assert(t>=1 && t<=1e5);
while(t--) solve();
assert(N<=1e6);
return 0;
}
Q-3 Ram ka karo kam
Hints
Hint1
Try to derive mathematical equation for $$$k$$$.
Hint2
Starting equation
$$$Y = X((1+k+k^2+...+k^{a_1}) + (1+k+k^2+...+k^{a_2}) + (1+k+..+k^{a_3}) + ...... + (1+k+..k^{a_n}))$$$
Last equation
$$$(k-1)\left( \frac{y}{x} \right) + n$$$ $$$=$$$ $$$\sum_{i = 1}^n k^{a_i+1}$$$, where all $$$a_i$$$ are pairwise distinct.
Hint3
For $$$ y \mod x$$$ $$$!=$$$ $$$0$$$ value cannot be achievable, so the answer for this will be $$$-1$$$.
For $$$ y \mod x = 0 $$$,here in the above formula maximum value of $$$n$$$ will be always smaller than $$$64$$$(depending on value of $$$k$$$), except for $$$k = 1$$$. For $$$k = 1$$$ value can be achievable in $$$y/x$$$ steps. You can fix the value of $$$n$$$, now your left side is constant, and now you have to check left side number in base $$$k$$$. Number of on-bit in the left side number must be equal to $$$n$$$. Value of on-bit in the left side number must be less or equal to 1 and also left side number must be divisible by $$$k$$$. $$$(Why?)$$$
Codes
Author: achyut_1412
Author's Code
#include <bits/stdc++.h>
#include <iostream>
#define ull long long int
using namespace std;
#define maxlen 100000
bool sortVec(const vector<ull> &l, const vector<ull> &r){
if (l[1]==r[1]){
if (l[0]==r[0])return l[2] > r[2];
else return l[0] > r[0];
}
else return l[1] > r[1];
}
ull check(ull n,ull k){
ull c = 0;
ull tmp=n;
while(tmp>0){
ull rmd=tmp%k;
tmp=tmp/k;
if(rmd>=2)
return -1;
if(rmd==1)
c++;
}
return c;
}
ull val(ull n,ull k){
ull c = 0;
for (ull i = 0;n>0; i++){
ull rmd=n%k;
if(rmd==1)
c+=i;
n=n/k;
}
return c;
}
void solve(){
ull x, y,k;
cin>>x>>y>>k;
if (y%x != 0 || x>y){
cout<<"-1"<<"\n";
return;
}
else{
if(x==y){
cout<<1<<endl;
return ;
}
y=y/x;
if(k==1){
cout<<y<<endl;
return ;
}
for (ull i = 0; i < 64; i++){
//cout<<check(y*(k-1)+i,k)<<" "<<i<<" "<<y+i<<"\n";
if((y*(k-1)+i)%k)
continue;
if (check((y*(k-1)+i),k)==i){
//(i-1) for breaks
cout<<val((y*(k-1)+i),k)+i-1<<"\n";
return;
}
}
cout<<"-1"<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
Tester: zxy0909
Tester's Code
#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
ll add(ll x,ll y) {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y) {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y) {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}
pair<ll,ll> fn(ll n, ll x)
{
ll vl1 = 0,vl2 = 0,cnt= 0;
while (n > 0) {
int rem = n % x;
if (rem >= 2) return {-1,-1};
if(rem) vl1++,vl2+=cnt;
cnt++;
n = n/x;
}
return {vl1,vl2};
}
void solve(){
ll x,y,k; cin>>x>>y>>k;
assert(x>=1 && x<=1e18 && y>=1 && y<=1e18 && k>=1 && k<=10);
ll ans = INT_MAX;
if(y%x) {cout<<-1<<endl; return;}
if(k == 1 || x == y){
cout<<y/x<<endl;
return;
}
ll tmp3 = y/x;
ll mx_vl = log10(LONG_LONG_MAX)/log10(k);
loop(i,1,mx_vl+1){
ll tmp = tmp3,vl = 0,vl2=tmp3;
pair<ll,ll> p = fn(((k-1)*(tmp3)+i),k);
if(((k-1)*(tmp3)+i)%k) continue;
vl = p.fr,vl2 = p.sc;
if(vl == i){
ans = min(ans,vl2+i);
}
}
if(ans == INT_MAX) cout<<-1<<endl;
else cout<<ans-1<<endl;
}
int main()
{
fast
int t; cin>>t;
assert(t >=1 && t<=1e5);
while(t--) solve();
return 0;
}
Q-4 A Game
Hints
Hint1
Firstly we have to take mod of all the elements with $$$(A+B)$$$ because when any number is greater than $$$(A+B)$$$, there is a series of operations you and the bot can do. When it becomes less than $$$(A+B)$$$, it decides that either of you can do the operations on it or not, and if it's less than A+B then either only one of you can do operation or neither of you can perform operation on it.
Hint2
After doing this, all the elements are now less than $$$(A+B)$$$. As the bot made the last move, so now it’s your chance. You check if any element is $$$>= A$$$, then you subtract it with $$$A$$$. If there is no such element, you lose, else the bot will check now if there is any element such that it is $$$>=B$$$. If there is no such element, it loses, and you win, else you lose because now there will be no element that can be $$$>= A$$$.
Codes
Author: dev_kabra
Author's Code
#include <bits/stdc++.h>
using namespace std;
int main(){
int test;
cin>>test;
while(test--){
int N, X, Y;
cin >> N >> X >> Y;
vector<int> A(N);
for (int i = 0; i < N; i++){
cin >> A[i];
}
for (int i = 0; i < N; i++){
A[i] %= X + Y;
}
bool ok = 1;
for(int i=0;i<N;i++){
if(A[i]>=X){
ok = false;
A[i]-=X;
}
}
if(ok){
cout<<0<<'\n';
}
else{
ok = 1;
for(int i=0;i<N;i++){
if(A[i]>=Y){
ok = false;
A[i]-=Y;
}
}
if(ok)
cout<<1<<'\n';
else
cout<<0<<'\n';
}
}
}
Tester: kunj_patel
Tester's Code
#include <bits/stdc++.h>
#include <iostream>
#define ull long long int
using namespace std;
bool sortVec(const vector<ull> &l, const vector<ull> &r){
return l[0] < r[0];
}
void solve(){
ull n, a, b;
cin>>n>>a>>b;
ull arr[n];
ull ga = 0, gb = 0;
for (ull i = 0; i < n; i++){
cin>>arr[i];
arr[i] = arr[i]%(a+b);
if (arr[i] >= a)ga++;
if (arr[i] >= b)gb++;
}
if (ga==0){
cout<<0<<"\n";
}
else if (ga >= gb){
cout<<1<<"\n";
}
else{
cout<<0<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
Q-5 New Capital
Hints
Hint1
As given in the question distance between $$$2$$$ node is the weight of max edge between them. So a good idea to find these values for every node is to make a table(array) and store values in it.
We start by making $$$2$$$ arrays, one to store distance to all nodes below the current node(lets name it $$$D$$$) and one for all other node(lets name it $$$U$$$).
Hint2
We perform a DFS and calculate $$$D$$$, when we reach a particular node we would have calculated $$$D$$$ for all its immediate children we traverse through them is a nodes distance from the child is less than the weight of edge from current node to the child we put note the distance of that node as weight of the edge(as it would be the max edge) else we keep it same(max edge is edge other than one connecting node and the child).
Hint3
For the root $$$D$$$ and $$$U$$$ are the same.
Then we perform another DFS and repeat the process but this time for $$$U$$$ and considering edge from current node to the parent. Read the solution code understand more.
Codes
Author: kunj_patel
Author's Code
#include <bits/stdc++.h>
#include <iostream>
#define ull long long int
using namespace std;
#define maxlen 2*100000
#define edg_wt 100
bool sortVec(const vector<ull> &l, const vector<ull> &r){
if (l[1]==r[1]){
if (l[0]==r[0])return l[2] > r[2];
else return l[0] > r[0];
}
else return l[1] > r[1];
}
vector<vector<ull>> adj(maxlen+1);
vector<vector<ull>> weight(maxlen+1);
vector<ull> parent(maxlen+1, 0);
vector<vector<ull>> up(maxlen+1, vector<ull> (edg_wt+1, 0));
vector<vector<ull>> down(maxlen+1, vector<ull> (edg_wt+1, 0));
vector<ull> val(maxlen+1);
ull temp[edg_wt+1]={0};
void get_parent(ull root, ull p){
parent[root]=p;
//cout<<root<<" ";
for (ull i = 0; i < adj[root].size(); i++){
if (adj[root][i]!=p){
get_parent(adj[root][i], root);
}
}
}
void calc_down(ull root, ull p){
for (ull i = 0; i < adj[root].size(); i++){
if (adj[root][i]!=p){
calc_down(adj[root][i], root);
}
}
//cout<<root<<"\n";
for (ull i = 0; i < adj[root].size(); i++){
if (adj[root][i]!=p){
//cout<<weight[root][i]<<" ";
down[root][weight[root][i]]++;
for (ull j = 0 ; j <= edg_wt; j++){
if (j > weight[root][i])
down[root][j]+=down[adj[root][i]][j];
else
down[root][weight[root][i]]+=down[adj[root][i]][j];
}
}
}
//cout<<"\n";
}
void calc_up(ull root, ull p, ull up_ed){
for (ull i = 0; i <= edg_wt; i++){
temp[i] = up[p][i];
}
for (ull i = 0; i <= edg_wt; i++){
if (i < up_ed){
temp[up_ed]-=down[root][i];
}
else{
temp[i]-=down[root][i];
}
}
for (ull i = 0; i < edg_wt+1; i++){
if (i < up_ed)up[root][up_ed]+=temp[i];
else up[root][i]+=temp[i];
up[root][i]+=down[root][i];
}
for (ull i = 0; i < adj[root].size(); i++){
if (adj[root][i]!=p){
calc_up( adj[root][i], root, weight[root][i]);
}
}
}
/*
11 0
1 4 2
1 3 4
4 6 8
7 4 7
8 6 2
6 5 5
3 2 3
3 9 6
10 2 6
2 11 9
*/
void solve(){
ull n, q;
cin>>n>>q;
ull u, v, w;
for (ull i = 0; i < n-1; i++){
cin>>u>>v>>w;
adj[u].push_back(v);
weight[u].push_back(w);
adj[v].push_back(u);
weight[v].push_back(w);
}
get_parent(1, 0);
calc_down(1, 0);
/*cout<<"\n";
for (ull i = 1; i <= n; i++){
cout<<i<<"->"<<" ";
for (ull j = 1; j <= edg_wt; j++){
cout<<down[i][j]<<" ";
}
cout<<"\n";
}*/
for (ull i = 0; i <= edg_wt; i++){
up[1][i]=down[1][i];
}
for (ull i = 0; i < adj[1].size(); i++){
if (adj[1][i]!=0){
calc_up( adj[1][i], 1, weight[1][i]);
}
}
/*cout<<"\n";
for (ull i = 1; i <= n; i++){
cout<<i<<"->"<<" ";
for (ull j = 1; j <= edg_wt; j++){
cout<<up[i][j]<<" ";
}
cout<<"\n";
}
cout<<"\n";*/
for (ull i = 1; i <= n; i++){
ull v = 0;
for (ull j = 0; j <= edg_wt; j++){
v += j*(up[i][j]);
}
val[i]=v;
//cout<<v<<" ";
}
ull num;
///cout<<"\n";
for (ull i = 0; i < q; i++){
cin>>num;
cout<<val[num]<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;
//cin>>t;
//while(t--){
//freopen ("input11.txt", "r", stdin);
solve();
//}
return 0;
}
Tester: zxy0909
Tester's Code
#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
ll add(ll x,ll y) {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y) {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y) {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}
map<pair<int,int>,int> m;
vector<vector<int>> v;
vector<int> vis;
vector<vector<int>> freq;
vector<int> final;
vector<int> fn(int i,int par){
vector<int> ans(101,0);
for(auto j:v[i]){
if(j == par) continue;
vector<int> tmp = fn(j,i);
int vl = m[{i,j}];
for(int k=vl;k<=100;k++) ans[k]+=tmp[k];
ans[vl]++;
for(int k=0;k<vl;k++) ans[vl]+=tmp[k];
}
return freq[i] = ans;
}
void fn2(int i,int par,vector<int> vec){
vector<int> ans(101,0);
if(par!=-1){
ans = freq[par];
int vl = m[{i,par}];
for(int j=0;j<=100;j++) if(j<=vl) ans[vl]+=vec[j]; else ans[j]+=vec[j];
for(int j=0;j<=100;j++){
if(j<=vl) ans[vl]-=freq[i][j];
else ans[j]-=freq[i][j];
}
int vl2 = 0;
for(int j=0;j<=100;j++) if(j<vl) ans[vl]+=ans[j],ans[j]=0;
for(int j=0;j<=100;j++) if(j<=vl) vl2+=(vl*ans[j]); else vl2+=(j*ans[j]);
for(int j=0;j<=100;j++) vl2+=(j*freq[i][j]);
final[i] = vl2;
}
for(auto j:v[i]){
if(j == par) continue;
fn2(j,i,ans);
}
}
void solve(){
ll n,q; cin>>n>>q;
assert(n>=1 && n<=2e5 && q>=1 && q<=2e5);
v.assign(n+1,{});
freq.assign(n+1,{});
vis.assign(n+1,0);
final.assign(n+1,0);
loop(i,1,n){
ll a,b,w; cin>>a>>b>>w;
assert(a>=1 && a<=n && b>=1 && b<=n && w>=1 && w<=100);
v[a].pb(b);
v[b].pb(a);
m[{a,b}] = m[{b,a}] = w;
}
fn(1,-1);
vector<int> tmp(101,0);
fn2(1,-1,tmp);
int vl = 0;
for(int j=0;j<=100;j++) vl+=(j*freq[1][j]);
final[1] = vl;
while(q--){
int k; cin>>k;
cout<<final[k]<<endl;
}
}
int main()
{
fast
int t = 1;
while(t--) solve();
return 0;
}
Q-6 Game of Indexes and Values
Hints
Hint1
For gcd you just have to calculate for prime-factors only. there will be at most $$$6$$$ prime-factor for any number in $$$[1,100000]$$$.
Hint2
Suppose you have store all the possible value of $$$(v[i]/x)$$$ ($$$x$$$ is prime number) in the binary form, for all $$$i$$$ in the Trie with indexes. Now if you fixed one prime number than for minimum value you will try to search for all bits $$$0$$$ and for maximum value you will try to search for all bits $$$1$$$. From this you can handle type of query $$$1$$$.
Hint3
Assume that you don't have to delete the element in the array but you just have to erase the value of that index from Trie. For each query calculate the original value of $$$l$$$ and $$$r$$$ in the original array from the help of Fenwick tree/Segment tree.
Code
Author: zxy0909
Author's Code
#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
ll add(ll x,ll y) {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y) {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y) {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}
class Node{
public:
Node* link[2];
set<int> s;
Node(){
link[0] = link[1] = NULL;
}
};
// Implementation of Trie
class Trie{
public:
Node* root = new Node();
// inserting value and index.
void insert(int n,int idx){
Node* ne = root;
for(int i=17;i>=0;i--){
int bit = (n>>i)&1;
if(ne->link[bit] == NULL) {
ne->link[bit] = new Node();
}
ne = ne->link[bit];
ne->s.insert(idx);
}
}
// finding maximum and minimum value and index in [l,r].
pair<int,int> find(int x,int l,int r){
Node *ne = root;
int i = 17,ans = 0,idx=-1;
while(ne && i>=0){
int bit = (x>>i)&1;
if(ne->link[bit]){
auto it = ne->link[bit]->s.lower_bound(l);
if(it!=ne->link[bit]->s.end() && *it <= r) {
ne = ne->link[bit];
if(bit == 1) ans+=(1ll<<i);
}
else if(bit) ne = ne->link[0];
else ne = ne->link[1],ans+=(1ll<<i);
}
else if(bit) ne = ne->link[0];
else ne = ne->link[1],ans+=(1ll<<i);
if(!ne) return {-1,-1};
i--;
}
if(i!=-1) return {-1,-1};
auto it = ne->s.lower_bound(l);
if(it == ne->s.end() || *it>r) return {-1,-1};
idx = *it;
return {ans,idx};
}
// removing perticular index from the trie.
void erase(int idx,int old){
Node *ne = root;
for(int i=17;i>=0;i--){
int bit = (old>>i)&1;
ne = ne->link[bit];
ne->s.erase(idx);
}
}
};
vector<int> spf(100000+1,INT_MAX),vec(20000+1,0);
// finding all prime factor of n
vector<int> prime_fact(int n){
vector<int> ans = {1};
while(n!=1){
int x = spf[n];
ans.push_back(x);
while(n!=1 && spf[n] == x) n/=spf[n];
}
return ans;
}
// fenwick tree
int query(int i){
if(i <= 0) return 0;
int ans = 0;
for(;i;i-=(i&(-i))) ans+=vec[i];
return ans;
}
void add_(int i,int vl){
for(;i<=20000;i+=(i&(-i))) vec[i]+=vl;
}
// for 2nd type of query-finding original position of x in the array.
int find_idx(int x){
int l = 1,r = 2e4,idx;
while(l<=r){
int mid = (l+r)/2;
int vl = query(mid);
if(vl < x) l = mid+1;
else r = mid-1,idx = mid;
}
return idx;
}
void solve(){
vector<Trie> trie(100000+1);
// input
int n; cin>>n;
assert(n>=1 && n<=2e4);
vector<int> v(n); in(v,n);
loop(i,0,n) assert(v[i]>=1 && v[i]<=1e5);
// building trie
loop(i,0,n){
vector<int> factors = prime_fact(v[i]);
for(auto j:factors) trie[j].insert(v[i]/j,i+1);
}
//
vector<int> final_ans;
loop(i,1,2e4+1) add_(i,1);
int q; cin>>q;
assert(q>=1 && q<=1e5);
int j = 0;
while(q--){
// input
int type ; cin>>type;
assert(type == 1 || type == 2);
int l,r,x; cin>>l>>r>>x;
assert(l>=1 && r>=1 && r>=l);
assert(x>=2 && x<=1e5);
assert(r<=n-j);
//
l = find_idx(l); // finding current position of l in original array
r = find_idx(r); // finding current position of r in original array
//
vector<int> factor = prime_fact(x);
//
vector<pair<int,int>> ans1,ans2; // ans1 for minimum value and ans2 for maximum value
for(auto j:factor){
if(j == 1) continue;
pair<int,int> p = trie[j].find(0,l,r); // (000....0000) for minimum value
if(p.sc == -1 || p.sc>r || p.sc < l) continue;
ans1.push_back({p.fr*j,p.sc});
p = trie[j].find((1ll<<18)-1,l,r); // (1111...1111) for maximum value
ans2.pb({p.fr*j,p.sc});
}
// sorting all possible values
sort(all(ans1));
sort(all(ans2));
//
if(type == 1){
if(ans2.size() == 0) final_ans.pb(-1); // if no element is present with those conditions
else final_ans.pb(ans2.back().fr-ans1[0].fr); // otherwise ans will be maximum value - minimum value
}
else{
if(!ans1.size()){
pair<int,int> p = trie[1].find(0,l,r); // if no element is present than finding minimum value
ans1.push_back(p);
}
factor = prime_fact(ans1[0].fr); // taking minimum value and removing that index it from the trie
for(auto j:factor) trie[j].erase(ans1[0].sc,ans1[0].fr/j);
add_(ans1[0].sc,-1);
final_ans.push_back(ans1[0].sc);
j++;
}
}
for(auto i:final_ans) cout<<i<<endl;
}
int main()
{
fast
// finding smallest_prime_factor of all element in [1,100000].
for(int i=2;i<=1e5;i++) spf[i] = i;
for(int i=2;i<=1e5;i++){
if(spf[i] == i){
for(int j=i;j<=1e5;j+=i) spf[j] = min(spf[j],i);
}
}
int t = 1;
while(t--) solve();
return 0;
}
Please allow to view contest.
For that you have to click on the contest link given at the beginning of the blog.