Блог пользователя Paradox1

Автор Paradox1, история, 7 недель назад, По-английски,

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.

  1. zscoder
  2. tanujkhattar
  3. rajat1603
  4. satyaki3794
  5. Vikram Singh Panwar
 
 
 
 
  • Проголосовать: нравится  
  • +19
  • Проголосовать: не нравится  

»
6 недель назад, # |
  Проголосовать: нравится +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.

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Are the problems related to machine learning?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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.

»
6 недель назад, # |
Rev. 3   Проголосовать: нравится -33 Проголосовать: не нравится

.

»
6 недель назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Lol somehow the contest has been extended to 1 day.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be an editorial for the contest?

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you please move the problems to practice?

»
6 недель назад, # |
  Проголосовать: нравится 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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 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 .

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    6 недель назад, # ^ |
    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

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please unlock the accepted codes until the editorials are uploaded.

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    All problems have been moved to practice and editorials have been uploaded. Also, accepted codes should be visible now.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Mathison an peculiar sums?