Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

768A. Oath of the Night's Watch

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;
}

768B. Code For 1

Set and Editorial by: killer_bee

It is easy to see that the total number of elements in the final list will be $\text{[math]}$ . The problem can be solved by locating each element in the list and checking whether it is '1' .The i^th 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;
}

768C. Jon Snow and his Favourite Number

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 * 2¹⁰)

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;
}

768D. Jon and Orbs

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 $\text{[math]}$ .
Case-2 : Jon does find a new orb then the probability of it is $\text{[math]}$ .

Therefore, $\text{[math]}$
We need to find the minimum n such that $\text{[math]}$
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 $\text{[math]}$ passes the system tests.

768E. Game of Stones

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.

Code

dp[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][2ⁱ - 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 $\text{[math]}$ . 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][2ⁱ - 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, 2ⁱ - 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

768F. Barrels and boxes

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 $\text{[math]}$
$\text{[math]}$ 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 x^w in {x^h + 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";
}

768G. The Winds of Winter

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 X_size 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 X_size. While performing binary search on these nodes there will be an offset of X_size. So we store them seperately. Now we need to maintain 3 Maps,
where
map_children : Stores the Subtree_size of all nodes present in heaviest child of X.
map_parent : Stores the Subtree_size of all nodes on the path from root to X.
map_outer : 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://mirror.codeforces.com/blog/entry/44351).

Maintaining the Maps
map_children and map_parent are initialised to empty while map_outer contains Subtree_size of all nodes in the tree.

map_parent : 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.
map_children : map_children can be maintained by using the dsu on tree trick mentioned in blogpost.
map_outer : When we insert a node's subtree_size in map_childern or map_parent we can remove the same from map_outer and similarly when we insert a node's Subtree_size in map_childern or map_parent we can remove the same from map_outer.

Refer to HLD style implementation in blogpost for easiest way of maintaining map_outer.
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(NlogN²)

Full text and comments »