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

×

UTMOPR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ankit Srivastava and Uttam Kanodia
Tester: Roman Rubanenko
Editorialist: Amit Pandey

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic programming

PROBLEM:

Given an array of $n$ integers, you have to do the following operation $K$ times: Insert a number in the array which is strictly greater than current sum of the array. You have to find whether the last number inserted is even or odd.

QUICK EXPLANATION:

As the value of $K$ is small, we can keep inserting smallest possible numbers at each step and print the $K^{th}$ number modulo $2$.

EXPLANATION:

This problem can be solved by simulating the operation given in the problem.

First find the sum of the given array($A$) . This can be done in $O(N)$ time using a single loop. As we have to print the $K^{th}$ element to be inserted (modulo $2$), we can replace $S$ by $S\ \% \ 2$.

S = 0;
for(int i=0; i< n; i++)
    S = S + A[i];
    S = S%2;

Now make an array $B$ of size $(K+1)$, $B_i$ will denote the $i^{th}$ element to be inserted, and $B_K$ will be our required answer. At any step, if parity of the sum of the elements of array is "even", parity of inserted element will be "odd".

B[1] = (S + 1) % 2 ;   // we will insert the smallest possible number at each step
total_sum = 0;
for(int i=2 ; i< K ; i++)
{
    total_sum = (total_sum + B[i-1]);
    B[i] = (total_sum + 1) % 2; // insert a number greater than current sum of the array.
}

Finally we can output $B_K$. The time complexity of the whole code will be $\mathcal{O}(N + K)$.

Another solution
Let us say that sum of the array $A$ is even. The next inserted element will be odd, now sum of array will be odd, so next inserted element will be even, now sum of array becomes odd, so we will insert an even number, and so on. So we can generalize that if sum of array is even, then for $K = 1$, last inserted number will be odd, otherwise it will be even.

Now, we will consider the case in which sum of the array $A$ is odd. The next inserted element will be even, now sum of array will become odd, so next inserted element will be even, now sum of array will be odd, we will add another even number, and so on. So we can generalize that last inserted number is always even in this case.

So finally, we can obtain the following simple solution.

Compute sum of array.
If K = 1:
    if sum is even:
        print "odd"
    else:
        print "even"
else:
    print "even"

Solution:

Setter's solution can be found here
Tester's solution can be found here

This question is marked "community wiki".

asked 17 Jun '15, 22:56

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 09 Feb '16, 19:58

admin's gravatar image

0★admin ♦♦
19.8k350498541


because Tester and Setter solution not yet updated ....

here is my code...

#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,k;
    int sum=0,val=0,ans=0;
    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&k);
        sum=0;

         while(n--){
         scanf("%d",&val);
         sum+=val;
         }
        if(sum%2==0){

            if(k==1) printf("odd\n");
            else printf("even\n");
         }
         else printf("even\n");
     }
     return 0;

}

End of code..................HAPPY CODING

link

answered 22 Jun '15, 00:25

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

edited 22 Jun '15, 09:50

2

This person is down voting answers to get his on top. How fascinating.

