Hello Guys, I’m back with November Cook Off Unofficial Editorials. I hope you find them helpful.
As Always, feel free to ask anything. 
Problem: Random Pair
Problem Statement
Given an array containing N integers, randomly select any two elements. What is the probability that the sum of selected elements will be same as the sum of two largest elements.
Solution
The basic thing to observe is that how the selection of any two elements will be valid.
Only the count of occurrences of largest two elements affect our answer. Because for maximizing sum, only selecting largest two elements makes sense.
Two cases arise
when largest element is present more than once.
In case largest element (say L) is present more than 1 time in array, (say c times). Therefore, we can have maximum required sum as 2L and number of ways to get sum 2L is c*(c-1)/2.
when largest element is present exactly once.
In this case, to get maximum sum, we should select largest element and second-largest element present in array. Since largest element is present only once, the number of ways of selecting such a pair is c, where c denote number of occurrences of second largest element.
Now that we have found count of favorable events and total events (N*(N-1)/2 basic combinatorics), just output the answer as favorable/total.
Take care to print the double output in required format (not in decimal format, as default in java at least.For java Have a read about DecimalFormat class for this.)
My Solution [Here][1]
Problem: Online Chess
Problem Statement
Given rating of player, minimum and maximum rating for opponent, time control, isRated and color chosen, we have to simulate online players matchmaking for games.
Solution
In this problem, the constraints were very small ( N<= 100) to allow a brute force solution ( for every player, checking all previously added and non-paired players and validating. ) to pass comfortably. The solution time complexity is O(N^2).
You can even simply do that, the following optimization is not needed, but i implemented (misread constraints… ).
I created player class (struct) for player and a match function which tells whether two players can play each other, and 8 vectors (ArrayList).
I created vectors on the basis of time controls (2 vectors for each time control) and rated or unrated (one for each rated and unrated in all 4 time controls.) This way, i am only checking those players non-paired yet, which already have same time controls and same rated choice, thereby reducing complexity of solution by a constant factor.
This is not at all needed, but i had implemented, so i explained.
Here’s my
[2]
### Problem: SKIING
#### Problem Statement
Given a grid of N*M dimensions, each having an integer depicting snow height at that position, we have to tell minimum number of cells to select so that we can visit all the cells of the grid (moving only to non-higher snow level)
#### Solution
The solution is very similar to basic graph problem to find number of connected components in graph.
Consider all the snow levels as different colors. Now the both the problems are same except for one thing that in this problem, we can visit cells of lower color too.
Now, one **observation** is that selecting the elements with maximum height makes sense, until the whole grid becomes reachable.
This is because the cells with higher snow level can move to greater number of adjoining cells.
Solution:
1. I have maintained a sorted queue (sorted desc on basis of snow height).
2. Selected topmost element of queue, check if its already visited, ignore if visited, else count++.
3. Ran a dfs on that position, while maintaining the record of visited elements, marking elements as visited.
4. when all elements are visited, (determined using a counter variable) print the count.
My Solution [Here][3]
Enjoy Coding. :D
Do share your opinions upon my editorials, as well as feel free to share your approach.
Feel free to ask anything... as always :)
[1]: https://www.codechef.com/viewsolution/16316447
[2]: https://www.codechef.com/viewsolution/16318155
[3]: https://www.codechef.com/viewsolution/16317358
