radoslav11's blog

Invitation to CodeChef April Lunchtime 2021
By radoslav11, history, 4 years ago, In English

We invite you to participate in CodeChef’s April Lunchtime in collaboration with Dream In Code — IIIT, Lucknow, this Friday, 30th April.

Time: 7:30 PM — 10:30 PM IST.

The April Lunchtime is going to have Amazon as the official contest recruiter! Amazon is hiring for Software Development Engineer 1, Software Development Engineer 2, and Support Engineer roles for its fast-paced environment.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Joining us on the problem setting panel are:

Prizes:

The winners will receive certificates and CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good Luck! Hope to see you participating!! Happy Programming!!

  • Vote: I like it
  • +101
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Reminder — the contest starts in less than 30 minutes.

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

Reminder: Starts in 5 minutes :)

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

What was the intended complexity for Intersection Matrix.

I tried the O(2^min(N, M) * min(2^max(N, M), max(N, M) * B))

It gave only 75/100

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Wouldnt this be O(4096 * 12 * 100000) at worse? How did it get 75 pts?

    Edit: sorry I thought B was outside.

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

      If max(N, M) == 12 then I will use 2^max(N, M) instead of max(N, M)*B

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

XX: The number of ways are the first 1+k coefficients of generating function of e^(bx)*(1+f*e^(ax))^n which can be computed in $$$O(K*log(K))$$$ using newton's method.

ALLGRAPH: For all nodes appearing as endpoint of atleast 1 edge, we assume the edges are undirected, and try to run dijkstra from each node. Most of the outgoing edges from a node have same weight, we try to handle them together using segment tree to support queries of extracting min and updating min.

IMAT: Combination of Knapsack DP and Meet in the middle based on N and M is intended solution. Specifically, Meet in the middle approach fails for $$$M > 40$$$ where knapsack works. This editorial will be out soon.

The editorials for rest of the problems are out. Hope you guys enjoyed it.

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

    Can you please elaborate the solution of XX?

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

      You can write the expression for expected value as follows:

      $$$ f_k = \sum\limits_{r=0}^{n} {n \choose r}g^r(1-g)^{n-r}(ar+b)^k $$$

      Writing the EGF of $$$f_k$$$, we have:

      $$$ F(x) = \sum\limits_{k \ge 0} \frac{f_kx^k}{k!} = \sum\limits_{r=0}^{n} {n \choose r}g^r(1-g)^{n-r}e^{(ar+b)x} $$$

      which can be simplified to get:

      $$$ F(x) = e^{bx}(1 + g(e^{ax} - 1))^n $$$

      You can calculate this expression in $$$O(klog(k)log(N))$$$ or even in $$$O(klog(k))$$$ since $$$P(x)^n = e^{nlog(P(x))}$$$

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

        Ohh !! I am quite weak at mathematical modifications T-T. Btw thanks a lot.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -9 Vote: I do not like it

      I just googled things to get required formulas and then plugged them into it.

      I just look at the definition of Moment-generating function (MGF) found it while looking at binomial distribution Wikipedia page.
      Multiplying coefficient of x^i with fac(i) would give us E(x^i)
      The moment generating function of the sum of 2 independent variables is just a product of individual variables.
      Now problem reduces to finding the MGF of the binomial distribution. Then finding nth power of that MGF. Then ith coefficient that with give us the expected value of r^i. We can open up (a*r+b)^j express it as powers of polynomials of r^i 0<=i<=j. One more convolution will give us generating function for the answer.
      For implementation details, you can look at main function of my submission

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

    The editorials for problems XX, ALLGRAPH and IMAT are also out.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

Honest feedback.
Anyways problems are way out of the IOI syllabus.
Please stop awarding points for just brute forces in the last 3 problems of div 1.
I missed 30 more points on the last problem by few seconds and I don't see any point in awarding 25 points for the first subtask of Hackerman.
Both of them eventually cost me a top 5 rank.

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

    The idea of lunchtimes is for them to be IOI style and it's quite normal to give partial points (which also might change your strategy). You might argue that the partial points on those problems are given for trivial solutions, but you still need time to implement them, which potentially decrease your chances to solve some other problems fully (you even mentioned that you didn't have time to fully implement the 30 points solution). If you don't give enough points for those subtasks, nobody will bother with solving them, and frankly I think the results won't be so interesting.

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

    Seems that we have very different views on what subtasks should represent. Just 2sat is like half of the code in full solution for Hackerman, why shouldn't we award 1/4 of points for it? Yeah it's not groundbreaking in terms of idea, but you have to spend time to write it. In Graph problem subtask for 22 pts gives a hint on how to get 60 and 100 after that, one could say that 100 is just 22 + dijkstra with some data structures. Like in IOI, you are not supposed to get only 100 and 0, solving the right set of subtasks is a part of the contest.

    → Reply