vishaaaal's blog

Invitation to Alohomora [Editorial Update]
By vishaaaal, history, 3 years ago, In English

       

Hello Codeforces!

From the infinite possibilities of the multiverse, Spider Man has found out the one and only one way to save the world from collapsing. You being his comrade must assist him in saving the world in the best possible way !

RECursion presents you Alohomora — an ICPC-styled team coding contest where you would have to assist Spiderman in teams of at most 3 people against an unwanted disaster. The contest will start on April 10 2022 at 9:00 PM IST. Contest duration is 2 hours 30 minutes.

We are also giving away prizes for top performing teams of our contest as follows :

  • Cash prize of Rs 5000 and Rs 3000 respectively for the top 2 performing teams.
  • Cash prize of Rs 2000 for the top performing Indian team.
  • Goodies for the top performing team from NIT Durgapur.

Regarding any queries, please contact :
Vishal : +91 9079971627
Saptarshi : +91 89278 53473

RECursion wholeheartedly invites you to take part in Alohomora!

Happy Coding :))

UPD: The contest is to start in less than 1 hr. Do register if you already haven't. Hope you enjoy the round!
UPD2: The contest has started! We hope you enjoy the problems.

UPD3: The problems have been moved to the practice section and editorials to all of them are out! Have a look at them at :
PETER
XOREASY
GREATSACK
VULTURE
DRSTRANGE
GOBLIN
HIGHWAY
SPIDEY

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

Comments Comments (28)
| Write comment?
»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

How many questions will be there in the contest?

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

    The number of problems will be revealed when the contest begins.

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

    Why so many downvotes, I dont see anything wrong in your question?

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

What we will be level of questions? Can a newbie participate in it?

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

    The difficulty of the problems increases gradually. The starting problems are easier and comfortable for beginners.

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

Just curious: Why is this contest not listed on Codechef/Compete/AllContests ?

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

    In case of CodeChef, external contests are not shown in the all contest tab by default.

    You have to toggle the "Show all contests" button to see them.

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

Excited for the contest!

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

Hope the contest is as cool as last years' !!

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

What languages can i use in this contest?

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

    Codechef supports all popular programming languages.

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

Only 6 hours to go for Alohomora 2022!
Register your team now at https://www.codechef.com/ALMR2022

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

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

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

Alohomora 2022 has started!
GLHF!

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

What is the expected soln to Goblin?

We came up with a super overkill soln (which we didn't code).

  • Store two implicit segtrees and doing the same AP trick people used to overkill yesterday's Div2D (one for increase and one for decrease).

  • Then we could binary search on the point where the value of the increase segtree becomes larger than the decrease segtree and taking the min of the answer for that position and the previous one.

Is this correct and / or is there a different (hopefully simpler) approach?

Also what was the expected soln of Great Responsibility?

We tried answering queries offline using small to large merging with maps of counts of values in $$$O(n \cdot \log^2(n) + a_{max} \sqrt a_{max} + sum\_div\_cnt(a_{max}) \cdot log(n))$$$ where $$$sum\_div\_cnt(x)$$$ is number of divisors for all $$$1 \leq i \leq x$$$, worst case like $$$2 \cdot 10^6$$$ for $$$x = 2 \cdot 10^5$$$ and got TLE.

We had to optimize to $$$O(n \cdot \log(n) + a_{max} \sqrt a_{max} + sum\_div\_cnt(a_{max}))$$$ using gp_hash_tables to get AC. (constant factor optimization by around 2-3x)

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

    I think Ternary Search + Coordinate compression + Fenwick/Segtree is intended

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

    I solved it using binary search + coordinate compression + fenwick tree.

    I'll briefly explain my solution here, In this problem, if we create a new array C by replicating ith element of A, Bi number of times, then we are basically asked to find minimum number of operations to make all the elements of C equal. The resulting value should be the median of the array C. We can binary search the median by storing the frequencies of values of array A in a fenwick tree. We can use compressed values in fenwick tree because that won't affect the position of median. We can maintain another fenwick tree to calculate the sum of values of array C on both sides of the median. You can find my code in the link below.

    (https://ideone.com/hAuOLm)

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

      Can be done using binary lifting on fenwick tree instead of binary search, saving a logN factor.

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

    For the problem GOBLIN, it can be solved using binary search and a fenwick tree.
    Basically, we take all different values $$$A_i$$$ we may encounter during all queries. Do coordinate compression to map them to some index. Later, binary search to find median and using fenwick tree to keep prefix sums can be used to solve it.

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

    great responsibility problem can be solved using mo's algo as well..

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

      Didn't think of Mo's earlier! Can you please share your approach.

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

        the query can be split into two parts for given two nodes and can be answered by flattening the tree using the Euler tour and then using simple mos algorithm over the flattened tree

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

    Great Responsibility can actually be solved using in-out times and binary search. Store in-times corresponding to each value and at the time of the query, traverse on all divisors of X and count occurrences of each divisor in the subtree of u and v using their in-out times and binary search. That's pretty much it.

    It can also be solved offline using DSU-on-tree as you suggest.
    Setter's solution uses this approach.

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

How to solve the problem HIGHWAY ??

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

    If we create a bipartite graph between the signals and the time instants they were Red on, we can observe that the only thing we require is the min vertex cover of the formed graph.

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

Hope you all enjoyed solving the problems.
We would appreciate some feedback for the contest in the comments.

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

The problems were really great.We loved to solve them.But why there is no option for upsolving?

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

    The problems are yet to be moved to the practice section. We are in touch we people from CodeChef to get this done as soon as possible.

    → Reply