swapnil07's blog

CodeRush March 2024 Invite
By swapnil07, history, 8 months ago, In English

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! :)

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester.

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

It conflicts with the CF round :(.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why there are too much contest at the same time?

→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Pls also post editorial after the contest

→ Reply
»
8 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

    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)

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

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

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

      Thanks, that blog has some great insights.

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    hint
    → Reply
»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

D is exactly same as this

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    WHat eulerian circuit here , its combinatorics problem for me.

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

      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.

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

        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
        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

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

            i will look in this new approach in more detail tonight

            → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 months ago, # |
  Vote: I like it +33 Vote: I do not like it

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.

→ Reply