×

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

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.

This question is marked "community wiki".

75485097
accept rate: 12%

19.8k350498541

 1 @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 :) Edit:Your AC solution Click here answered 19 Mar '17, 12:36 619●6 accept rate: 12% Nice of you to help him! (19 Mar '17, 12:40) happy coding :) (19 Mar '17, 12:42)

# 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 /

0★vayuhu
1
accept rate: 0%

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

0★vayuhu
1
accept rate: 0%

(19 Mar '17, 12:06)

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<iostream>

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

1
accept rate: 0%

 0 /* 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;is2)System.out.println(s2); else System.out.println(s1); } } } What is wrong with my code? answered 29 Mar '17, 10:43 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×1,688
×124
×81
×5

question asked: 07 Mar '17, 18:43

question was seen: 1,532 times

last updated: 17 Feb, 13:09