### MiteshAgrawal's blog

By MiteshAgrawal, history, 10 months ago, ,

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 _AJ_, 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.

•
• +19
•

 » 10 months ago, # |   +1 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.
•  » » 10 months ago, # ^ |   0 Are the problems related to machine learning?
•  » » » 10 months ago, # ^ |   0 No.
•  » » 10 months ago, # ^ |   +56 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.
•  » » » 10 months ago, # ^ |   0 Sorry for the inconvenience, we have added it in the blog post now.
 » 10 months ago, # | ← Rev. 3 →   -33 .
 » 10 months ago, # |   +22 Lol somehow the contest has been extended to 1 day.
•  » » 10 months ago, # ^ |   0 Damn!Was waiting for the editorial
 » 10 months ago, # |   0 Will there be an editorial for the contest?
 » 10 months ago, # |   0 Can you please move the problems to practice?
 » 10 months ago, # |   0 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
•  » » 10 months ago, # ^ |   0 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.
•  » » » 10 months ago, # ^ |   0 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 .
•  » » 10 months ago, # ^ |   0 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
•  » » 10 months ago, # ^ | ← Rev. 2 →   +3 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
 » 10 months ago, # |   0 Please unlock the accepted codes until the editorials are uploaded.
•  » » 10 months ago, # ^ |   0 All problems have been moved to practice and editorials have been uploaded. Also, accepted codes should be visible now.
 » 10 months ago, # |   0 How to solve Mathison an peculiar sums?
•  » » 10 months ago, # ^ |   0 Hint: segment tree + dfs traversal
•  » » » 10 months ago, # ^ |   0 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 ?
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +3 Try to implement segment trees without recursion and to use % as little as possible.
•  » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 Still getting TLE , CODE . The speed up from removing recursion was not so high .
•  » » » » » 10 months ago, # ^ |   +5 Finally AC . (removed recursion + reduced % + Fast IO (custom parser + BufferedOutputStream))
•  » » » » » » 10 months ago, # ^ |   0 Congrats!