Hello Codeforces Community!
I would like to invite you to take part in Ittiam "Think" Challenge, scheduled to start on the 13th of August at 12:00 PM IST.
You will be treated with some interesting set of problems which are set by MazzForces, AlexandruValeanu, saatwik27 and send_nodes. It was real challenge to solve and test them for me(paradox1).
So get your weekend booked to solve some intriguing problems. The contest will be slightly on the harder side, few challenging problems for high experts and div1 contestants, but others too will find them interesting. So buckle up for maximum participation, as there are great prizes to be won.
I hope you will enjoy solving the problems. You can discuss and provide feedback about them in comment section below after the contest.
UPD : Note that prizes will only be for Indians. In addition, keeping up with previous issues with challenges with prizes, this is an open challenge running for 7 hours, without any slots, with a better problemset, to ensure the prizes to go the people who deserve them.
UPD2 : The Contest has ended, Congrats to the winners.
Note that prizes will only be for Indians. In addition, keeping up with previous issues with challenges with prizes, this is an open challenge running for 7 hours, without any slots, with a better problemset, to ensure the prizes to go the people who deserve them.
Thanx.
Are the problems related to machine learning?
No.
Maybe it is a good idea to point out somewhere that people from other countries are not eligible for prizes? I only see it in this comment — I can't find anything about it at the contest page or even in the announcement here. I thought it is most likely true because it is so in most of the cases for similar contests, yet it may be quite a big surprise for some random contestants who didn't read your comment.
In case it is actually written somewhere at the contest page, it is a good idea to make it easier to notice — I quickly read through and also checked everything I get for ctrl+F on "priz", "elig", "indi" etc.
Sorry for the inconvenience, we have added it in the blog post now.
.
Lol somehow the contest has been extended to 1 day.
Damn!Was waiting for the editorial
Can you please move the problems to practice?
Can E be solved using linearity of expectation ?
Suppose Ci be the random variable for the maximum in the ith column after choosing the random k tuple . We need to find
using linearity of expectation we can write this as 
.
Now to find the expected value for each column , I sorted the column and iterated in descending order . So if the jth largest number is the maximum then the remaining K - 1 numbers should be chosen from the numbers smaller than the jth largest number , which is N - j .
I was able to get 44 points using this approach . Can someone point out the problem in my logic . My CODE
Yes that's the solution.I think you might have misunderstood the question as the maximum value from the column needn't belong to the selected subset of rows.
Yeah I misunderstood that we choose the max from the chosen k tuple , whereas the question asked us to find the overall max . Fixing that gave me AC .
Try and consider the case when we select a tuple of k rows in a single column, but the maximum element in the column doesn't change. All the other reductions are correct
Yes, you need to use linearity of expectation. Find answer for each column and add them to get final ans. For a single column, sort the values in it and iterate over them, assuming that they are the kth chosen row (k-1 values are already chosen to its left).
So, the resultant ans for that column will be max(arr[i]+x, arr[n]). And you need to multiply this by the probability C(i-1, k-1)/C(n, k).
I think the mistake in your code is that arr[n] may be greater than arr[i]+x but you always use the latter value.
My code
Please unlock the accepted codes until the editorials are uploaded.
All problems have been moved to practice and editorials have been uploaded. Also, accepted codes should be visible now.
How to solve Mathison an peculiar sums?
Hint: segment tree + dfs traversal
I find the time limit for this problem to be tight for java. My solution runs in O(Nlog(N)) , but still I got TLE for the last 3 test cases . Any suggestions to make it faster ?
My CODE
Try to implement segment trees without recursion and to use
%as little as possible.Still getting TLE , CODE . The speed up from removing recursion was not so high .
Finally AC . (removed recursion + reduced
%+ Fast IO (custom parser +BufferedOutputStream))Congrats!