Greetings Coders, We would like to invite all of you to the SpyBits CP Round 2021, under the banner of Udyam’21, IIT (BHU) Varanasi.
Udyam is the annual technical fest of the Department of Electronics Engineering, Indian Institute of Technology (BHU), Varanasi organized from Apr 15-18, 2021.
The CP round of SpyBits is a hugely anticipated annual affair now, entering it’s 11th edition under different names and forms. It will take place on April 15th from 9:00 PM — 11:30 PM IST.
We would like to thank our Title Sponsors, CoinSwitch Kuber, and the Event Sponsors, Silence Laboratories.
Click here to go to the contest page.
Click here to go to the contest discussion page.
The Problem Set has been prepared by ashish_vishal, adikrsingh and me, dakshgarg.
We would like to thank jtnydv25, iscsi, 7dan,shikhar7s, emperor_gentoo and pied-piper for their support in testing and preparation of this contest.
Participants will have 2.5 hours to solve 7 problems. The scoring will be ICPC style. The contest will be rated for Div. 2 and Div. 3 participants, but even so, has some hugely exciting problems for everyone!
Prizes! Merit Certificates shall be awarded for the Global Top 15 as well as Top 5 Indian participants
Good Luck everyone! Hope to see you on the leaderboard.
Update: There will be 8 problems in the contest.
8 problems in each of all three divisions ?
Yes
Reminder: The contest is about to begin in an hour.
Why the heck time limit of Gotham is so tight ? Many NlogN solutions easily fail , fix it , if possible .
My N(LogN)^2 is passing.
You might be using std::lower_bound instead of std::set::lower_bound
That's why your complexity would've been n^2 rather than nlogn.
Difference between std::set::lower_bound and std::lower_bound in C++
Any Hint for Problem F , in case when we have i and j & arr[i] > arr[j]. How do we handle this case ?
hint: The height of not only i and j but each stone between i and j matters in calculating the final answer.
You have to take the maximum height between i and j, this can be done by segment tree.
Wow. That was a nice one. So the answer for ( i,j) will eventually become ans[max between i,j]
Can u give an intuition why answer for max of the range is the final answer for the range.
For the $$$ith$$$ stone the maximum height stone(let's say $$$kth$$$ stone) would come in between the $$$ith$$$ and $$$jth$$$ stone so the next stone which is visible would have to have height greater than $$$kth$$$ stone, and this stone would naturally occur after $$$jth$$$ index as we have taken the maximum height stone between $$$i$$$ and $$$j$$$.
Just connect every element with its next greater element and those which have none connect to n + 1 , now the answer is just the depth of LCA of nodes i and j with just one case when one node is itself the LCA.
The problem set is just implementation heavy not thought provoking at all. Anyway, the problem set is okayish.
How to solve the problem MINIMUM OPERATION? Can't we do it with binary search?
Yes, you can use binary search, this can also be solved in n*k complexity using the previous operations.
Ok, can you give some insight into the O(n*k) solution?
SOLVE IT Editorial
I enjoyed this problem set — barely any math and all algorithmic problems... Thank you!
UPDATE
Click below to open editorilas of the problems:
SAVE WATER
Valentine Couple
MISSION GOTHAM
PILGRIMS DESTINATION
MINIMUM OPERATION
STONE LAND
MAXPOOL
SOLVE IT
I think C was much difficult than D, gave 1hr 40 minutes to C While D took 20 minutes.
For those who got TLE in problem C
Difference between std::set::lower_bound and std::lower_bound in C++
TLE Code V/S AC Code