# PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Sombit Bose

Tester : Alipasha Montaseri / Kasra Mazaheri

Editorialist : Anand Jaisingh

Medium

# PREREQUISITES :

Bit manipulation.

# 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.

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.

1. 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.

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

1 Like

Long Challenge is all about learning something new. I didn’t learn anything new from this problem. Just spend time in observing patterns isn’t learning.

11 Likes

I’m sorry to admin, but its hard to disagree with you. Not a nice problem to solve.

2 Likes

Everyone has their own interests, I guess you are enough smart to understand if these challenges are good for you or not, then simply participate or not as you think instead of complaining …

2 Likes

If I may present a slightly different solution here, it uses similar ideas but doesn’t need management of left and right blocks. It needs less observations in my opinion, but even if there was no better way than making observations and bit manipulations, it still is a nice problem to solve. [People should stop abusing problems and problem setters when they fail to solve a problem. Keep those negative views to yourself, until you learn how to solve the problem]. It uses a C++ STL data structure (deque).
You can refer the solution idea and code, here :
https://www.codechef.com/viewsolution/25283640

4 Likes

The problem was good and also the logic behind it. But the problems were with testcases , one of my friend just thought of that answer would be last surviving index of josephus’s problem and was checking for that index only and got many AC’s within no time…So, for that case where the index wasnt valid,So he ran a O(n^2) brute force on indexes on whose right soldiers with less than F are present. Shockingly , it passes all of the test cases . If only one of the many sub cases of any testcases was strong enough , it would have TLE’d out.

Here, is a link to that nearly O(n^2) approach–
https://www.codechef.com/viewsolution/25203919

It passes within 0.24 sec in JAVA.

Go and read about Long Challenges in codechef docs. They are all about helping people learn new techniques and tricks, not about spending hours to find patterns.

1 Like

Where is the “pattern recognition” here as you claim? This problem has a legitimate recursive solution.

1 Like

Everyone has there techniques, some people didn’t able to find patterm so they will learn from it. Ability of finding patterns is also related with patience, thinking and writing

1 Like

Can’t you see the editorial?

1 Like

The pattern is that you recongnize that after one round, every second soldier is alive.
After two rounds every fourth. After three rounds every eight… and so on.

But this pattern is so simple, it is not the solution, it is only one step to find the solution.

Here is one with a lot of comments, which might explaining the process of finding one of the solutions.
https://www.codechef.com/viewsolution/25276044

But this problem wasn’t good enough to be in long challenge.There could have been many better problems.

Such Editorialist, much wow

1 Like

See submissions. It was easy than CIRMERGE and GUESSPRIME but still it has less submissions than them.

Editorialist solutions cover greater detail and depth in terms of interpreting a solution. While I would cover the bit-expansion solution of Josephus in an editorial, I would simply write a recursion during a programming contest.

Feel free to look at this:
https://www.codechef.com/viewsolution/25231988

Its because though everyone got the logic, but it was too hard to implement.

Not really, I know many guys who wasn’t able to find approach better than O(n^2)
Some of them are 4stars

Nice approach
Also the part where you defined fast i/o lines as nfs_mw…I love that game.

1 Like

Couldn’t agree more. I personally was too lazy to implement this one and also nothing new to learn. On contrary, people got to learn DP and at least about quadratic residue/congruences from CIRMERGE and GUESSPRIME.

1 Like

can you please debug my code where i am missing…in subtask 1 i got 2 ac and and for some testcases i got wrong answer.i tried too much to find some cases which i am missing.
i have done this problem with recursion.
https://www.codechef.com/viewsolution/25282485