MiteshAgrawal's blog

Invitation to Ittiam "Think" Challenge 2017
By MiteshAgrawal, history, 7 years 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 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.

  1. zscoder
  2. Baba
  3. rajat1603
  4. satyaki3794
  5. Vikram Singh Panwar
  • Vote: I like it
  • +19
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
7 years 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.

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

    Are the problems related to machine learning?

    → Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years 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.

      → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it -33 Vote: I do not like it

.

→ Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Lol somehow the contest has been extended to 1 day.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please move the problems to practice?

→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years 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 .

      → Reply
  • »
    »
    7 years 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

    → Reply
  • »
    »
    7 years 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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please unlock the accepted codes until the editorials are uploaded.

→ Reply
  • »
    »
    7 years 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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Mathison an peculiar sums?

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

    Hint: segment tree + dfs traversal

    → Reply
    • »
      »
      »
      7 years 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

      → Reply
      • »
        »
        »
        »
        7 years 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.

        → Reply
        • »
          »
          »
          »
          »
          7 years 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 .

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

          → Reply