PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author & Editorialist: Jay Sharma
Tester: Yash Daga
DIFFICULTY:
TBD
PREREQUISITES:
Combinatorics
PROBLEM:
You are given a N\times N chessboard. Calculate two things -
- The minimum number of pawns that need to be placed on the board so that they attack every square on the board except the squares on the first rank.
- The number of ways to arrange these pawns in order to achieve the goal modulo 10^9+7.
QUICK EXPLANATION:
This is a casework problem. The following four cases arise -
| N\bmod 4 | Number of pawns needed | Number of ways of arranging them |
|---|---|---|
| 0 | (N-1)\times \frac{N}{2} | 1 |
| 1 | (N-1)\times \frac{N+1}{2} | (\frac{N-1}{4})^{N-1} |
| 2 | (N-1)\times \frac{N+2}{2} | (\frac{N+2}{4})^{2(N-1)} |
| 3 | (N-1)\times \frac{N+1}{2} | (\frac{N+5}{4})^{N-1} |
EXPLANATION:
First, notice that a pawn on the i^{th} rank can only attack the squares on the (i+1)^{th} rank. So, the arrangement of pawns in one rank cannot affect the arrangement in any other rank. Hence, the arrangement of pawns in different ranks are independent of each other and we can simply solve the problem for a single rank and then raise it to the power N-1 to get the answer for the whole board.
Second, note that a pawn can attack at most two squares having the same color as the square in which the pawn is placed. So, pawns placed on different colored squares are also independent of each other. This leads to the following 4 cases -
-
N\bmod 4 = 0 : In this case, each rank has \frac{N}{2} light squares and \frac{N}{2} dark squares. So, we need at least \frac{N}{4} pawns to attack the light squares and at least \frac{N}{4} pawns to attack the dark squares. It turns out by construction that these many pawns are sufficient.
It is also not hard to see that there is only 1 way to arrange them so that they attack all squares on the next rank. So, the second answer is simply 1.
The following figure shows the arrangement for a single rank of an 8\times 8 board -
-
N\bmod 4=1 : Without loss of generality, let’s assume that there are \frac{N+1}{2} light squares and \frac{N-1}{2} dark squares in the rank we want to attack. Since N\bmod 4=1, there are an odd number of light squares and an even number of dark squares.
For the pawns attacking the dark squares, there must be \frac{N-1}{4} such pawns and they can be placed in 1 way only.
However, for the pawns attacking the light squares, there must be \frac{N+3}{4} such pawns and there are multiple ways to arrange these pawns. It is not hard to see that all pair of consecutive pawns attacking the light squares must be placed at a distance of 4 files from each other except exactly one pair of pawns which must be placed at a distance of 2 from each other. There are \frac{N+3}{4}-1=\frac{N-1}{4} choices for the pair.
So, the total number of arrangements for a single rank is \frac{N-1}{4}. The total number of arrangements is (\frac{N-1}{4})^{N-1}.
The following are the 2 possible arrangements for a single rank of a 9\times 9 chessboard -
-
N\bmod 4=2 : There are \frac{N}{2} light squares and \frac{N}{2} dark squares in the rank we want to attack. Since N\bmod 4=2, there are an odd number of light squares and an odd number of dark squares. We need \frac{N+2}{4} pawns to attack squares of each type.
This time, all the pair of consecutive pawns attacking the light squares can be placed at a distance of 4 from each other except at most one pair of pawns which can be placed at a distance of 2 from each other. Same is true for the set of pawns attacking the dark squares. So, there are \frac{N+2}{4} ways to arrange each of these set of pawns (there is 1 way in which no pair of consecutive pawns is at a distance of 2 from each other and \frac{N+2}{4}-1 ways in which exactly one pair of consecutive pawns is at a distance of 2 from each other).
So, the total number of arrangements for a single rank is (\frac{N+2}{4})^2. The total number of arrangements for the board is (\frac{N+2}{4})^{2(N-1)}.
The following are the 9 possible arrangements for a single rank of a 10\times 10 chessboard -
-
N\bmod 4=3 : Without loss of generality, let’s assume that there are \frac{N+1}{2} light squares and \frac{N-1}{2} dark squares in the rank we want to attack. Since N\bmod 4=3, there are an even number of light squares and an odd number of dark squares.
For the pawns attacking the light squares, there must be \frac{N+1}{4} such pawns and they can be placed in 1 way only.
However, for the pawns attacking the dark cells, there must be \frac{N+1}{4} such pawns and they can be arranged in \frac{N+1}{4}+1 = \frac{N+5}{4} ways (there are 2 ways in which no pair of consecutive pawns is at a distance of 2 from each other and \frac{N+1}{4}-1 ways in which exactly one pair of consecutive pawns is at a distance of 2 from each other) .
So, the total number of arrangements for a single rank is \frac{N+5}{4}. The total number of arrangements is (\frac{N+5}{4})^{N-1}.
The following are the 4 possible arrangements for a single rank of a 11\times 11 chessboard -
TIME COMPLEXITY:
\mathcal{O}(T\log N) because of exponentiation.
SOLUTIONS:
Setter's Solution
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
int power(int a,int b)
{
if(b==0)
return 1;
else
{
int x=power(a,b/2);
int y=(x*x)%MOD;
if(b%2)
y=(y*a)%MOD;
return y;
}
}
void solve(int tc)
{
int n;
cin >> n;
int pawns,arrangements;
if(n%4==0)
pawns = (n-1)*n/2;
else if(n%4==1 || n%4==3)
pawns = (n-1)*(n+1)/2;
else
pawns = (n-1)*(n+2)/2;
if(n%4==0)
arrangements = 1;
else if(n%4==1)
arrangements = power((n-1)/4,n-1);
else if(n%4==2)
arrangements = power((n+2)/4,2*(n-1));
else
arrangements = power((n+5)/4,n-1);
cout << pawns << " " << arrangements << '\n';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007ll //998244353ll
#define mii map<int, int>
using namespace std;
int power(int a, int b, int p=mod) {
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n%4==0)
cout<<((n-1)*(n/2))<<" "<<1<<"\n";
else if(n%4==1)
cout<<((n-1)*((n+1)/2))<<" "<<power(n/4, n-1)<<"\n";
else if(n%4==2)
cout<<((n-1)*(n/2 + 1))<<" "<<power(n/4 + 1, 2*(n-1))<<"\n";
else
cout<<((n-1)*(n/2 + 1))<<" "<<power(n/4 + 2, n-1)<<"\n";
}
}