You are not logged in. Please login at to post your questions!




Contest: Division 1
Contest: Division 2

Setter: Stylianos Kasouridis
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh




Arrays would do.


Given Attacking power and shield power of $N$ soldiers standing in a circle in order, labeled from 1 to $N$ such that soldier $N$ is to the left to soldier $1$. When the king commands, each soldier may attack one of the soldiers standing adjacent to it at once. King asks to find out the most powerful shield of the soldier which is guaranteed to survive irrespective of the soldiers being attacked. A soldier survives if its defense shield power is strictly greater than the attack applied on him. Print -1, if no soldier is guaranteed to survive.


  • In the worst case for each soldier, both of the adjacent soldiers might choose to attack him, in which case, the attack applied on him is the sum of attacking power of both soldiers attacking the current soldier.
  • So, a soldier survives in the worst case only if the power of his defence shield is greater than the sum of attacking power of two adjacent soldiers. Out of all surviving soldiers, the power of most powerful shield is the required shield power here.


First of all, understand the worst case for any soldier. If considering soldier $x$, both soldiers labeled $x-1$ and $x+1$ may choose to attack him. In this case, Attack applied on him shall be sum of attacking powers of soldiers $x-1$ and $x+1$.

Now, Since we need to guarantee that the soldier survives, we shall only choose the shield of a soldier whose defense shield is powerful than the sum of attacking power of adjacent soldiers. Since we want to find the most powerful shield, we may offer to the king, the shield with maximum power out of all these shields.

For implementation, we can just make two arrays $A$ and $D$ and check $D[i] > A[i-1]+A[i+1]$ and take maximum value of $D[i]$ here. Don't forget to consider that solder $N$ and soldier $1$ are adjacent too.

Extended problem

In this problem, there are $N$ soldiers and given $M$ pairs of soldiers which may attack each other, find out the best shield to be offered to king. The condition is same. If the chosen soldier doesn't survive, you, the deputy of Chef die a painful death.

Time Complexity

Time complexity is $O(N)$ per test case.


Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 13 Feb, 23:48

taran_1407's gravatar image

accept rate: 22%

edited 16 Feb, 17:01

admin's gravatar image

0★admin ♦♦

import java.util.scanner; class airland { public static void main(String []args) { int i=0,T,N; Scanner sc=new Scanner(; T=sc.nextInt(); N=sc.nextInt();

for(i=T;i>0;i--) { int s=-1; int a[]=new int[N]; int b[]=new int[N]; for(i=0;i<N;i++) { a[i]=sc.nextInt(); } for(i=0;i<N;i++) { b[i]=sc.nextInt(); } int ar,al,brl,win=0,; if(i==0) { ar=a[1]; al=a[N-1]; brl=ar+al; } else if(i==N-1) { ar=a[0]; al=a[N-2]; brl=ar+al; } else { ar=a[N-1]; al=a[N+1]; brl=ar+al; }

if(ar<b[i]){ {="" win++;="" }="" if(al<b[i])="" {="" win++;="" }="" if(brl<b[i])="" {="" win++;="" }="" if(win="=3" &&="" b[i]="">-1) { s=b[i] } } System.out.println(s); System.out.println(\n); } } }


answered 26 Feb, 11:54

pankaj001's gravatar image

accept rate: 0%

edited 26 Feb, 15:00

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 13 Feb, 23:48

question was seen: 642 times

last updated: 26 Feb, 15:00