ODDSUM - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Rahul Kumar
Tester: Danny Mittal
Editorialist: Nishank Suresh

DIFFICULTY:

SImple

PREREQUISITES:

None

PROBLEM:

Given N, consider all arrays of length N consisting of non-negative and distinct integers whose prefix sums are all odd. Output the minimum sum of elements of such an array.

QUICK EXPLANATION

One possible array is A = [1, 0, 2, 4, \dots, 2N-2], whose sum is 1 + (N-1)(N-2).

EXPLANATION:

First, note that the condition on all prefix sums being odd tells us that:

  • A_1 is odd
  • A_i is even for i > 1

There is only one odd number in the array, and we want to minimize the total sum. It is thus optimal to choose the smallest odd integer we can; that being 1.

The remaining N-1 elements must all be even and distinct. Once again, it is obviously optimal to choose the smallest N-1 even elements we can, which turns out to be \{0, 2, 4, 6, \dots, 2N - 4\}.

Now we know all the elements of the array, all that remains is to find their sum. Note that

0 + 2 + 4 + \dots + 2N-4 = 2\cdot (0 + 1 + 2 + \dots N-2) \\ = 2\cdot \frac{(N-2)(N-1)}{2} \\ = (N-2)(N-1)

So, the final answer turns out to be 1 + (N-2)(N-1).

A lesson about endl

This problem had rather high constraints - in most languages, the default method of taking input and printing output will likely time out, and the statement had a note asking participants to use faster methods.

However, there is one more pitfall here, specifically in C++ - and that is the use of endl.
The standard way of speeding up i/o in C++ via adding the lines

ios::sync_with_stdio(0);
cin.tie(0);

speeds up output by ensuring that the output buffer is not flushed every time cin is called (which is what cin.tie(0) does).
However, endl always forces a flush of the buffer, so using it essentially nullifies any benefit you had in the first place.
The workaround is to always use \n instead of endl.

TIME COMPLEXITY:

\mathcal{O}(1) per test.

CODE:

Setter (C++) 
#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int 
#define vi vector<int>
#define w(x) int x; cin>>x; while(x--)
#define pb push_back
 
int32_t main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    fio
    w(t)
    {
        int n;
        cin>>n;
        cout<<(n-1)*(n-2)+1<<"\n";
    }
}
Tester (Kotlin) 
import java.io.BufferedInputStream

fun main(omkar: Array<String>) {
    val jin = FastScanner()
    val out = StringBuilder()
    repeat(jin.nextInt(1000000)) {
        val n = jin.nextInt(1000000000).toLong()
        val answer = ((n - 1L) * (n - 2L)) + 1L
        out.appendln(answer)
    }
    print(out)
    jin.assureInputDone()
}

class FastScanner {
    private val BS = 1 shl 16
    private val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC
    private var `in`: BufferedInputStream? = null

    constructor() {
        `in` = BufferedInputStream(System.`in`, BS)
    }

    private val char: Char
        private get() {
            while (bId == size) {
                size = try {
                    `in`!!.read(buf)
                } catch (e: Exception) {
                    return NC
                }
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun assureInputDone() {
        if (char != NC) {
            throw IllegalArgumentException("excessive input")
        }
    }

    fun nextInt(endsLine: Boolean): Int {
        var neg = false
        c = char
        if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
            throw IllegalArgumentException("found character other than digit, negative sign, space, and newline")
        }
        if (c == '-') {
            neg = true
            c = char
        }
        var res = 0
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        if (endsLine) {
            if (c != '\n') {
                throw IllegalArgumentException("found character other than newline")
            }
        } else {
            if (c != ' ') {
                throw IllegalArgumentException("found character other than space")
            }
        }
        return if (neg) -res else res
    }

    fun nextInt(from: Int, to: Int, endsLine: Boolean = true): Int {
        val res = nextInt(endsLine)
        if (res !in from..to) {
            throw IllegalArgumentException("$res not in range $from..$to")
        }
        return res
    }

    fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)
}
Editorialist (Python) 
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    print(1 + (n-1)*(n-2))
2 Likes
2

I was using the Java Fast Reader Method which was provided in GFG and which proves to be the fastest way to take input in java yet I got TLE in each submission.
Can I get a Java Explanation?

2 Likes
3

True there was something wrong with java constraints.Pls provide an explanation.

4

Please check my thread, related to this thread.

5

Can somebody tell me what’s the error in my program.?
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);

int t;
cin>>t;

while(t--){
    long long int n;
    cin>>n;
    cout<<(n-2)*(n-1) +1<<endl;
   }
return 0;

}

I can’t able to submit this question even after the contest ends. TLE is the error.

6

replace endl with “\n”. This should solve your problem. u can read this for more info

1 Like
7

https://www.codechef.com/viewsolution/53075307

I had the same approach but still got WA. Can someone please help me explain what’s wrong with my code?

8

Why is this giving TLE, Using the same approach?

1 Like
9

Have you tried running your code locally? It doesn’t even pass the sample case, where it prints 2 instead of 3.
The mistake is in int y = x++ - it first assigns to y the value of x, and then increments x.
All you need to do is use y = x+1 instead.

1 Like
10

Your code will work if you replace endl with '\n' - please read the last part of the editorial where I’ve explained why.

11

In case of fast I/O constraints, it should be mentioned in the problem what exactly we need to use and for all programming languages (at least a link to a page which would explain how we can perform fast IO). Because, it is hard to find during contest.

1 Like
12

what’s the difference between this

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    print(1 + (n-1)*(n-2))

and this?

T = int(input())

for _ in range(T):
    n = int(input())
    print(1+(n-1)*(n-2))

I got 0.6 seconds for the Editorialist (Python) and 4.91 secs on the second one, (written by me)

can someone explain this pls?

13

Why does this give WA ?

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0);


const int N = 1e6;


int main(){
    fastio()
    int t; 
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int ans = 1 + ((n-1) * (n-2)) ;
        cout<<ans<<endl;
    }

    return 0;
}
14

use “\n” instead of endl

15

The first one is a simple way to read input much faster in python.
In this problem most of the execution time ends up being the input and output because the actual computation is so trivial, so reading input faster makes a massive difference.

1 Like
17

Can anyone explain why this is giving WA ? CodeChef: Practical coding for everyone

18

@kunal_1388 @rohit_00004
Both of you have n declared as int, which will cause an overflow when you multiply.

2 Likes
19

Thanks for the explanation!

20

try this in future for fast input output

/* 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
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
while(tc–>0){
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
writer.write(((n-2)(n-1)+1) +“\n”);
}
writer.flush();
writer.close();
br.close();
}
}

21

try this in future for fast input output , I’m using this from starting thanks to blog of codeforces for fast input output

just search about it u will get slight_smile:

/* 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
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
while(tc–>0){
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
writer.write(((n-2)(n-1)+1) +“\n”);
}
writer.flush();
writer.close();
br.close();
}
}