You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 07 Mar '17, 18:43

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 13 Mar '17, 15:27

admin's gravatar image

0★admin ♦♦
19.8k350498541


@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

link

answered 19 Mar '17, 12:36

naksh9619's gravatar image

4★naksh9619
6196
accept rate: 12%

edited 19 Mar '17, 12:49

Nice of you to help him!

(19 Mar '17, 12:40) vijju123 ♦♦5★

happy coding :)

(19 Mar '17, 12:42) naksh96194★

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 /

link

answered 19 Mar '17, 11:54

vayuhu's gravatar image

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

link

answered 19 Mar '17, 11:56

vayuhu's gravatar image

0★vayuhu
1
accept rate: 0%

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 :)

(19 Mar '17, 12:06) vijju123 ♦♦5★

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

link

answered 25 Mar '17, 23:06

ankurraj1's gravatar image

0★ankurraj1
1
accept rate: 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;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&lt;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?

link

answered 29 Mar '17, 10:43

sonai2000's gravatar image

2★sonai2000
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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