Thank you for participating in DECATHLON.
DECOBITS
The condition A&B=A|B satisfies when A=B.
There can be 3 condition for each bit in A and B.
- Both bits are same
- Bit is 1 in A and 0 in B
- Bit is 0 in A and 1 in B
To make A and B equal we only need to handle condition 2 and 3.
If sum of cnt1 and cnt2 is odd, then it is impossible to make them equal.
Let cnt1 be bits satisying condition 2 and cnt2 be bits satisying condition 3.
2 bits satifying condition 2 can be made equal by performin 1 operation.
Similarly, 2 bits satifying condition 3 can be made equal by performin 1 operation.
I we have 1 bit satisfying condition 2 and 1 bit satisfying condition 3, then we can make them equal in 2 operations.
So the answer will be cnt1/2 + cnt2/2 + 2*(cnt1%2 + cnt2%2).
Time complexity: O(1) per test case
Code
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;
main()
{
ll t,a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
int ans=0, cnt1=0, cnt2=0;
for(ll i=0;i<62;i++)
{
if(((1LL<<i)&a) && !((1LL<<i)&b))
cnt1++;
else if(!((1LL<<i)&a) && ((1LL<<i)&b))
cnt2++;
}
ans+=cnt1/2+cnt2/2;
cnt1%=2;
cnt2%=2;
if(cnt1==cnt2)
{
if(cnt1)
ans+=2;
}
else
ans=-1;
cout<<ans<<endl;
}
}
DECOANA
“A string s is known as good string if any anagram of the string is lexicographically greater than every anagram of
the string P”
This condition satisfies only lexicoraphically largest anagram of s is greater than lexicoraphically largest anagram of P.
To solve this problem we use two pointer method.
We store the frquency of characters of P in hash table hash1.
We use two pointers i( forward pointer ) and j( backward pointer ).
Let length of S be n.
To traverse S we update hash table hash2 by increasing frequency of S[i] by 1.
Then while we satisfy the above condition we increase j, increase answer by n-i and decrease frequency of S[j];
We do this for i=0 to i=n-1.
Time complexity: O(N) where N is length of string S.
Code
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;
main()
{
string s,p;
cin>>s>>p;
int n=s.size(),m=p.size();
vector<int> tmp(26),hash(26);
for(int i=0;i<m;i++)
tmp[p[i]-'a']++;
ll ans=0;
int i=0,j=0;
while(i<n && j<n)
{
hash[s[i]-'a']++;
int flag=0,k=25;
for(;k>=0;k--)
{
if(hash[k]>tmp[k])
{
flag=1;
break;
}
else if(hash[k]<tmp[k])
break;
}
if(!flag)
{
i++;
continue;
}
flag=1;
while(flag)
{
ans=(ans+(n-i))%MOD;
hash[s[j]-'a']--;
k=25;
for(;k>=0;k--)
{
if(hash[k]>tmp[k])
{
break;
}
else if(hash[k]<tmp[k])
{
flag=0;
break;
}
}
j++;
}
i++;
}
cout<<ans<<endl;
}
DECOCHIP
If width of any chip is grater than L, we return -1;
For each combination of the chips we can calculate the number of holders it requires and their answer in dp table.
To generate each combination we can use bit mask from 1 to 2^N-1;
For each combination C we need to check if sum of widths of any subset S of C is less than or equal to W.
If the condition exists we can update dp[C]=min(dp[C], dp[C^S] + 1).
We return dp[2^N-1].
Time complexity: O(N*3^N)
PS: Sorry for the weak test cases.
Code
#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
using namespace std;
using ll=long long;
main()
{
IO;
ll t,n,w;
cin>>t;
while(t--)
{
cin>>n>>w;
vector<ll> v(n);
for(int i=0;i<n;i++)
cin>>v[i];
vector<ll> dp(1<<n, 1e9);
dp[0]=0;
for(ll i=1;i<(1<<n);i++)
{
vector<ll> bits;
for(ll j=0;j<n;j++)
{
if((1<<j)&i)
bits.push_back(j);
}
for(ll j=1;j<(1<<bits.size());j++)
{
ll mask=0, sum=0;
for(ll l=0;l<bits.size();l++)
{
if((1<<l)&j)
{
mask|=(1<<bits[l]);
sum+=v[bits[l]];
if(sum>w)
break;
}
}
if(sum<=w)
dp[i]=min(dp[i], dp[i^mask]+1);
}
}
if(dp[(1<<n)-1]!=1e9)
cout<<dp[(1<<n)-1]<<"\n";
else
cout<<-1<<"\n";
}
}
DECOEVIL
First step is coordinate compression, observe that the number of sequences remains same as before the coordinate compression.
Now the problem can be solved using two fenwick tree. Let’s maintain a fenwick tree greater which stores the number of subsequences ending at the current value such that the current element is a hill similarly another fenwick tree lesser which stores the number of subsequences ending at that current value such that the current element is a valley. For each position we can add the number of subsequences created by the current element and update
greater = 1 + all subsequences in lesser smaller than current value and,
lesser = 1 + all subsequences in greater larger than current value.
Note: Modulo operations are costly so remember to use addition/substraction operations(for taking modulo) in fenwick tree as well as calculation of answer.
Time complexity: O(N log N) per test case.
Code
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
vector<int> compress(vector<int> &org){//coordinate compression
int n = org.size();
vector<int> aux = org;
map<int, int> mp;
sort(aux.begin(), aux.end());
for(int i = 0; i < n; i++){
mp[aux[i]] = i + 1;
}
for(int i = 0; i < n; i++){
org[i] = mp[org[i]];
}
return org;
}
int get(vector<int>&v, int idx)
{
int ans = 0;
while(idx >= 0)
{
ans += v[idx];
if(ans >= mod)
ans -= mod;
idx = (idx & (idx+1)) - 1;
}
return ans;
}
void upd(vector<int>&v, int idx, int val)
{
while(idx < v.size())
{
v[idx] += val;
if(v[idx] >= mod)
v[idx] -= mod;
idx |= (idx + 1);
}
}
int solve(int n, vector<int> &arr){
arr = compress(arr);//coordinate compression
vector<int> lesser(n + 1), greater(n + 1);//fenwick trees
int ans = 0;
for(int i = 0; i < n; i++){
int less_than_curr = get(lesser, arr[i] - 1) + 1;
ans += less_than_curr - 1;//add current element as hill
if(ans >= mod)
ans -= mod;
int more_than_curr = get(greater, n) - get(greater, arr[i]) + 1;
if(more_than_curr < 0)
more_than_curr += mod;
ans += more_than_curr - 1;//add current element as valley
if(ans >= mod)
ans -= mod;
upd(lesser, arr[i], more_than_curr);//update lesser
upd(greater, arr[i], less_than_curr);//update greater
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> arr(n);
for(int i = 0; i < n; i++)
cin >> arr[i];
cout << solve(n, arr) << "\n";
}
}
DECOHOLE
We can model the given problem in a graph problem. In which each point is a node and each wormhole is an edge connecting two nodes with two parameters, length and time. Each edge has length 1 but time varies (u v t). So the minimum time is equal to sum of time on edges travelled during journey. Note that edges can repeat (i.e. path is not simple). We apply normal dijkstra on length to obtain distance of each node from Black hole (point 1). Then we apply modified dijkstra from node S, having a state of 3 parameters, (cur, kused, parity) where cur = last taken node in travel, kused = restricted edges travelled till last node and parity = a boolean variable to check if have even or odd number of important elements. At last we just take minimum of all possible valid solutions to reach node E.
Time complexity: O(T * (N + M) * logN * K)
CODE
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2")
#define sync ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
#define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(0);
using pii = pair<int , int>;
int inline max(const int x, const int y){return (x > y ? x : y);}
int inline min(const int x, const int y){return (x < y ? x : y);}
int inline abs(const int x){return (x < 0 ? -x : x);}
int n, m, k, r, dLIMIT;
vector<int> dj(int s, vector<vector<pii>> g){
vector<int> d(n + 1, -1);
set<pii> st;
st.insert({0, s});
d[s] = 0;
while(st.size()){
pii dt = *st.begin();
st.erase(st.begin());
int cur = dt.se, nwd = dt.fi;
for (const pii& e : g[cur]){
int x = e.fi, nd = nwd + 1;
if (~d[x]){
if (nd < d[x]){
if (st.count({d[x], x})) st.erase({d[x], x});
d[x] = nd;
st.insert({nd, x});
}
}
else{
d[x] = nd;
st.insert({d[x], x});
}
}
}
for (int& x : d){
if (x == -1) x = 1e9;
}
return d;
}
struct State{
int cur, kused, parity;
State():cur(0), kused(0), parity(0){}
State(int x, int y, int z){
cur = x; kused = y; parity = z;
}
bool inline operator == (const State& s){
return (cur == s.cur && kused == s.kused && parity == s.parity);
}
};
bool inline operator < (const State& l , const State& s){
if (l.cur != s.cur) return (l.cur < s.cur);
if (l.kused != s.kused) return l.kused < s.kused;
return l.parity < s.parity;
}
ll mod_dj(int s, int e, vector<vector<pii>> g, vector<int> a, vector<int> take){
vector<vector<vector<ll>>> d(n + 1, vector<vector<ll>>(k + 1, vector<ll>(2, -1)));
vector<int> dt = dj(1, g);
set<pair<ll , State>> st;
st.insert({0, State(s, 0, take[a[s]])});
d[s][0][take[a[s]]] = 0;
while(st.size()){
auto data = *st.begin();
st.erase(st.begin());
ll nwd = data.fi;
int x, cur = data.se.cur, kused = data.se.kused, par = data.se.parity;
for (const pii& ed : g[cur]){
x = ed.fi;
State nsta(x, kused, par);
if (take[a[x]]) nsta.parity ^= 1;
if (dt[cur] <= dLIMIT && dt[x] <= dLIMIT) nsta.kused++;
if (nsta.kused > k) continue;
ll nd = nwd + ed.se;
if (~d[nsta.cur][nsta.kused][nsta.parity]){
if (nd < d[nsta.cur][nsta.kused][nsta.parity]){
if (st.find({d[nsta.cur][nsta.kused][nsta.parity], nsta}) != st.end()){
st.erase({d[nsta.cur][nsta.kused][nsta.parity], nsta});
}
d[nsta.cur][nsta.kused][nsta.parity] = nd;
st.insert({nd, nsta});
}
}
else{
d[nsta.cur][nsta.kused][nsta.parity] = nd;
st.insert({nd, nsta});
}
}
}
ll mn = 1e18;
for (int i = 0; i <= k; i++){
if (~d[e][i][0]){
mn = min(mn , d[e][i][0]);
}
}
return (mn == 1e18 ? -1 : mn);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
sync
int t = 1;
cin >> t;
for (int tc = 1; tc <= t; tc++){
cin >> n >> m >> k >> dLIMIT >> r;
vector<vector<pii>> g(n + 1);
for (int u, v, wt, i = 0; i < m; i++){
cin >> u >> v >> wt;
g[u].push_back({v, wt});
g[v].push_back({u, wt});
}
vector<int> a(n + 1), take(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int x, i = 1; i <= r; i++){
cin >> x;
take[x] = 1;
}
int u, v;
cin >> u >> v;
cout << mod_dj(u, v, g, a, take) << endl;
}
cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s ";
return 0;
}
DECORICK
First notice that if we prime factorize P then each prime has power atmost 1. Also, for the multiplication of prefix and suffix elements (after subarray removal) to be divisible by P, all primes that are divisor of P must be present in either prefix product or suffix product. So we first replace each a[i] with common primes between a[i] and P (because other primes are not important). Common primes can be found by prime factorizing gcd(a[i] , P) (we can precompute prime factors of numbers upto max(a[i]) using sieve). Then we iterate over each prefix (assuming this prefix is in our solution) and find the smallest suffix such that, product(prefix) * product(suffix) is divisible by P. One way is to use bitmask for each valid prime. We iterate over prefix and for each prefix we have a mask which has ith bit set if ith prime if in the prefix. Similarly, we will can store such suffix masks for each suffix. Then, for a particular prefix mask we need to find such a suffix mask such that, (prefix mask | suffix mask) has a set bit for every bit. We can use binary search or some other ways to find such suffix. If there is no valid answer, we print -1.
Time Complexity: O(Max(Ai) * log(Max(Ai)) + T * NlogN)
CODE
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2")
#define sync ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
#define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(0);
using pii = pair<int , int>;
int inline max(const int x, const int y){return (x > y ? x : y);}
int inline min(const int x, const int y){return (x < y ? x : y);}
int inline abs(const int x){return (x < 0 ? -x : x);}
const int mxn = 1e5 + 5;
bitset<mxn> p;
vector<vector<int>> sieve(){
p.set();
p[0] = p[1] = 0;
vector<vector<int>> pf(mxn);
for (int i = 2; i < mxn; i++){
if (p[i]){
for (int j = i; j < mxn; j += i){
p[j] = 0;
pf[j].push_back(i);
}
}
}
return pf;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
sync
int t = 1;
cin >> t;
vector<vector<int>> pf = sieve();
for (int tc = 1; tc <= t; tc++){
int n;
ll p;
cin >> n >> p;
vector<int> candi, a(n + 2);
for (int i = 1; i <= n; i++){
cin >> a[i];
for (int x : pf[__gcd((ll)a[i], p)]){
candi.push_back(x);
}
}
unq(candi);
ll chkp = 1;
map<int , int> mapa;
int ptr = 0;
for (int& x : candi){
chkp *= x;
mapa[x] = ptr++;
}
assert(candi.size() <= 16);
if (chkp != p){
cout << -1 << endl;
}
else{
int sz = candi.size();
vector<int> Q(n + 1, (1 << sz) - 1);
for (int msk = 0, i = 1; i <= n; i++){
for (int x : candi){
if (a[i] % x == 0){
msk |= (1 << mapa[x]);
}
}
Q[i] ^= msk;
}
int cnt = n;
vector<int> pos(sz, -1), dp(n + 1);
for (int msk = 0, i = n; i >= 1; i--){
for (int x : candi){
if (msk & (1 << mapa[x])) continue;
if (a[i] % x == 0){
msk |= (1 << mapa[x]);
pos[mapa[x]] = i;
}
}
dp[i] = msk;
if (!Q[i - 1]) cnt = i - 1;
for (int j = 0; j < sz; j++){
if (Q[i - 1] & (1 << j)){
if (pos[j] == -1) continue;
if ((dp[pos[j]] & Q[i - 1]) == Q[i - 1]){
cnt = min(cnt, i - 1 + (n - pos[j] + 1));
}
}
}
}
cout << cnt << endl;
}
}
cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s ";
return 0;
}
