XENTASK - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vaibhav Tulsyan
Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Most basic programming

PROBLEM:

There are N tasks numbered from 1 to N to perform. Two people, Xenny and Yana, have to complete all these tasks alternatingly. It means that either Xenny performs tasks with odd numbers and Yana with even numbers, or Xenny performs tasks with even numbers and Yana with odd numbers. These two ways are the only possibilities to fulfill the task. Moreover, we know that Xenny takes X_i seconds to complete the i-th task, while Yana takes Y_i to do that. The goal of the problem is to compute the minimum possible time in which Xenny and Yana can complete all the tasks.

QUICK EXPLANATION:

Calculate the time needed to complete the tasks for each of two distinct ways of doing that and return the minimum of these times.

EXPLANATION:

The main observation is that since all the tasks have to performed alternatingly by Xenny and Yana, then there are only two distinct ways of completing all the tasks:

  1. Xenny starts first, which means that Xenny performs tasks with odd numbers: 1, 3, \ldots, while Yana performs tasks with even numbers: 2, 4, \ldots
  2. Yana starts first, which means that Yana performs tasks with odd numbers: 1, 3, \ldots, while Xenny performs tasks with even numbers: 2, 4, \ldots

If we assume that for i = 1, 2, \ldots, N X[i] is the time for performing the i-th task by Xenny and Y[i] is the time for performing the i-th task by Yana, then we can solve the problem by the following pseudocode:

xenny_starts_first = 0 // time to perform all the tasks using the first method,
                       // i.e. when Xenny starts first
for i = 1 to N:
    if i is odd:
       xenny_starts_first = xenny_starts_first + X[i] // add time of completing 
                                                      // the i-th task by Xenny
   else:
      xenny_starts_first = xenny_starts_first + Y[i] // add time of completing 
                                                     // the i-th task by Yana

yana_starts_first = 0 // time to perform all the tasks using the second method, 
                             // i.e. when Yana starts first 
for i = 1 to N:
    if i is odd:
       yana_starts_first = yana_starts_first + Y[i] // add time of completing 
                                                    // the i-th task by Yana
   else:
      yana_starts_first = yana_starts_first + X[i] // add time of completing 
                                                   // the i-th task by Xenny

print minimum(xenny_starts_first, yana_starts_first)

Since in order to compute the time of completing the tasks for each of the two methods we need only to iterate once over all tasks, the overall time complexity of this solution is O(N).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.
Editorialist’s solution can be found here.

1 Like

#include<stdio.h>
int main()
{
int t,n,i,z,w;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
int a[n],z=0;
int b[n],w=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
scanf("\n%d",&b[i]);
}
for(i=1;i<=n;i++)
{
if(i%2==0)
{
z+=a[i];
}
else
{
z+=b[i];
}
}
for(I=1;i<=n;i++)
{
if(i%2==0)
{
w+=b[i];
}
else
{
w+=a[i];
}
}
int sum=z<w?z:w;
printf("%d",sum);
}
return 0;
}
/* help me it’s shoing rong answer */

#include<stdio.h>
int main()
{
int t,n,i,z,w;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
int a[n],z=0;
int b[n],w=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
scanf("\n%d",&b[i]);
}
for(i=1;i<=n;i++)
{
if(i%2==0)
{
z+=a[i];
}
else
{
z+=b[i];
}
}
for(i=1;i<=n;i++)
{
if(i%2==0)
{
w+=b[i];
}
else
{
w+=a[i];
}
}
int sum=z<w?z:w;
printf("%d",sum);
}
return 0;
}

@vayuhu Change the indexing in your code or make array of size n+1 this will get you can AC.In your code you have made array of n which will be from 0 to n-1 and you are accessing 1 upto n elements.You are not able to access very first element of the array.Hope it helps :slight_smile:
Edit:Your AC solution Click here

1 Like

hi
I need a little help
codechef is not considering my code as correct answer but I have run is on ideone . com and its running perfectly there.
Can you please tell me where am I wrong.
#include
using namespace std;
int main()
{
int t,n,i;
cin>>t;
int s[2]={0,0};
if(t>=0)
{
cin>>n;
int a[n],b[n];
for(int j=0;j<t;j++)
{

        for(i=0; i<n; i++)
        {
            cin>>a[i];
        }
        for(i=0; i<n; i++)
        {
            cin>>b[i];
        }
        for(i=0;i<n;i++)
        {
            if(i%2==0)
            {
                s[0]+=a[i];
                s[1]+=b[i];
            }
            else
            {
                s[0]+=b[i];
                s[1]+=a[i];
            }
        }
        if(s[0]<=s[1])
            cout<<s[0]<<"\n";
        else
            cout<<s[1]<<"\n";

        s[0]=s[1]=0;
    }
}

return 0;

}
thanks

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
long n,s1=0,s2=0;
long xi[]=new long[20000];
int i;
while(t!=0)
{
t–;
n=sc.nextLong();
for(i=0;i<n;i++)
{
xi[i]=sc.nextLong();
if(i%2==1)s1+=xi[i];
if(i%2==0)s2+=xi[i];
}
for(i=0;i<n;i++)
{
xi[i]=sc.nextLong();
if(i%2==1)s2+=xi[i];
if(i%2==0)s1+=xi[i];
}
if(s1>s2)System.out.println(s2);
else System.out.println(s1);
}
}
}
What is wrong with my code?

Can you edit your answer, select the code and use the “Insert code” button. That would make your code readable. Then I can help you dear :slight_smile:

Nice of you to help him!

happy coding :slight_smile: