# Unofficial Editorials October Long Challenge (Part 1)

Hello Guys

This is the part 1 of three posts of unofficial editorials for October Long Challenge.

This post has editorials for problems PERFCONT, MEX and CHEFCOUN

## Note: Problems are explained for newbie/beginner level. In case you find it too basic, feel free to skip paragraphs of explanation and just read the bold text… ### Problem Difficulty : Cakewalk

#### Problem Explanation

Given number of problems ans number of participants who solved it, check contest overall difficulty as balanced or not

If p denote the number of participants who solved the problem, A contest is balanced if

p >= P/2 (Integer division) for exactly two problems AND
p<=P/10 (Integer division) for exactly one problem.

#### Solution

The problem Explanation provides a direct solution. Use counter variables easy and hard, denoting Simply Check for every problem

if first condition satisfied, easy++;

if second condition satisfied, hard++;

In the end, if easy == 1 && hard == 2 print “yes” else print "no"

# Problem [MEX]

### Problem Dificulty:Simple

#### Problem Explanation

Mex is the smallest non-positive integer which is not present in given set.

Given a set, find the Maximum value of MEX of given set, after inserting any K values into set…

## Solution

This problem needs one observation

consider set {0, 1, 2, 2} and K = 2

Mex of given set = 3

Insert 3 into set, set become {0,1,2,2,3}, mex = 4

Insert 4 into set, set become {0, 1, 2, 2, 3, 4} mex = 5

From this, it follows that if at every step, Mex of existing set is inserting into set, we will get maximum value of Mex after inserting K values.

Perhaps the simplest solution,

1. Declare a boolean array (for c++ users, int array) present of size upto 10^6
(2*10^5+1 will also suffice here, reason explained below)

2. For every value x present in array, set present[x] = true (present[x] = 1 for c++ users)

3. Run a loop i = 0 to 10^6, if(!present[x] && K > 0)K–; else if(!present[x] && K==0)answer = x; break;

A link to my code [here]

Note: for this problem, many other (efficient) solutions are also possible, but this one i found easiest.

### Problem difficulty:Easy

#### Problem Explanation

Given an incorrect solution of problem [CHEFSUM], generate a test case with an array containing given number of elements N (99991<=n<=1000000)

#### Solution

In this problem, the inexpert coder fails to take into account that prefsum(i)+sufsum(i) may not fit integer range.

Integer overflow is a scenario where the resultant number arising from addition, subtraction and other arithmetic operations, exceeds the maximum range of Integer data type.

The Maximum range of unsigned int is 2^32-1 = 4294967296-1 (11111111111111111111111111111111 in binary)

whenever an unsigned int exceeds this value, only the last 32 bits are stored.

For Example 4294967298 has binary representation 100000000000000000000000000000010

If we try to store this value in unsigned int, it will be stored as 00000000000000000000000000000010 that is 2.

Notice that 4294967298 remainder 4294967296 = 2

let MOD = 2^32 = 4294967296

So the code snippet given in problem return the index in array where (prefsum(i)+suffsum(i))%MOD is minimum.

Actual Solution to CHEFSUM is the first index of minimum value in the given array

So we can construct any array such that

index where (prefsum(i)+suffsum(i))%MOD is minimum != smallest index where the number is minimum value of array.

I used a trick in my solution. I set 4294967296 - a as total sum of array. X is chosen to be 43000 (Any value above 4294967296 / N would solve the problem).

long Total = 4294967296 - 43000-43000; //Total denote sum of array excluding first element)

a = 43000

Rest array is generated as
for i = 1 to N-1{

a[i] = Total/(N-i)

Total -= a[i];

}

This way, almost all values are assigned value 42948 to 42954 (Depending on value of N).

Correct answer for aboce generated array is 2, but incorrect code will give answer 1

Because, PrefSum(i)+Suffsum(i) = Sum of whole array + a[i]

prefSum(0)+sufsum(0) = (4294881296 - 43000) + 43000 = 4294881296 = 0 (mod 4294881296)

Consequently, incorrect code return 1 while correct answer is 2.

``````


43000 was chosen because if any number smaller than 42948 is chosen, it is likely that it it actually the correct answer of the problem. So the incorrect code will actually get the answer correct despite wrong solution, **Something Chef doesn't want to happen :)**

PS: I liked this problem a lot. It was completely an out-of-box problem... Thanks to codechef problem setters.

Next problems are discussed in Unofficial Editorial Part 2.

Keep Coding. Feel free to ask anything.

: https://discuss.codechef.com/questions/114541/unofficial-editorials-october-long-challenge-part-2
: https://discuss.codechef.com/questions/114542/unofficial-editorials-october-long-challenge-part-3
: https://www.codechef.com/OCT17/problems/PERFCONT
: https://www.codechef.com/viewsolution/15750760
: https://www.codechef.com/OCT17/problems/MEX
: https://www.codechef.com/viewsolution/15751189
: https://www.codechef.com/OCT17/problems/CHEFCOUN
: https://www.codechef.com/problems/CHEFSUM
: https://www.codechef.com/viewsolution/15759487``````
2 Likes

There is small typo in explanation of first problem. Here it is
In the end, if easy == 2 && hard == 1 print “yes” else print “no”
which should be In the end, if easy == 1 && hard == 2 print “yes” else print “no”

updated!! 