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
How many questions will be there in the contest?
The number of problems will be revealed when the contest begins.
Why so many downvotes, I dont see anything wrong in your question?
What we will be level of questions? Can a newbie participate in it?
The difficulty of the problems increases gradually. The starting problems are easier and comfortable for beginners.
Just curious: Why is this contest not listed on Codechef/Compete/AllContests ?
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.
Excited for the contest!
Hope the contest is as cool as last years' !!
What languages can i use in this contest?
Codechef supports all popular programming languages.
Only 6 hours to go for Alohomora 2022!
Register your team now at https://www.codechef.com/ALMR2022
Auto comment: topic has been updated by ankit907 (previous revision, new revision, compare).
Alohomora 2022 has started!
GLHF!
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)
I think Ternary Search + Coordinate compression + Fenwick/Segtree is intended
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)
Can be done using binary lifting on fenwick tree instead of binary search, saving a logN factor.
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.
great responsibility problem can be solved using mo's algo as well..
Didn't think of Mo's earlier! Can you please share your approach.
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
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.
How to solve the problem HIGHWAY ??
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.
Hope you all enjoyed solving the problems.
We would appreciate some feedback for the contest in the comments.
The problems were really great.We loved to solve them.But why there is no option for upsolving?
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.