Set and Editorial by: vntshh
You just have to find the number of elements greater than the minimum number occurring in the array and less than the maximum number occurring in the array. This can be done in O(n) by traversing the array once and finding the minimum and maximum of the array, and then in another traversal, find the good numbers.
Complexity: O(n)
Code#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n,c1=0,c2=0,mx=0,mn=1000000007;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
mx=max(mx,a[i]),mn=min(mn,a[i]);
}
for(int i=0;i<n;i++)
{
if(a[i]==mx) c1++;
if(a[i]==mn) c2++;
}
if(mx==mn) cout<<0;
else cout<<(n-c1-c2);
return 0;
}
Set and Editorial by: killer_bee
It is easy to see that the total number of elements in the final list will be . The problem can be solved by locating each element in the list and checking whether it is '1' .The ith element can be located in O(logn) by using Divide and Conquer strategy. Answer is the total number of all such elements which equal '1'.
Complexity : O((r - l + 1) * logn)
Code#include<bits/stdc++.h>
using namespace std;
long long int cnt(long long int temp) //returns the length of final list
{
long long int x=1;
while(temp>1)
{
temp/=2;
x*=2;
}
return x;
}
int is_one(long long int pos,long long int target,long long int num)
{
if(num<2)
return num;
if(pos+1==2*target)
{
return num%2;
}
num/=2;
pos/=2;
if(target>pos+1)
target-=(pos+1);
return is_one(pos,target,num);
}
int main()
{
long long int l,r,n,x,ans=0,i;
cin>>n>>l>>r;
x=cnt(n);
x=2*x-1;
for(i=l; i<=r; i++) ans+=is_one(x,i,n);
cout<<ans<<endl;
return 0;
}
Set and Editorial by: vntshh
The range of strengths of any ranger at any point of time can be [0,1023]. This allows us to maintain a frequency array of the strengths of the rangers. Now, the updation of the array can be done in the following way: Make a copy of the frequency array. If the number of rangers having strength less than a strength y is even, and there are freq[y] rangers having strength y, ceil(freq[y] / 2) rangers will be updated and will have strengths y^x, and the remaining will retain the same strength. If the number of rangers having strength less than a strength y is odd,and there are freq[y] rangers having strength y, floor(freq[y] / 2) rangers will be updated and will have strengths y^x, and remaining will have the same strength. This operation has to be done k times, thus the overall complexity is O(1024 * k).
Complexity: O(k * 210)
Code#include<bits/stdc++.h>
#define rep(i,start,lim) for(int i=start;i<lim;i++)
using namespace std;
#define N 100005
int freq[1100],tmp[1024];
int main()
{
int n,k,maxm=0,minm=INT_MAX,p,x;
cin>>n>>k>>x;
rep(i,0,n) cin>>p,freq[p]++;
rep(i,0,k)
{
rep(j,0,1024) tmp[j]=freq[j];
int par=0;
rep(j,0,1024)
{
if(freq[j]>0)
{
int curr = (j^x),change = (freq[j]/2);
if(par==0) change+=(freq[j]&1);
tmp[j]-=change;
tmp[curr]+=change;
par^=(freq[j]&1);
}
}
rep(j,0,1024) freq[j]=tmp[j];
}
rep(i,0,1024) if(freq[i]>0) minm=min(minm,i),maxm=max(maxm,i);
cout<<maxm<<" "<<minm;
return 0;
}
Set and Editorial by: arnabsamanta
This problem can be solve using inclusion-exclusion principle but precision errors need to be handled. Therefore, we use the following dynamic programming approach to solve this problem.
On n - th day there are two possibilities,
Case-1 : Jon doesn't find a new orb then the probability of it is .
Case-2 : Jon does find a new orb then the probability of it is .
Therefore,
We need to find the minimum n such that
where,
n = number of days Jon waited.
x = number of distinct orbs Jon have till now.
dp[n][x] = probability of Jon having x distinct orbs in n days.
k = Total number of distinct orbs possible.
Code#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
const double eps = 1e-7;
double dp[N];
int ans[N];
int main(){
int k, q, d = 1;
cin >> k >> q;
dp[0] = 1;
for(int n = 1; d <= 1000; ++n){
for(int x = k; x > 0; --x){
dp[x] = (x * dp[x] + (k - x + 1) * dp[x - 1]) / k;
}
while(d <= 1000 && 2000 * dp[k] >= (d - eps)){
ans[d] = n;
d++;
}
dp[0] = 0;
}
while(q--){
int x;
cin >> x;
cout << ans[x] << "\n";
}
}
PS:The ε was added so that the any solution considering the probability in the given range passes the system tests.
Set and Editorial by: AakashHanda
This problem can be solved using DP with Bitmasks to calculate the grundy value of piles. Let us have a 2-dimensional dp table, dp[i][j], where the first dimension is for number of stones in the pile and second dimension is for bitmask. The bitmask has k-th bit set if we are allowed to remove k + 1 stones from the pile.
Now, to calculate dp[i][j] we need to iterate over all possible moves allowed and find the mex.
Codedp[0][0] = 0;
for(i=1 ; i<N ; ++i){
for(j=0 ; j<(1<<N)-1 ; ++j){
vector<bool> found(N, false);
for(k=0 ; k<i ; ++k){
if(((j>>k)&1) != 1)
continue;
found[dp[i-k-1][j^(1<<k)]] = true;
}
for(k=0 ; k<N ; ++k){
if(!found[k]){
dp[i][j] = k;
break;
}
}
}
}
Finally for the game, we use the grundy values stored in dp[i][2i - 1] for a pile of size i. We take the xor of grundy values of all piles sizes. If it is 0, then Jon wins, otherwise Sam wins.
The complexity of this solution is . This will not be accepted. We can use the following optimizations for this problem:
- Use a top-down approach to calculate the values of dp[i][2i - 1], hence calculating only those values that are required.
- Since we can only remove at most i stones from a pile, as stated above, we need to store values from j in range [0, 2i - 1].
So we can rewrite the above code to incorporate these change. Hence, the final solution is as follows
Code#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<pair<int, ll>, int> grundy;
map<pair<int, ll>, bool> mp;
int retgrundy(int ps, ll bm, int prev = 63){
for(int i=ps ; i<prev ; ++i){
if(((bm>>i)&1LL) == 1LL)
bm ^= (1LL<<i);
}
if(mp[{ps, bm}])
return grundy[{ps, bm}];
vector<bool> marked(63, false);
for(int k=0 ; k<ps ; ++k){
if(((bm>>k)&1LL) == 0)
continue;
marked[retgrundy(ps-k-1LL, (bm^(1LL<<k)), ps)] = true;
}
int ret;
for(int i=0 ; i<63 ; ++i){
if(marked[i])
continue;
grundy[{ps, bm}] = i;
ret = i;
break;
}
mp[{ps, bm}] = true;
return ret;
}
int main(){
int n, in, x=0;
scanf("%d", &n);
grundy[{0, 0}] = 0;
mp[{0, 0}] = true;
vector<int> gr(70, 0);
for(int i=0 ; i<=60 ; ++i)
gr[i] = retgrundy(i, (1LL<<i)-1LL);
while(n--){
scanf("%d", &in);
x ^= gr[in];
}
if(x == 0)
printf("YES");
else
printf("NO");
}
Bonus: Try to find and prove the O(1) formula for grundy values
Set and Editorial by: arnabsamanta, apoorv_kulsh
Every arrangement of stacks can expressed in the form of linear arrangement. In this linear arrangement, every contiguous segment of wine barrels are separated by food boxes. For the arrangement to be liked by Jon each of the f + 1 partitions created by f food boxes must contain either 0 or greater than h wine barrels.
Let u out of f + 1 partitions have non-zero wine barrels then the remaining r + 1 - u partitions must have 0 wine barrels..
Total number of arrangements with exactly u stacks of wine barrels are
is the number of ways of choosing u partitions out of f + 1 partitions.
X is the number of ways to place w wine barrels in these u partitions which is equal to the coefficient of xw in {xh + 1·(1 + x + ...)}u. Finally we sum it up for all u from 1 to f + 1.
So the time complexity becomes O(w) with pre-processing of factorials.
w = 0 was the corner case for which the answer was 1.
We did not anticipate it will cause so much trouble. Not placing it in the pretests was a rookie mistake.
Code#include <bits/stdc++.h>
using namespace std;
const int N = 212345;
const int mod = 1000000007;
int fac[N], ifac[N], inv[N];
void prep(){
fac[0] = ifac[0] = inv[1] = 1;
for(int i = 1; i < N; ++i)
fac[i] = 1LL * i * fac[i - 1] % mod;
for(int i = 2; i < N; ++i)
inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
for(int i = 1; i < N; ++i)
ifac[i] = 1LL * inv[i] * ifac[i - 1] % mod;
}
int C(int n, int r){
if(r < 0 || n < r) return 0;
return 1LL * fac[n] * ifac[n - r] % mod * ifac[r] % mod;
}
int num(int r, int b, int k){
if(b == 0) return 1;
int ans = 0;
for(int u = 1; u <= r + 1 && (k == 0 || u <= (b - 1) / k); ++u){
ans += 1LL * C(r + 1,u) * C(b - k * u - 1, u - 1) % mod;
ans %= mod;
}
return ans;
}
int pwr(int b, int p){
int r = 1;
while(p){
if(p & 1) r = 1LL * r * b % mod;
b = 1LL * b * b % mod;
p >>= 1;
}
return r;
}
int finv(int x){
return pwr(x, mod - 2);
}
int main(){
prep();
int f, w, h;
cin >> f >> w >> h;
int sn = num(f, w, h);
int sd = C(f + w, w);
cout << 1LL * sn * finv(sd) % mod << "\n";
}
Set and Editorial by: apoorv_kulsh
We are given a tree. We remove one node from this tree to form a forest. Strength of forest is defined as the size of largest tree in forest. We need to minimize the strength by changing the parent of atmost one node to some other node such that number of components remain same.
To find the minimum value of strength we do a binary search on strength. It is possible to attain Strength S if
1. There is less than one component with size greater than S.
2. There exists a node in maximum component with subtree size Y such that,
M - Y ≤ S (Here M is size of maximum component and m is size of minimum component)
m + Y ≤ S.
Then we can change the parent of this node to some node in smallest component.
The problem now is to store Subtree_size of all nodes in the maximum component and perform binary search on them. We can use Stl Map for this.
Let X be the node which is removed and Xsize be its subtree size There are two cases now -:
1. When max size tree is child of X.
2. When max size tree is the tree which remains when we remove subtree of X from original tree.(We refer to this as outer tree of X).
In the second case the subtree sizes of nodes on path from root to X will change when X is removed. Infact their subtree size will decrease exactly by Xsize. While performing binary search on these nodes there will be an offset of Xsize. So we store them seperately. Now we need to maintain 3 Maps,
where
mapchildren : Stores the Subtree_size of all nodes present in heaviest child of X.
mapparent : Stores the Subtree_size of all nodes on the path from root to X.
mapouter : Stores the Subtree_size of all nodes in outer tree which are not on path from root to X.
Go through this blog post before reading further (http://codeforces.com/blog/entry/44351).
Maintaining the Maps
mapchildren and mapparent are initialised to empty while mapouter contains Subtree_size of all nodes in the tree.
mapparent : This can be easily maintained by inserting the Subtree_size of node in map when we enter a node in dfs and remove it when we exit it.
mapchildren : mapchildren can be maintained by using the dsu on tree trick mentioned in blogpost.
mapouter : When we insert a node's subtree_size in mapchildern or mapparent we can remove the same from mapouter and similarly when we insert a node's Subtree_size in mapchildern or mapparent we can remove the same from mapouter.
Refer to HLD style implementation in blogpost for easiest way of maintaining mapouter.
Refer to code below for exact point of insertions and deletions into above mentioned 3 maps.
Code#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> adj[N];
int sz[N], ans[N];
int n, root;
bool big[N];
map<int,int> mp, mpo, par;
void getsz(int s){
sz[s] = 1;
ans[s] = n - 1;
for(auto it : adj[s]){
getsz(it);
sz[s] += sz[it];
}
mpo[sz[s]]++;
}
void bs(map<int, int> &mp1, int l, int r, int mi, int s, int off){
if(mi == n - 1) return;
int ma = r;
while(r - l > 1){
int mid = (r + l) / 2;
auto it = mp1.lower_bound(ma - mid + off);
if(it == mp1.end())
l = mid;
else if(mi + it->first <= mid + off)
r = mid;
else
l = mid;
}
ans[s] = min(ans[s], r);
}
void add(int s){
mp[sz[s]]++;
if(mpo[sz[s]] == 1)
mpo.erase(sz[s]);
else
mpo[sz[s]]--;
for(auto it:adj[s])
if(!big[it]) add(it);
}
void rem(int s){
mpo[sz[s]]++;
if(mp[sz[s]] == 1)
mp.erase(sz[s]);
else
mp[sz[s]]--;
for(auto it:adj[s])
if(!big[it]) rem(it);
}
void dfs(int s, bool isbig){
par[sz[s]]++;
if(mpo[sz[s]] == 1)
mpo.erase(sz[s]);
else
mpo[sz[s]]--;
int ma = -1, sma = -1, mac = -1, mi = n - 1;
for(auto it:adj[s]){
if(sz[it]>ma){
sma = ma;
ma = sz[it];
mac = it;
}
else if(sz[it]==ma)
sma = ma;
else
sma = max(sma,sz[it]);
mi = min(mi,sz[it]);
}
if(s != root)
mi = min(mi,n-sz[s]);
for(auto it:adj[s]){
if(it!=mac)
dfs(it,0);
}
if(mac != -1){
big[mac]=true;
dfs(mac,1);
}
if(ma >= n - sz[s]){
sma = max(sma, n - sz[s]);
bs(mp, sma - 1, ma, mi, s, 0);
}
mpo[sz[s]]++;
add(s);
if(par[sz[s]] == 1)
par.erase(sz[s]);
else
par[sz[s]]--;
if(n-sz[s] > ma){
sma = ma;
bs(mpo, sma - 1, n - sz[s], mi, s, 0);
bs(par, sma - 1, n - sz[s], mi, s, sz[s]);
}
if(mac != -1)
big[mac] = false;
if(!isbig) rem(s);
}
int main(){
int i, u, v;
scanf("%d", &n);
for(i = 0; i < n; ++i){
scanf("%d%d", &u ,&v);
if(u == 0) root = v - 1;
else
adj[u - 1].push_back(v - 1);
}
getsz(root);
dfs(root, 1);
for(i = 0; i < n; ++i)
printf("%d\n", ans[i]);
}
Complexity O(NlogN2)