Hello Guys
This is the part 1 of three posts of unofficial editorials for October Long Challenge.
For Solutions of problems CHEFGP and/or MARRAYS, [click here][1].
For Solutions of problems CHEFCCYL and/or SHTARR, [click here][2]
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 [PERFCONT][3]
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"
Link to my Solution [here][4]
Problem [MEX][5]
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,
-
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) -
For every value x present in array, set present[x] = true (present[x] = 1 for c++ users)
-
Run a loop i = 0 to 10^6, if(!present[x] && K > 0)K–; else if(!present[x] && K==0)answer = x; break;
-
print answer;
A link to my code [here][6]
Note: for this problem, many other (efficient) solutions are also possible, but this one i found easiest.
Problem [CHEFCOUN][7]
Problem difficulty:Easy
Problem Explanation
Given an incorrect solution of problem [CHEFSUM][8], 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[0] 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[0] = 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.
Here’s a link to my
[9]
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.
[1]: https://discuss.codechef.com/questions/114541/unofficial-editorials-october-long-challenge-part-2
[2]: https://discuss.codechef.com/questions/114542/unofficial-editorials-october-long-challenge-part-3
[3]: https://www.codechef.com/OCT17/problems/PERFCONT
[4]: https://www.codechef.com/viewsolution/15750760
[5]: https://www.codechef.com/OCT17/problems/MEX
[6]: https://www.codechef.com/viewsolution/15751189
[7]: https://www.codechef.com/OCT17/problems/CHEFCOUN
[8]: https://www.codechef.com/problems/CHEFSUM
[9]: https://www.codechef.com/viewsolution/15759487