swapnil07's blog

CodeRush March 2024 Invite
By swapnil07, history, 2 years 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

Comments Comments (22)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a tester.

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

It conflicts with the CF round :(.

→ Reply
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why there are too much contest at the same time?

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

Pls also post editorial after the contest

→ Reply
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve B?

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

D is exactly same as this

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

    WHat eulerian circuit here , its combinatorics problem for me.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        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
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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