(28 Jun '15, 23:47) gkcs4★

@rcsldav2017 press CTRL+K and start typing your code

link

answered 22 Jun '15, 01:09

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

@shubham99 .... THANKS DUDE....IT WORKS

(22 Jun '15, 09:52) rcsldav20175★

I wonder how could this solution be accepted! It just prints "odd" if k equals 1, and prints "even" otherwise.

link

answered 22 Jun '15, 01:34

snk967's gravatar image

4★snk967
1841110
accept rate: 9%

lol, thats his luck

(22 Jun '15, 08:58) king_of_hacker3★

@snk967:- That happened because of some weak test cases at corner!

(22 Jun '15, 09:02) saiavinashiitr1★

IT WORKS SOME TIMES..YOUR CODE WORKS BUT U DON'T KNOW HOW IT WORK.. VERY WEAK TEST CASES....IT IS NOT GOOD AFTER SEEING VERY LOOSE TEST CASE..

(22 Jun '15, 09:56) rcsldav20175★

No array will be not like S, S+1, 2S+2, 4S+4, 8S+8, 16S+16. It will be like S, 2S+1, 4S+3, 8S+7, 16S+15.....

kth term -> S * ( 2 ^ ( k - 1 ) ) + ( 2 ^ ( k - 1 ) - 1 ).

Then we can get answer by putting values of S and k.

link

answered 22 Jun '15, 00:36

dushsingh1995's gravatar image

4★dushsingh1995
92313
accept rate: 11%

Can someone point out the mistake in my solution?
I guess it's pretty much same as @rcsldav2017 's solution.


#include <bits stdc++.h="">
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    int n,k,x,s=0;
    cin>>n>>k;
    while(n--)
    {
        cin>>x;
        s += x%2; 
    }
    if(k==1)
    {
        if(s%2)
            cout<<"even"<<endl; else="" cout<<"odd"<<endl;="" }="" else="" cout<<"even"<<endl;="" return="" 0;="" }="" <="" code="">
link

answered 23 Jun '15, 13:57

nikhilhassija's gravatar image

4★nikhilhassija
193
accept rate: 0%

hi I have corrected your code and pointed out your mistake ...hope it is helpful to u....happy coding.................

(29 Jun '15, 12:54) rcsldav20175★

@nikhilhassija

Number of test cases. Your code should run for Various test case T. You are not scanning that.

link

answered 23 Jun '15, 20:16

shivam9753's gravatar image

4★shivam9753
696112
accept rate: 17%

We can also observe a pattern forming in the array. First, the sum of all elements in the array is computed to be S. Then, the array fans out as: S, S+1, 2S+2, 4S+4, 8S+8, 16S+16....

The kth term is equal to 2^(k-1)*(S+1)

So our answer is odd if and only if S is even and K is equal to 1. Complexity: O(N).

link

answered 22 Jun '15, 00:23

gkcs's gravatar image

4★gkcs
2.6k11128
accept rate: 9%

@amitpandeykgp...how to paste code with indentation here...

link

answered 22 Jun '15, 00:36

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

@nikhilhassija

hi....

actually your logic is same as mine and

  • your logic is right too

  • what is wrong with your code

  • why u got WA?

here what you have missed...

just look at constraints

  • Constraints:

  • 1 ≤ T ≤10

  • 1 ≤ K ≤ pow(10,6)
  • 1 ≤ N ≤ pow(10,3)
  • 1 ≤ array element ≤ pow(10,9)

-Hope you get your mistake ....still not...No problem

MISTAKE

  • 1<=array element<pow(10,9)
    • what You have done here... int n,k,x,s=0;
    • how can u store x[1,pow(10,9)] into integer data type
  • Your are thinking here is no test case ..still believe look at constraints again....):P

Solution

  • make x and sum variable long or long long

- there are multiple test cases.... look at 1<=T<=10

here is your corrected code..still did not get it ...click on me

for more conversation join my group....Novice Programmers @ NITK


Happy coding

link

answered 29 Jun '15, 12:52

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

its showing runtime error...can someone please help?

include<stdio.h>

include<stdlib.h>

int main() { int t,n,k,j,i,sum=0;

scanf("%d",&t);
for(i=0;i<t;i++)
{

    scanf("%d%d",&n,&k);
    int *N=(int *)malloc((n+k)*sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%d",N+i);
        sum=sum+*(N+i);

    }
    if(k==1)
    {
        if(sum%2==0)
            printf("odd");
        else
            printf("even");

    }
    else
        printf("even");

}

}

link

answered 01 Jul '15, 10:32

gpurva_18's gravatar image

0★gpurva_18
1
accept rate: 0%

Since you declared sum as int sum=0 , but each number can be uptil 10^9 and total numbers at max can be 10^3 so sum becomes 10^12 which overflows int data type. So I hope using long long will help.

(01 Jul '15, 14:22) apptica5★

public static String logicHere(String fileName){ BufferedReader br = null; int opArr[]; int N=0; int K=0; String line2=""; String line3=""; int initialSum=0; String retValue=""; try {
br = new BufferedReader(new FileReader(fileName)); br.readLine(); line2=br.readLine(); line3=br.readLine(); String[] tmpCh = line2.split(" "); N=Integer.parseInt(tmpCh[0]); K=Integer.parseInt(tmpCh[1]); opArr = new int[N+K]; tmpCh = line3.split(" "); for(int i=0;i<N;i++){ int tmp=Integer.parseInt(tmpCh[i]); opArr[i]= tmp%10; initialSum=(initialSum + tmp)%10; } for(int i=N;i<K;i++){ opArr[i]=(initialSum%10)+1; initialSum=(initialSum+opArr[i])%10; } if(opArr[K]%2==0) retValue="even"; else retValue="odd";

    }
    catch(Exception ex){
        ex.printStackTrace();
    }
    return retValue;
}
link

answered 01 Jul '15, 15:16

kulsingh's gravatar image

2★kulsingh
1
accept rate: 0%

Why everyone is trying to take an array and then evaluate the sum. There's no need of it at all. We just need to look for number of odd elements in the array. if number of odd elements is even then sum is always even.if number of odd elements is odd them sum is always odd.

enter code here
import java.util.*;

import java.math.*; import java.util.regex.Pattern; public class check {

// Driver code
public static void main(String[] args)
{

Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t>0){ int n=sc.nextInt(); int k=sc.nextInt(); int count=0; for(int i=0;i<n;i++){ if(sc.nextInt()%2!=0){ count++; } } if(count%2==0){ if(k==1) System.out.println("odd"); else System.out.println("even"); }else{

    System.out.println("even");

} t--; }

}

}

link

answered 29 Oct '16, 00:12

kanha95's gravatar image

1★kanha95
1
accept rate: 0%

include<bits stdc++.h="">

using namespace std; int main() { int t; cin>>t; while(t--) { int n,k; cin>>n>>k; long long s=0,a[n+5]; for(int i=0;i<n;i++) {="" cin="">>a[i]; s+=a[i]; } if(k==1) cout<<((s+1)%2?"odd":"even"); else if(k==2) cout<<((2*s+1)%2?"odd":"even"); else cout<<"even"; cout<<endl; } return 0; }

link

answered 25 Dec '16, 17:32

salman_1's gravatar image

5★salman_1
1
accept rate: 0%

Plz can someone point out mistake in my code plz.Here is my code:

include<bits stdc++.h="">

using namespace std; int main() { int t; cin>>t; while(t--) { long long int n,k,i,s=0; cin>>n>>k; long long int a[n]; for(i=0;i<n;i++){

    cin>>a[i];
    if(a[i]%2==1)
    s++;

}
if(s%2==1)
s=1;
else
s=0;
if(k==1)
{
    if(s==1)
    cout<<"odd"<<endl;
    else
    cout<<"even"<<endl;
    }
    else
    cout<<"even"<<endl; 
}
return 0;

}

link

answered 30 Dec '16, 12:12

saisurya027's gravatar image

4★saisurya027
1666
accept rate: 0%

#include<bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t;

while(t--)
{
    int n,k;
    cin>>n>>k;
    long int a[n],s=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s+=a[i];
    }

    if(s%2==0&&k==1)
    {
        cout<<"odd\n";
    }
    else
        cout<<"even\n";
}
return 0;

}

link

answered 21 Jul '18, 11:34

prateek181996's gravatar image

2★prateek181996
1
accept rate: 0%

-1

Here is my solution too short

include<bits stdc++.h="">

using namespace std; int main() { long long int t,n,k,i,s,a,p; cin>>t; while(t--) {s=0; cin>>n>>k; for(i=0;i<n;i++) {="" cin="">>a; s+=a; } p=(s+1)*(long long int)pow(2,k-1); if(p%2==0) cout<<"even"<<endl; else cout<<"odd"<<endl; } }

link

answered 22 Jun '15, 10:54

bhardwaj_75's gravatar image

4★bhardwaj_75
-11
accept rate: 0%

nothing is short same as previous............):P

(29 Jun '15, 12:55) rcsldav20175★
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:

×1,646
×170
×81
×81
×1

question asked: 17 Jun '15, 22:56

question was seen: 4,553 times

last updated: 21 Jul '18, 11:34