# Unofficial Editorials November Cook Off

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``````
9 Likes

I further invite anyone to share their approach for last two problems. (different approaches for first three are also invited).

Hey @taran_1407
This is regarding the SKIING problem in the November Cook-Off
Here is my solution
It would be really helpful if you can help me asto why my logic is wrong. Thanks!

Mate, what are you trying to do??

Looks like u r trying just to find maximum value in grid.

I would recommend u reading http://www.geeksforgeeks.org/find-number-of-islands/ and about connected components in graph.

Try this test case
1
3 3
4 2 4
2 3 2
4 2 4

2 Likes

Nice approach for 3rd question. I thought about it but wasn’t sure.

@yvj1809

Answer of above test case should be 5. Enjoy Debugging.

1 Like

Thanks. I too wasted two submissions in that problem due to a typo.

Thank you so much! @taran_1407 and @shukrant

No problem mate. (again :P)

The approach for cakewalk question is just loveeeeeely!! <3

I was thinking on “What if the constraints were larger” and before using my brain I found this :p.

Regarding p2, well, it was pretty much implementation. (Brute force again). The problem statement was…lol.

As for p3, I liked this approach. TBH, that problem had really weak test data, though I dont know if there even exists an easily framable case against my approach.

What I did was, -

1. Visit largest element, and hence all possible elements from those. Increment answer likewise (whether connected or not).
2. If number of visited components==N*m, break out and print. else step 3.
3. Pick next largest element. (Done by scanning whole array of unvisited elements- kind of seems brute force :/)
4. Visit them, and all visitable elements from those. Note that we are marking the elements already visited- each cell is visited once (or twice)

The case I thought for was kind of-

``````N 1 N-1 1 N-2 1.....
N 1 N-1 1 N-2 1....
N 1 N-1 1 N-2 1....
. . . . . ....
. . .  .  . . .
``````

& so on, with N and M being 1000 both. Here complexity is O(500*N*M), but I think I can do better by making case where each maximum is able to visit at max 4 elements. Seems tough to make though

But anyhow, knowing your approach did help

3 Likes

Great!!

PS:i got two WA, because i forgot to add one statement (if(visited[i][j])continue.

Wow that was fast!

I got WAs for very stupid reason- 1 was for not even reading the statement of p3 properly XDXD

No problem for that.

what was fast?? @nilesh3105

Reading problem statements and constraints require a lot of patience mate!!!

I too wasted much time on ONCHESS, instead of writing brute force, i went for the mess i explained above.

1 Like

Writing editorial in ~20 min or so.

Thanks Mate…