DEPCHEF - EDITORIAL

taran_1407 · February 13, 2019, 11:48pm

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.

pankaj001 · February 26, 2019, 11:54am

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

shysta · March 24, 2019, 1:32pm

#include <stdio.h>
#include<stdlib.h>
void main() {

int T;
scanf("%d",&T);
while(T--){
    int N;
    scanf("%d",&N);
    int i;
    int attack[N],defense[N];
    for(i=0;i<N;i++){
        scanf("%d",&attack[i]);
    }
    int original_defense[N];
    for(i=0;i<N;i++){
        scanf("%d",&defense[i]);
        original_defense[i]=defense[i];
    }
    
    for(i=0;i<N;i++){
        if(i==0){
            defense[i]-=attack[i+1]+attack[N-1];
        }
        else if(i==N-1){
            defense[i]-=attack[i-1]+attack[0];
        }
        else{
            defense[i]-=attack[i-1]+attack[i+1];
        }
    }
    int best_shield=defense[0];
    int soldier=0;
    for(i=1;i<N;i++){
        if(best_shield<defense[i]){
            best_shield=defense[i];
            soldier=i;
        }
    }
    if(best_shield>0){
    printf("%d\n",original_defense[soldier]);
    
    }
    else
    printf("-1\n");
    
}

}

this is returning as wrong answer what\s wrong in this

puru_behl · July 12, 2019, 4:47am

for i in range(int(input())):
n=int(input())
a= [int(x) for x in input().split()]
b= [int(x) for x in input().split()]
c=[]
for j in range(n):
if b[i]-a[i+1]-a[i-1]<0:
c.append(0)
else :
c.append(b[i]-a[i+1]-a[i-1])
if max©==0:
print(-1)
else:
print(b[c.index(max©)])

puru_behl · July 12, 2019, 4:48am

this is my answer . it gives the correct answer but ain’t successful in code shef .Don’t know why?

puru_behl · July 12, 2019, 4:50am

and please it was max© i don’t kn ow why the copyright sign came

puru_behl · July 12, 2019, 4:50am

max( c) is what i wrote

aditya_oke · January 13, 2020, 12:07pm

Simple Python 3 Implementation

t = int(input())
while(t>0):
    n = int(input())
    atk = list(map(int, input().split()))
    defe = list(map(int, input().split()))
    
    if(atk[-1] + atk[1] >= defe[0]):
        shield = -1
    else:
        # 1st soldier survives
        shield = defe[0]
    
    if(atk[-2] + atk[0] >= defe[-1]):
        shield_l = -1
    else:
        shield_l = defe[-1]
        
    shield = max(shield, shield_l)
    
    for i in range(1, n-1):
        if(atk[i-1] + atk[i+1] < defe[i]):
            shield = max(shield, defe[i])
    
    print(shield)
    t -= 1

anon9973776 · April 20, 2020, 2:54am

@shysta You have not focused

on this line of output format
** print a single line containing one integer ― the best defense value of the shield the king gets, or −1−1 if Chef can be thrown in the snake pit.**

anon77629987 · August 13, 2020, 4:39pm

#include<bits/stdc++.h>

using namespace std;

int main() {

int t;

cin>>t;

while(t--)

{

    int n;

    cin>>n;

    int A[n],D[n];

    for(int i=0;i<n;i++)

    cin>>A[i];

     for(int i=0;i<n;i++)

    cin>>D[i];

     int ans=-1;

    for(int i=0;i<n;i++)

    {

        if(D[i]>A[i+1]+ A[i-1] && i!=0 )

        {

        ans=max(ans,D[i]);

        }

        else if(i==0)

        {

            if(D[i]>A[i+1]+ A[n-1])

            {

            ans=max(ans,D[i]);

            }

        }

        else if(i=n-1)

        {

            if(D[i]>A[i-1]+ A[0]) {

             ans=max(ans,D[i]);

            }

        }

    }

    cout<<ans<<endl;

}

return 0;

}

Why this is giving the wrong answer on submission. Please tell any error

ub2092000 · November 1, 2020, 6:38pm

Why is it showing WA can someone tell the error.

#include <stdio.h>

int main()

{

int t;

scanf("%d", &t);

while (t--)

{

    int n;

    scanf("%d", &n);

    int a[n], d[n];

    for (int i = 0; i < n; i++)

    {

        scanf("%d", &a[i]);

    }

    for (int i = 0; i < n; i++)

    {

        scanf("%d", &d[i]);

    }

    int min = 0;

    int v = 0, l = -1;

    for (int i = 0; i < n; i++)

    {

        if (i == 0)

        {

            v = d[i] - a[n - 1] - a[i + 1];

        }

        else if (i == n - 1)

        {

            v = d[i] - a[i - 1] - a[0];

        }

        else

        {

            v = d[i] - a[i + 1] - a[i - 1];

        }

        if (v > min)

        {

            min = v;

            l = d[i];

        }

    }

    printf("%d\n", l);

}

return 0;

}