Idea:Yugandhar_Master
Let's handle each two lines separately. We greedily place kings in all the white squares in the first row. Then, we cannot place kings in the second row.
Overall, the answer is $$$\lfloor \frac{n+1}{2} \rfloor \cdot \lfloor \frac{m+1}{2} \rfloor$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
cout<<((n+1)/2)*((m+1)/2)<<"\n";
}
}
Idea:beyondpluto
First let's assign a number to each sector from $$$1$$$ to $$$n$$$ in clockwise order.
One obvious construction is to move all cones to sector $$$1$$$ as follows:
i) move cones at sector $$$2$$$ and $$$n$$$ to sector $$$1$$$, by moving both of them one unit towards sector $$$1$$$ at each operation.
ii) move cones at sector $$$3$$$ and $$$n-1$$$ to sector $$$1$$$ in same way.
iii) move cones at sector $$$4$$$ and $$$n-2$$$ to $$$1$$$ in same way.
So on.
It takes $$$\frac{\frac{n}{2}.\big(\frac{n}{2}+1\big)}{2}$$$ ops. And it is minimum possible.
Consider parity of sum of sector numbers where cones are currently present. (with repeated count for multiple cones in same sector).
It is invariant in given operation. ie: it's parity doesn't change over any operation.
Our final state is something where all cones present in one same sector. And it's parity is always even as $$$n$$$ is even. So, if parity of the initial state and final state are not same, then it's impossible to move to the final state from the initial state. And initial state parity is the parity of $$$1+2+3....+n = \frac{n \cdot (n+1)}{2}$$$ or just parity of $$$\frac{n}{2}$$$ as $$$n$$$ is already even.
So, it's impossible when the parity of $$$\frac{n}{2}$$$ is odd. Otherwise, it's always possible with the following construction for minimum possible operation:
Let's assume we want to move all cones to sector $$$1$$$.
Always choose the top two cones that are farthest away from sector $$$1$$$ and move them towards sector $$$1$$$. On each of this operation, the total sum of distance of all cones from sector $$$1$$$ is decreased by two (which is maximum possible in one operation).
Initially total sum of distance is even (when $$$\frac{n}{2}$$$ is even) and it can be shown that our final operation will be with two different cones.
Notice that, after each of our operation, the distance between first farthest cone and second farthest cone doesn't go beyond one.
So, the minimum number of operations would be sum of initial (shortest) distance of all cones from sector $$$1$$$, divided by two.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
if(n%2==0){
if((n/2)%2==1) cout<<"-1\n";
else{
ll x=(n/2);
cout<<(x*(x+1))/2-(n/4)<<"\n";
}
}
else{
ll x=(n-1)/2;
cout<<(x*(x+1))/2<<"\n";
}
}
}
Idea:Yugandhar_Master
Root the tree at a node, say $$$1$$$. Now, calculate depths of all nodes from the root, and mark all nodes with even depth as $$$0$$$, and odd depth as $$$1$$$. Imagine we connect two nodes of the different parity. This would form a cycle of even length and so the diametrically opposite vertices on the cycle would violate the condition.
So, we are left with choices where we connect vertices of the same parity. This will always satisfy our conditions.
This is because precisely $$$1$$$ cycle is formed, with trees dangling to it. For 2 vertices on the cycle, there are never 2 shortest paths since total cycle length is odd. The trees hanging to the cycle trivially satisfy the condition.
Also since the path between two attached trees also goes through the cycle, it essentially reduces to shortest path between corresponding points on the cycle and is also unique.
So our answer is all pairs of nodes having the same parity. Complexity is $$$O(n)$$$.
#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
vector<int> v[1000010];
bool ch[1000010];
ll cnt1,cnt0;
void DFS(int po,bool c){
if(!c) cnt0++;
else cnt1++;
ch[po]=1;
for(auto i:v[po]){
if(!ch[i]){
DFS(i,!c);
}
}
return;
}
void solve(){
int n,a,b;
cnt1=0;
cnt0=0;
cin>>n;
for(int i=1;i<=n;i++){
v[i].clear();
ch[i]=0;
}
for(int i=1;i<n;i++){
cin>>a>>b;
v[a].eb(b);
v[b].eb(a);
}
DFS(1,0);
cout<<(((cnt1-1)*cnt1)/2)+(((cnt0-1)*cnt0)/2)<<'\n';
return;
}
int main(){
iofast
int t;
cin>>t;
w(t) solve();
return 0;
}
Idea:wuhudsm
Preparer:PROELECTRO444
We can observe that the upper bound of the answer is $$$\frac{n(n+1)}{2}$$$(corresponding to $$$[0,1,...,n-1]$$$) and the lower bound is $$$n$$$(corresponding to $$$[n-1,n-2,...,1,0]$$$).
In fact, we construct the permutation for all $$$n \le S \le \frac{n(n+1)}{2}$$$. Note $$$x$$$ as the maximum number such that $$$x+(x+1)+(x+2)+...+n \ge S$$$, we have $$$S=y+(x+1)+(x+2)+...+n(y \le x)$$$.
If $$$y \neq x$$$, we get $$$p=[1,...,y-1,y+1,...,0,y,x+1,x+2,...,n]$$$;
Otherwise, we get $$$p=[1,2,...,...,x-1,0,x,x+1,x+2,...,n]$$$;
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
if(k<n || k>(n*(n+1))/2) cout<<"-1\n";
else{
if(k==n){
for(ll i=1;i<n;i++) cout<<i<<" ";
cout<<0<<"\n";
}
else if(k==(n*(n+1))/2){
for(ll i=0;i<n;i++) cout<<i<<" ";
cout<<"\n";
}
else{
k-=n;
vector<ll> ans(n);
ll val=0,ind=0,ind1=0;
for(ll i=0;i<n;i++) ans[i]=i;
for(ll i=n-1;i>0;i--){
if(k>i) k-=i;
else{
swap(ans[i-1],ans[0]);
val=k;
ind=i;
break;
}
}
for(ll i=0;i<n;i++){
if(ans[i]==val){
ind1=i;
break;
}
}
swap(ans[ind],ans[ind1]);
for(auto i:ans) cout<<i<<" ";
cout<<"\n";
}
}
}
}
Idea:HexShift
Reimagine the integers in $$$a$$$ as binary integers. Since XOR operation is done before any addition, this means that we can count the contribution of each bit separately, because XOR operation can be done by doing the XOR operation for each bit, and addition can also be done in a similar way.
Let $$$s_k$$$ be the sum of costs from all $$$2^{n-1}$$$ possible expressions if we only consider the $$$k$$$-th bit from each integer as the elements. Then, the sum of costs is $$$\sum_{i=0}^{28} s_i \cdot 2^i$$$.
Let's try to count $$$s_0$$$. We will use dynamic programming to solve this. Let $$$dp_i$$$ be the sum of costs from all $$$2^{i-1}$$$ possible expressions if we only consider the $$$0$$$-th bit from each integer as the elements, and we only consider the first $$$i$$$ elements. Let the $$$0$$$-th bit of $$$a_i$$$ be $$$b_i$$$. Then, $$$dp_0 = 0$$$ and $$$dp_i = \sum_{x=0}^{i-1} (dp_x + (b_{x+1} \oplus b_{x+2} \oplus \dots \oplus b_i))$$$. Although doing this naively would result in $$$O(n^3)$$$ transition, we can optimize this to $$$O(n)$$$ using prefix sum.
Let $$$pdp_i = \sum_{x=0}^{i} dp_x$$$ and $$$pb_i = b_1 \oplus b_2 \oplus \dots \oplus b_i$$$. Then, $$$dp_i = pdp_{i-1} + \sum_{x=0}^{i-1} (pb_x \oplus pb_i)$$$. Notice that the second expression is still $$$O(n)$$$. So, to count it in $$$O(1)$$$, we just have to store two extra variables $$$c_{i,0}$$$ and $$$c_{i,1}$$$, where $$$c_{i,k}$$$ is the number of integers $$$x$$$ such that $$$1 \leq x \leq i$$$ and $$$pb_x = k$$$. If $$$pb_i = 0$$$, the second expression is equal to $$$c_{i,1}$$$. Otherwise, the second expression is equal to $$$c_{i,0}$$$.
Other values of $$$s_i$$$ can be counted in a similar way.
Time complexity: $$$O(n \log a_i)$$$
// #pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pob pop_back
const int MOD = 1e9 + 7;
const int MODD = 998244353;
const int MAXN = 5e5 + 2;
const ll BIGG = 2e18;
using namespace std;
int a[MAXN];
ll dp[MAXN], cnt[2], pref[MAXN];
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
ll res = 0, comb;
bool od;
for (int i = 0; i < 29; i++) {
od = true;
cnt[0] = 0;
cnt[1] = 1;
comb = 1;
if (a[0] % 2) {
dp[0] = 1;
pref[0] = 1;
od = !od;
}
else {
dp[0] = 0;
pref[0] = 0;
}
a[0] >>= 1;
cnt[od]++;
for (int i = 1; i < n; i++) {
comb = (comb * 2) % MODD;
if (a[i] % 2) od = !od;
a[i] >>= 1;
dp[i] = (pref[i - 1] + cnt[!od]) % MODD;
pref[i] = (pref[i - 1] + dp[i]) % MODD;
cnt[od] = (cnt[od] + comb) % MODD;
}
res = (res + dp[n - 1] * (1 << i)) % MODD;
}
cout << res << endl;
}
int main(){
// ios_base::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Idea:Yugandhar_Master
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
ll mod=1e9+7;
long long power(long long a,long long b){
long long x=1,y=a;
while(b>0){
if(b&1ll){
x=(x*y)%mod;
}
y=(y*y)%mod;
b>>=1;
}
return x%mod;
}
long long modular_inverse(long long n){
return power(n,mod-2);
}
#define MAXN 2000005
long long factorial[MAXN];
long long invfact[MAXN];
void cfact(){
long long i;
factorial[0]=1;
factorial[1]=1;
for(i=2;i<MAXN;i++){
factorial[i]=factorial[i-1]*i;
factorial[i]%=mod;
}
invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
for(i=MAXN-2;i>=0;i--){
invfact[i]=invfact[i+1]*(i+1);
invfact[i]%=mod;
}
}
long long calcnCr(long long n,long long k){
if(k<0 || n<k){return 0;}
return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}
int main(){
fast;
cfact();
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
string s1,s2;
cin>>s1>>s2;
ll cnt11=count(s1.begin(),s1.end(),'1');
ll cnt20=count(s2.begin(),s2.end(),'0');
if(cnt11>0 && cnt20>0) cout<<"0\n";
else if(cnt11==0 && cnt20>0) cout<<power((power(2,n)-1)%mod,n-cnt20)%mod<<"\n";
else if(cnt11>0 && cnt20==0) cout<<power((power(2,n)-1)%mod,n-cnt11)%mod<<"\n";
else{
ll res=0;
for(ll i=0;i<n;i++){
if(i%2==0){
res=(res-((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod+mod)%mod;
}
else{
res=(res+((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod)%mod;
}
}
cout<<(power(2,n*n)+2*res)%mod<<"\n";
}
}
}
Idea:vikram108
WLOG, assume that $$$x \geq y$$$. We desire for Alice to win. Let us check the scenarios where this is possible:
Case 1: $$$(x \geq 2y)$$$: This means Alice has to subtract a multiple of $$$y$$$ from $$$x$$$. There are, say $$$k$$$ choices of subtracting $$$y, 2y, .., ky$$$. We have more than $$$1$$$ choices $$$(k>1)$$$. If $$$ky$$$ is winning, Alice chooses that. If it is losing, then since $$$k>1$$$, Alice can choose $$$(k-1)y$$$ and Bob will then be forces to subtract $$$y$$$ in the next move, essentially making Bob choose the losing $$$ky$$$ state. So Alice always wins.
Case 2: $$$(x<2y)$$$: This means there is only one possible move, which is to subtract $$$y$$$ from $$$x$$$. If the resulting pair of numbers $$$(y,x-y)$$$ is losing, Alice wins. Else she loses.
Now, for her to loose, like in case 1, $$$(y \geq 2(x-y))$$$ (we already know $$$y$$$ is larger than $$$(x-y)$$$ since $$$x<2y$$$). So for her to win, $$$y \leq 2(x-y)$$$, which means $$$x \geq \frac{3y}{2}$$$.
If $$$y<2(x-y)$$$, we again subtract and go to the next iteration. The new pair is $$$(x-y,2y-x)$$$. For it the winning conditions come out to be $$$x \geq \frac{5y}{3}$$$.
If we keep doing the iterations, we observe that in the $$$n^{th}$$$ step the condition comes out to be $$$x \geq \frac{F(n+1)}{F(n)}$$$ where $$$F(n)$$$ is the $$$n^{th}$$$ Fibonacci number $$$(F(1)=1, F(2)=2)$$$. So, to get the exact bound, we take its limit as $$$n$$$ approaches infinity, and get $$$\lim_{n \to \infty} \frac{F(n+1)}{F(n)} = \frac{1+\sqrt{5}}{2} = \phi$$$. So Alice wins iff $$$(x> \phi y)$$$ (equality dropped since both $$$x$$$ and $$$y$$$ are integers).
So our problem becomes counting the number of $$$(l,r)$$$ such that $$$r> \phi l$$$. Since our numbers $$$\leq 10^9$$$, we can take an appropriate approximation of $$$\phi$$$, (say $$$\frac{p}{q}$$$).
Now our problem boils down to calculating $$$\sum_{x=L'}^{R} \lfloor \frac{xq}{p} \rfloor$$$ (here $$$L'$$$ is the first index such that $$$\lfloor \frac{L'q}{p} \rfloor \geq L $$$).
This is a standard problem and can be calculated in $$$O(log(max(p,q))$$$ complexity. Here is reference a blog with exact details about solving this: https://www.cnblogs.com/apjifengc/p/17492207.html
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll P = 1e18;
const ld phi=1.61803398874989;
const ll a=1134903170, b=0, c=1836311903;
//code for euclidean algo from blog mentioned in the editorial
struct Node {
ll x, y, sumx, sumy;
Node() : x(0), y(0), sumx(0), sumy(0) {}
Node operator*(Node b) {
Node a = *this, c;
c.x = (a.x + b.x) % P;
c.y = (a.y + b.y) % P;
c.sumx = (a.sumx + b.sumx + a.x * b.x) % P;
c.sumy = (a.sumy + b.sumy + a.y * b.x) % P;
return c;
}
};
Node pow(Node a, ll b) {
Node ans;
while (b) {
if (b & 1ll) ans = ans * a;
a = a * a;
b >>= 1ll;
}
return ans;
}
Node euclid(ll p, ll q, ll r, ll n, Node U, Node R) {
if (!n) return Node();
if (r >= q) return pow(U, r / q) * euclid(p, q, r % q, n, U, R);
if (p >= q) return euclid(p % q, q, r, n, U, pow(U, p / q) * R);
ll m = (1ll * p * n + r) / q;
if (!m) return pow(R, n);
return pow(R, (q - r - 1) / p) * U * euclid(q, p, (q - r - 1) % p, m - 1, R, U) * pow(R, n - (q * m - r - 1) / p);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Node U, R;
U.y = 1, R.x = 1, R.sumx = 1;
int t;cin>>t;while (t--){
ll l, r;cin>>l>>r;
ll sp=ceil(phi*l);
ll fa=(r-l+1)%P;
if (sp<=r){
ll ne=r-sp+1;
fa=(fa-((ne*(l-1))%P)+4*P)%P;
auto ans_r = euclid(a, c, b, r, U, R);
ans_r.sumy = (ans_r.sumy + (b / c)) % P;
auto ans_sp = euclid(a, c, b, sp-1, U, R);
ans_sp.sumy = (ans_sp.sumy + (b / c)) % P;
fa=(fa+ans_r.sumy-ans_sp.sumy+5*P)%P;
}
cout<<fa<<endl;
}
return 0;
}