PROBLEM LINK:Practice Setter: Stylianos Kasouridis DIFFICULTY:Simple PREREQUISITES:Arrays would do. PROBLEM: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. QUICK EXPLANATION
EXPLANATIONFirst of all, understand the worst case for any soldier. If considering soldier $x$, both soldiers labeled $x1$ and $x+1$ may choose to attack him. In this case, Attack applied on him shall be sum of attacking powers of soldiers $x1$ 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[i1]+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 ComplexityTime complexity is $O(N)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter'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

import java.util.scanner; class airland { public static void main(String []args) { int i=0,T,N; Scanner sc=new Scanner(System.sc); 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[N1]; brl=ar+al; } else if(i==N1) { ar=a[0]; al=a[N2]; brl=ar+al; } else { ar=a[N1]; 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
