PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Setter : Sombit Bose
Tester : Alipasha Montaseri / Kasra Mazaheri
Editorialist : Anand Jaisingh
DIFFICULTY :
Medium
PREREQUISITES :
Bit manipulation.
PROBLEM :
Please read the statement using the links above.
Quick Explanation
The idea here is to try and place Josh in each position from 1 to N and calculate the minimum defense required if he is placed in the current position.
The difficult part is calculating fast for a particular position, the minimum defense required if Josh is placed in it. The basic idea about calculating this number fast is maintaining Josh’s previous soldier at all times.
It can be proved that the number of attacks on Josh ( when we fixed his position ) is of the order of O( \log(N)), and we can find out who carried out these attacks and sum their sword powers.
EXPLANATION :
This problem is all about hard work. You need to work out multiple test cases on paper, and finding a working pattern to construct a solution.
The basic idea we’re going to use here is : For each position from 1 to N, we try and place Josh in this position. Now, for each position, we just consider Josh never dies if he’s placed in this position, and sum the sword powers of all attacks on him.
The answer shall be the minimum of such a sum over all positions. Let’s begin.
Subtask 1 :
Here, the basic idea is to just simulate the entire process for each starting position of Josh. This can be done in O(N \cdot \log (N)) time for a single position using just a vector ( or a boolean array ), and a variable sum.
As there are N distinct starting positions, the complexity of such a solution is approximately O( N^2 \cdot \log (N))
Full Score :
Here, we need to be more clever. Instead of doing the entire simulation, we just try and maintain the sum of attacks over Josh and his previous soldier.
Claim 1 :
If Josh is placed at position P, then the number of times he can be attacked and his previous soldier can change is of the order of O( \log(N))
Proof :
Let’s mark the position Josh is standing using an X, and all other positions by the index of the soldier standing on them. Now, let’s call a single step a process where all existing soldiers in the game have attacked or been attacked, beginning with the 1^{st} existing soldier.
For example, if the current list is [1,2,X,3,4] , then at the end of step 1, the list shall be [1,X,3] , and after the second step it shall be [X,3].
Then, it’s easy to see that Josh’s previous soldier can change only once during a single step. Also, during a single step, Josh may be attacked at most once. Now, during each step, the size of the current list decreases by almost half.
So, the maximum number of steps if of the order of O( \log(N)) , and hence the above claim holds.
Now, let’s make some very important observations.
Observation 1 :
Let’s say that the soldiers with higher positional index that Josh are to his right, and the others are to his left. Then, let the number of soldiers to Josh right be Z. In that case, after each step, Z transforms as : Z = \left\lceil \frac{Z}{2} \right\rceil
Proof :
We know that Josh won’t attack anybody. So, all soldiers standing at an odd distance from Josh to his right will survive, and all others will be killed.The numbers of such soldiers standing at odd distance from Josh is always \left\lceil \frac{Z}{2} \right\rceil
For example, if the current list is :
[1,2,3,X,4,5,6] , then after 1 step it is [3,X,4,6], and after 2 steps it is [3,X,4]. Here, Z is initially 3, then 2, and then 1.
Observation 2 :
After a certain number of steps have been performed, let’s say the vector v_1 contains indexes of all soldiers to Josh’s left, and v_2 contains those to his right.
For example, if the current arrangement is [1,2,3,X,4,5], then after 1 more step, the vector v_1 is [1,3], and the vector v_2 is [4],
Now, we need to handle 2 cases.
- The size of v_2 i.e. Z is odd.
In this case, the soldiers that have an odd index in vector v_1 are killed during the next step.
For example, if the current arrangement is [1,3,5,7,X,8,10,12], then in the next step, soldier 1,5 will be dead.
- The size of v_2 i.e. Z is even.
In this case, the soldiers with even index in v_1 will be killed.
Now, instead of actually maintaining these lists v_1 and v_2, we can just keep 2 variables left and right, indicating the person immideatly to the left of Josh, and the rightmost person in the list.
If no soldier stands to the left of Josh, then let left =-1, and actually Josh’s previous soldier is right. The variables left and right are functions of the number of steps performed , the current left and right, and the parity of Z.
Maintain left :
If i steps have been performed, and Z \mod 2 \equiv 0 , and the current left has its i^{th} bit set in binary, then left=left-(2^{i}).
If i steps have been performed and Z \mod 2 \equiv 1 , and the current left does not have it’s i^{th} bit set, then left=left-2^{i}.
In all other cases, left does not change.
Maintain right :
If i steps have been performed , i \ge 1 and Z \mod 2 \equiv 0 , then right=right-2^{i-1}
In all other cases, right remains the same.
It’s obviously easy to sum up sword powers when before/ after each step we know Josh’s previous soldier.
In the end, when there are exactly 2 soldiers left, i.e Josh and right ( It can be proved that right always equals the index of the soldier that was to the right of Josh in the initial arrangement ) , we just need to check if A[right] \le F .
If that is not the case, it’s not possible to place Josh here, since then right will keep hitting Josh indefinitely, and he will eventually die.
Since, after we fix Josh position, the number of attacks, left/right changes we process are of the order O(\log(N)) and all operations we perform are O(1), taking into consideration all starting positions, the overall time complexity is O( N \cdot \log(N))
COMPLEXITY ANALYSIS :
Time Complexity : O( T \cdot ( N \cdot \log N ) )
Space Complexity : O(N)
SOLUTION LINKS :
Setter
import math
def impossible(F,N,l):
l2=[]
count=0
for i in range(N-1):
if l[i]<=F:
l2.append(i)
else:
count+=1
if count==N-1:
print("impossible")
return
pos=0
Dmin=math.inf
for i in range(len(l2)):
D=F
l3=[j for j in range(N-1)]
index=0;carry=0
while len(l3)>1:
if l3[index]==l2[i] and carry==1:
D=D+l[l3[index-1]]
index+=1
if index>=len(l3):
index=0
elif carry==1:
del(l3[index])
carry=0
elif carry==0:
carry=1
index+=1
if index>=len(l3):
index=0
if Dmin>D:
Dmin=D
pos=l2[i]+1
print("possible")
print(pos,Dmin)
T=int(input())
while T>0:
N=int(input())
l=list(map(int,input().split()))
F=int(input())
pos=int(math.log2(N-1))
pos=N-pow(2,pos)
pos=2*pos-1
if(l[pos-1]>F):
impossible(F,N,l)
else:
print("possible")
print(pos,F)
T=T-1
Tester
// KALAM
# include<bits/stdc++.h>
using namespace std;
const int N = 1000000 + 77 , L = 22;
const long long inf = 1e18 + 77;
int T;
int n , F;
int a[N];
inline void Test() {
scanf("%d" , & n);
for(int i = 1;i < n;++ i)
scanf("%d" , a + i);
scanf("%d" , & F);
vector < int > odd;
pair < long long , int > A = make_pair(inf , - 1);
for(int i = 1;i < n;++ i) {
if(i > 1 && (i % 2 == 0))
odd.push_back(a[i - 1]);
if(F < a[i])
continue ;
long long cost = 0;
if(i % 2 == 0)
cost += odd.back();
int sz = n - i + (odd.size());
int f = (1 << 30);
int tsz = sz;
for(int bit = 0;bit < L;++ bit) {
if(tsz & 1) {
int pos = ((sz - 1) & (f - (1 << bit))) + 1;
if(pos == 1)
continue ;
if(pos <= n - i)
cost += a[i + pos - 1];
else
cost += odd[pos - n + i - 1];
}
tsz = ((tsz + 1) >> 1);
}
cost += F;
A = min(A , make_pair(cost , i));
}
if(A.first == inf)
printf("impossible\n");
else {
printf("possible\n");
printf("%d %lld\n" , A.second , A.first);
}
}
int main() {
scanf("%d" , & T);
while(T --)
Test();
return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(1e6+6);
const ll mod=(ll)(1e9+7);
int a[maxn];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
while(t>0)
{
int n;cin>>n;
for(int i=1;i<n;i++)
{
cin>>a[i];
}
int F;cin>>F;
int res=INT_MAX,pos=-1,left_pos=-1,left_tot=0;
for(int i=1;i<=n;i++)
{
int now=0;
if(i%2==0)
{
left_pos=i-1;now=a[i-1];left_tot++;
}
int nxt=(i==n)?1:i;
if(a[nxt]>F)
{
continue;
}
int right=n-i,left=left_tot,bit=1,right_last=n-1,left_last=left_pos;
while(left+right>1)
{
//cout<<left<<" "<<right<<" "<<left_last<<" "<<right_last<<endl;
if(right%2==0)
{
right_last-=(1<<(bit-1));
left=(left+1)/2;
if(left_last>=1 && (left_last&(1<<bit)))
{
left_last-=(1<<bit);
}
else if(left_last>=1)
{
now+=a[left_last];
}
}
else
{
left/=2;
if(left_last<1)
{
now+=a[right_last];
}
if(left_last>=1 && (left_last&(1<<bit))==0)
{
left_last-=(1<<bit);
}
else if(left_last>=1)
{
now+=a[left_last];
}
}
right=(right+1)/2;bit++;
}
// cout<<i<<" "<<now<<endl;
if(now<res)
{
res=now;pos=i;
}
}
if(pos>=1)
{
cout<<"possible"<<endl;
cout<<pos<<" "<<(res+F)<<endl;
}
else
{
cout<<"impossible"<<endl;
}
t--;
}
return 0;
}
