Hello everyone!
We are proud to invite you all to CodeRed 2021, A flagship coding event of Aparoksha — The annual TechFest of IIIT Allahabad.
CodeRed 2021 will be a 3.5 hour-long team event with a maximum size of the team being 3 members. The participants need not be from the same college/institution/organization. You will be given eight problems of varying difficulty. CodeRed 2021 is scheduled for April 11-2021, at 14:30 IST.
CodeRed, Alkhwarizm (Rated for all CodeChef contest), and Humblefool cup (which happened on April 9th on Topcoder) are all among the flagship coding events of Aparoksha — Techincal fest of Indian Institute of Information Technology (IIIT), Allahabad.
Last year, CodeRed 2020 had 958 registered teams, we are expecting higher participation this year. So, hurry up and get your team registered by filling up this form as the total prize money is worth INR 50,000.
I would like to thank jaketyler, nestedcode, tourist_k, unusual_wonder, akSingh and myself for wonderful problemsetting and testing of the round.
Are we (non-Indian participants) also eligible to receive the cash prizes?
Excited!
Excited so much
Excited (σ≧▽≦)σ
Excited!!!!
(╯✧ ∇ ✧)╯
Can we code on three computers at the same time?
Yes, You can. During registration, You have to create a team on CodeChef. You will get your team login ID there. During the contest, log in using that ID into CodeChef. All your teammates can log in at the same time and make submissions from different PCs.
For creating a team on CodeChef, follow this link.
Thx!
REALLY EXCITED FOR THE EVENT.
Hey I just filled the form. Will we get any confirmation mail with the link of the contest?
No, The contest link is already in the blog. I can paste it here as well for you. Link: https://www.codechef.com/CRED2021.
To participate, you have to register a team on CodeChef on the contest page and use that team's login ID during the contest. For more info, visit this link.
The questions were really cool. The setters did a good job. Will there be an editorial?
I guess test cases were weak for Lost Chitti. Ans for (0,0) to (0,0) in 1 sec should be No but it was accepting solutions printing Yes.
How to do MAXTREE? i thought of an approach using centroid decomposition and implicit segment trees but it was too much too code :\
No submit option :'(
When can we submit as practice?
Is this approach for MAXTREE correct, convert the tree into array and then divide the array into root(n) segments while maintaining a set for each segment and for each query find the largest element less than a[s] then search in the segments remaining (we have to search on at max 2 different segments)?
My Approach For MAXTREE:
maintain a pair of set of {node_values,node} and then for any particular query find that node which has just smaller value than A[s] then this node is selected one of the end points (name this end- point as P) now we have to select another end point such that other node should be not in the same subtree of P node and should not be in the path from P to 's'. To find this other end-point :
There are two options where P can be :
1st option — P can be in the subtree of 's'. -> try to find immediate child of 's' which contains node P. and let the name of that immediate child be 'C' ( now in 'C' subtree P is there.)
use binary search over the children of 's' with in-out time.
After finding 'C' node exclude the subtree of C and find the maximum value after excluding the subtree of 'C' whose value is less than A[s]. this node is our second end-point. (we can do this using merge sort tree)
2nd — not in the subtree of 's'. in this case take only subtree of s and find the maximum value in subtree of 's' whose value is less than A[s]. ( this also can be done by merge sort tree).
For update- point update in merge sort tree.
MY Submission- > https://www.codechef.com/viewsolution/44911635
I think it wont work directly this way. After you flatten the tree into array , the subtree of any node is fixed. You can definitely manage to get the best node inside subtree and best node outside subtree , but things get complicated when both best nodes lie inside subtree/ outside subtree. In such a case , an additional condition that one of the 2 best nodes inside subtree must not be ancestor of other...
A simple example would be
1-2-3-4-5
Subtree of 1 contains 2-3-4-5 , if you dont be careful, the segment tree query will return 2 best elements from this linear chain.. but then 1 wont lie on the simple path from one element to other.So it's invalid.
I submitted code without considering the above case.. got WA. :(
for finding best nodes we can use greedy approach.
As first best node is always that value whose value is maxium but less than A[s] and to find other best node we have to exclude the subtree of 1st best node and exclude the path from 1st best node to s.
You can also check my submission with the above approach.
Thanks for the implementation. :)
I didn't do exactly this, first I found the best number (lets say $$$u$$$) then I took the lca of $$$u$$$ and $$$s$$$ Now there are 2 cases:
lca is $$$s$$$: which means $$$s$$$ is ancestor of $$$u$$$ then I find the largest ancestor of $$$u$$$ which is child of $$$s$$$ (lets say $$$g$$$) now I search in 2 segments $$$(0, intime[g]-1)$$$ and $$$(outtime[g]+1, end)$$$ .
lca is not $$$s$$$: which means entire array except the subtree starting at s is rejected so now I search in segment $$$(intime[s], outtime[s])$$$ .
Yeah. This should be correct i guess. Nice approach.
when will the editorial of CODERED be posted ?