Paradox1's blog

By Paradox1, history, 11 days ago, In English,

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
 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

»
10 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are the problems related to machine learning?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    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.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry for the inconvenience, we have added it in the blog post now.

»
7 days ago, # |
Rev. 3   Vote: I like it -33 Vote: I do not like it

.

»
7 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Lol somehow the contest has been extended to 1 day.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be an editorial for the contest?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please move the problems to practice?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please unlock the accepted codes until the editorials are uploaded.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Mathison an peculiar sums?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: segment tree + dfs traversal

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        6 days ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        Try to implement segment trees without recursion and to use % as little as possible.

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Still getting TLE , CODE . The speed up from removing recursion was not so high .

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Finally AC . (removed recursion + reduced % + Fast IO (custom parser + BufferedOutputStream))