Unofficial Editorials November Cook Off

cook88
editorial
onchess
rndpair
skiing

#1

Hello Guys, I’m back with November Cook Off Unofficial Editorials. I hope you find them helpful.

As Always, feel free to ask anything. :slight_smile:

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… :slight_smile: ).

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

#2

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!


#3

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 :confused:

But anyhow, knowing your approach did help :smiley:


#4

Hey @taran_1407 @vijju123 , I have applied same logic for problem SKIING. got NZEC 10 times in java. same solution accepted in cpp. even I have copied already accepted solution of java after contest got over . Got NZEC.

Link to my Solution : https://www.codechef.com/viewsolution/16319005

I don’t Expect this type of judging from Codechef. Used fast Scanner Class for java. Fast Printwriter. Got nothing. my complete logic was correct.

Also I don’t have enough karma to open question for this…
Disappointed.


#5

My Approach for Hasan and boring classes :

As the string we have to find must be a palindrome the condition that must hold is T == T[n-1-i]* for all i. So for every such pair (i,n-1-i) there are two cases :

Case 1: S == S[n-1-i]*

In this case we can either change both the characters to some other character or do not change any of two character. There are 25 ways to change both the characters. There is 1 way to change none of them.

Case 2: S != S[n-1-i]*

In this case we can either change the ith character to (n-1-i)th character or change (n-1-i)th character to ith character or change both the characters to some character other than both of them. If we are chnaging only one of them then there are 2 ways and if we are changing both of them there 24 ways.

Some Mathematics before Moving Further

Suppose there are m balls and n bins. Assume bins are distinct. How to put m balls in n bins such that no bins contains more than k balls. There is easy way to deal with such type of problems. Formulate the question in terms of polynomial. So the polynomial for first bin is (x^0 + x^1 + x^2 + … + x^k). x^0 represents we put 0 balls in the bin,and in general x^k represents we put k balls in the bin.And it will be same polynomial for all bins because the max limit is same for all bins. So now our answer will be nothing but just the coefficient of x^m in polynomial generated by multiplication of polynomials of all bins. So answer is coefficient of x^m in (x^0 + x^1 + x^2 + x^3 + … x^k)^n. . Note this logic can even be extended if we have different max limits for each bin.

Solution to original Question

So as discussed above we will create a polynomial for all (i,n-1-i) pairs and then find coefficient of x^k where k is the hamming distance needed. As in our case k is the max hamming distance possible, actual answer is summation that is coeff(x^0) + coeff(x^1) + … + coeff(x^k). Now the polynomial for case 1 is (x^0 + 25*x^2) Here x^0 corresponds to changing 0 characters and x^2 is changing 2 characters and coefficient describes number of ways to do it. Similarly the polynomial for case 2 is (2x^1 + 24x^2).

So now suppose that there are a pairs of case1 and b pairs of case 2 then multiplied polynomial will be (x^0 + 25x^2)^a * (2x^1 + 24*x^2)^b. So now compute first part and second part individually using combinatorial expansion and then use FFT to derive the multiplied polynomial. Now find summation of coeff(x^0) + coeff(x^1) + … + coeff(x^k) in the multiplied polynomial obtained using FFT. That’s the answer.

Note you have to separately handle for the odd case. Because the just middle character, the polynomial will be (x^0 + 25 * x^1). So answer in this case will be ans(S’,k)1 + 25ans(S’,k-1). where S’ is the string obtained by removing the middle character.

Optimization

If we have to find a coefficient of a single power in multiplication of two polynomials A and B, it is just O(N). But here we have to find k such powers. So it is not feasible to do this way and because of this reason only we are using FFT. But wait we have to find summation of coefficients of first k powers then what we can to do just find the coefficient of x^k in the multiplication of (prefix sum polynomial of A) and B. That is define new polynomial A’ where coefficient of x^k is summation of coeff(x^0) + coeff(x^1) + … + coeff(x^k) in polynomial A. Now we have to find just coefficient of x^k in A’B. Remember to expand A upto x^k by appending zeros and then form A’. You can also use B’A instead of A’B because A’B = B’A.

Intuition behind optimization : Suppose I want to buy at most k apples in total from shop A and shop B. Then you can solve this by fixing the amount of apples to buy from shop B and then loop over that fixed amount. That is (0 apple from shop B,at most k apples from shop A), (1 apple from shop B, at most k-1 apples from shop A), … , (k apples from shop B,0 apples from shop A). So for finding coefficient for at-most in A we are using prefix sum polynomial A’.


#6

Hi,

I am unable t ask any question. @vijju123 can you tell me what is karma and all that stuff.
Actually I wanted to know What is STL equivalent in python?? I am thinking to use python instead of C++ for competitive Coding. any suggestions about this.


#7

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


#8

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.

Feel free to ask. :slight_smile:


#9

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


#10

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


#11

@yvj1809

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


#12

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


#13

Thank you so much! @taran_1407 and @shukrant


#14

No problem mate. (again :P)


#15

And sorry about the new answer thing. Kind of new here :stuck_out_tongue:


#16

Great!!

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


#17

Wow that was fast!


#18

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


#19

No problem for that. :slight_smile:


#20

what was fast?? @nilesh3105