Depchef - editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

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

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

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

EXPLANATION

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

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

2

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[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);
}
}
}