# CHFWAR-Editorial

**URL:** <https://discuss.codechef.com/t/chfwar-editorial/31169>\
**Category:** editorial\
**Tags:** medium, july19, bitwise-operation\
**Created:** [July 14, 2019, 12:58pm UTC](https://discuss.codechef.com/t/chfwar-editorial/31169 "2019-07-14T12:58:26Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![anand20](https://discuss.codechef.com/user_avatar/discuss.codechef.com/anand20/32/259015_2.png) [@anand20](https://discuss.codechef.com/u/anand20)\
**Post date:** [July 14, 2019, 12:58pm UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/1 "2019-07-14T12:58:26Z")

</div>

# PROBLEM LINKS :

Contest : [Division 1](https://www.codechef.com/JULY19A/problems/CHFWAR)

Contest : [Division 2](https://www.codechef.com/JULY19B/problems/CHFWAR)

[Practice](https://www.codechef.com/problems/CHFWAR)

**Setter :** [Sombit Bose](https://www.codechef.com/users/deadshot_sb)

**Tester :** [Alipasha Montaseri](https://www.codechef.com/users/alipasha132) / [Kasra Mazaheri](https://www.codechef.com/users/kmaaszraa)

**Editorialist :** [Anand Jaisingh](https://www.codechef.com/users/anand20)

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

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

---

<div class="post-metadata">

**Author:** ![an09mous](https://discuss.codechef.com/user_avatar/discuss.codechef.com/an09mous/32/47737_2.png) [@an09mous](https://discuss.codechef.com/u/an09mous)\
**Post date:** [July 15, 2019, 10:48am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/2 "2019-07-15T10:48:39Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![anand20](https://discuss.codechef.com/user_avatar/discuss.codechef.com/anand20/32/259015_2.png) [@anand20](https://discuss.codechef.com/u/anand20)\
**Post date:** [July 15, 2019, 10:50am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/3 "2019-07-15T10:50:56Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![codingisez](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codingisez/32/10974_2.png) [@codingisez](https://discuss.codechef.com/u/codingisez)\
**Post date:** [July 15, 2019, 10:52am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/4 "2019-07-15T10:52:53Z")

</div>

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 …

---

<div class="post-metadata">

**Author:** ![megatron10](https://discuss.codechef.com/user_avatar/discuss.codechef.com/megatron10/32/256270_2.png) [@megatron10](https://discuss.codechef.com/u/megatron10)\
**Post date:** [July 15, 2019, 10:53am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/5 "2019-07-15T10:53:29Z")

</div>

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](https://www.codechef.com/viewsolution/25283640)

---

<div class="post-metadata">

**Author:** ![mohittkkumar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mohittkkumar/32/269227_2.png) [@mohittkkumar](https://discuss.codechef.com/u/mohittkkumar)\
**Post date:** [July 15, 2019, 10:55am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/6 "2019-07-15T10:55:31Z")

</div>

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](https://www.codechef.com/viewsolution/25203919)

It passes within 0.24 sec in JAVA.

---

<div class="post-metadata">

**Author:** ![an09mous](https://discuss.codechef.com/user_avatar/discuss.codechef.com/an09mous/32/47737_2.png) [@an09mous](https://discuss.codechef.com/u/an09mous)\
**Post date:** [July 15, 2019, 11:05am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/7 "2019-07-15T11:05:37Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![agtxdy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/agtxdy/32/278000_2.png) [@agtxdy](https://discuss.codechef.com/u/agtxdy)\
**Post date:** [July 15, 2019, 11:08am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/8 "2019-07-15T11:08:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![codingisez](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codingisez/32/10974_2.png) [@codingisez](https://discuss.codechef.com/u/codingisez)\
**Post date:** [July 15, 2019, 11:08am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/9 "2019-07-15T11:08:20Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![an09mous](https://discuss.codechef.com/user_avatar/discuss.codechef.com/an09mous/32/47737_2.png) [@an09mous](https://discuss.codechef.com/u/an09mous)\
**Post date:** [July 15, 2019, 11:09am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/10 "2019-07-15T11:09:40Z")

</div>

Can’t you see the editorial?

---

<div class="post-metadata">

**Author:** ![spookywooky](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@spookywooky](https://discuss.codechef.com/u/spookywooky)\
**Post date:** [July 15, 2019, 11:12am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/11 "2019-07-15T11:12:36Z")

</div>

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](https://www.codechef.com/viewsolution/25276044)

---

<div class="post-metadata">

**Author:** ![an09mous](https://discuss.codechef.com/user_avatar/discuss.codechef.com/an09mous/32/47737_2.png) [@an09mous](https://discuss.codechef.com/u/an09mous)\
**Post date:** [July 15, 2019, 11:18am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/12 "2019-07-15T11:18:02Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![megatron10](https://discuss.codechef.com/user_avatar/discuss.codechef.com/megatron10/32/256270_2.png) [@megatron10](https://discuss.codechef.com/u/megatron10)\
**Post date:** [July 15, 2019, 11:18am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/13 "2019-07-15T11:18:17Z")

</div>

Such Editorialist, much wow 😮

---

<div class="post-metadata">

**Author:** ![codingisez](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codingisez/32/10974_2.png) [@codingisez](https://discuss.codechef.com/u/codingisez)\
**Post date:** [July 15, 2019, 11:19am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/14 "2019-07-15T11:19:27Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![agtxdy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/agtxdy/32/278000_2.png) [@agtxdy](https://discuss.codechef.com/u/agtxdy)\
**Post date:** [July 15, 2019, 11:22am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/15 "2019-07-15T11:22:20Z")

</div>

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](https://www.codechef.com/viewsolution/25231988)

---

<div class="post-metadata">

**Author:** ![an09mous](https://discuss.codechef.com/user_avatar/discuss.codechef.com/an09mous/32/47737_2.png) [@an09mous](https://discuss.codechef.com/u/an09mous)\
**Post date:** [July 15, 2019, 11:25am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/16 "2019-07-15T11:25:42Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![codingisez](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codingisez/32/10974_2.png) [@codingisez](https://discuss.codechef.com/u/codingisez)\
**Post date:** [July 15, 2019, 11:27am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/17 "2019-07-15T11:27:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mohittkkumar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mohittkkumar/32/269227_2.png) [@mohittkkumar](https://discuss.codechef.com/u/mohittkkumar)\
**Post date:** [July 15, 2019, 11:37am UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/18 "2019-07-15T11:37:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![iambk](https://discuss.codechef.com/user_avatar/discuss.codechef.com/iambk/32/73261_2.png) [@iambk](https://discuss.codechef.com/u/iambk)\
**Post date:** [July 15, 2019, 12:30pm UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/19 "2019-07-15T12:30:15Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![nikitachirania](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nikitachirania/32/3653_2.png) [@nikitachirania](https://discuss.codechef.com/u/nikitachirania)\
**Post date:** [July 15, 2019, 2:15pm UTC](https://discuss.codechef.com/t/chfwar-editorial/31169/20 "2019-07-15T14:15:34Z")

</div>

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](https://www.codechef.com/viewsolution/25282485)

[Next page](https://discuss.codechef.com/t/chfwar-editorial/31169.md?page=2)