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

CodeRush March 2024 Invite
Автор swapnil07, история, 3 месяца назад, По-английски

Update: The contest goes live today, 4th March 2024 at 9 PM IST.

Warm greetings!

Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 4th March 2024 at 9 PM IST.

Registration Link: CodeRush

You will be given 6 problems and 150 minutes to solve them. The contest will be rated for all.

The problems are prepared by spongebobsquareroot.

We would also like to thank pradumangoyal and gkapatia for co-ordinating the round.

Highlights of contest:

  1. The Prize Money for the top 5 performers are as follows:
    • First Prize: ₹10,000
    • Second Prize: ₹5,000
    • Third Prize: ₹2,500
    • Fourth Prize: ₹1,500
    • Fifth Prize: ₹1,000
  2. ₹100 Amazon gift vouchers to the top 50 participants.
  3. ₹100 Amazon gift vouchers to 50 randomly selected participants who solve at-least 1 problem.

Have an amazing contest! See you all at the leaderboard! :)

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

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

As a tester.

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

It conflicts with the CF round :(.

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Excited for another CodeRush challenge. The blend of competitive spirit and rewards truly makes this a can't-miss event. Best of luck to all coders, and hats off to the organizers and problem setters

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why there are too much contest at the same time?

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Pls also post editorial after the contest

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

How to solve D? All that I can figure out was this sequence in the last minute.

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

    It was basically a variant of Catalan Numbers. Number of paths from (0,0) to (n,m) such that you never cross (x,x+k) for a selected k . Now do the normal process of bijection we do in normal catalan number suppose x R used and x+k+1 U used so flip on right side now there are (n-x) U on right side and (m-x-k-1) R so we will reach (n-x+x+k+1 , m-x-k-1) or (n+k+1 , m-x-k-1) so total ways are n+mCn — (n+m)C (n+k+1)

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

    https://discuss.codechef.com/t/vaimin-editorial/18417

    → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B?

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

D is exactly same as this

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E was good and easy once you figure out only checking existence of eulerian circuit is needed, we don't actually need to find it as it's unique and we just count all permutations of same edges.

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

    WHat eulerian circuit here , its combinatorics problem for me.

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

      It is a combi problem after you check that it forms eulerian circuit, otheriwse answer is 0, if it is eulerian then the cycle is unique, we can only the order of edges between same pair of vertex, ie. every permutation so it's just product of factorials of their count, deriving it is simple with eulerian circuit.

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

        i dont know , what you mean by checking euleria circuit
I do it like : 
      Make all of them in 4 groups->
              1) need a power and a power to the next one
              2) just need a power to complete
              3) just power to next one
              4) no need a power and nor giving

Then it is just ordering them in n positions
        → Ответить
        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          interesting, what I did is suppose column i needs X carry to be valid, and after getting X it leaves carry Y then consider an edge in graph as (Y, X) we get N such edges, in any valid ordering, the edges will look like this (0, a), (a, b), (b, c), ..., (w, x), (x, y), (y, 0), ie. a path that starts and ends with 0 and contains each edge exactly once, probably didn't need euler circuit for rest of part but it's easy to see this circuit is unique except for the choice of identical edges, if a path exists then just combi of choosing any permutation of those identical edges, else 0, anyways not hard to check just indegree == outdegree stuff.

          → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i can't register at newton school, the OTP has never arrived to my mobile number

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

What's the exact solution of Q6?
I use random (incorrect) heuristic (actually, my solution is determistic when $$$O(N^2)$$$ is allowed) and got AC.

  • First, I apply an idea of tree radius. Start random vertex $$$u$$$ and find $$$v$$$ which has the largest $$$d(u,v) = d_1(u,v) + d_2(u,v) + d_3(u,v)$$$, and after that start $$$v$$$ and find $$$w$$$ which has the largest $$$d(v,w)$$$ ... (let call this work A) I continued this until the first vertex is already checked. I continued this until TL and got 7/9 AC.
  • Let's modify the definition of $$$d$$$. Instead of $$$d_1+d_2+d_3$$$, we can choose non-empty subset of this. I choose the definition randomly.
    • Before start each work A, I fixed the definition of $$$d$$$. This allows 8/9 AC.
    • For each step of work A, I changed the definition of $$$d$$$. This allows 8/9 AC.
  • Actually, I fail two different testcase with above two heuristic. Now, I have a potential of AC with the probability of $$$1/4$$$! Let the showtime start, submit my solution several times!

code

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    They just know how to make contests, they dont care about editorials, so dont expect a response

    → Ответить
  • »
    »
    2 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Yah man. They excel at crafting contests but show little interest in editorials, so don't anticipate a reply.

    → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Deepest apologies for the delayed response; I was stuck in a situation with limited connectivity. Here is the editorial for CodeRush March '24 https://drive.google.com/file/d/1jqL7iHEMETyTKtNU2mqno6LpN6SwvHvT/view?usp=sharing The editorials for future CodeRush contests will be published right after the contest.

→ Ответить