We invite you to participate in CodeChef’s July Lunchtime, this Sunday, 17th July, rated for all.
Time: 8:00 PM — 11:30 PM IST
Please note, the contest duration is changed to 3.5 Hours, i.e, from 8:00 PM — 11:30 PM
Joining me on the problem setting panel are:
Setters: Utkarsh Utkarsh.25dec Gupta, Jeevan Jyot JeevanJyot Singh, Nishank IceKnight1093 Suresh, Ashish Ashishgup Gupta, Anay AwakeAnay Karnik, Jatin jtnydv25 Yadav, Udit T1duS Sanghi
Tester: Harris gamegame Leung
Statement Verifier: Nishank IceKnight1093 Suresh
Contest Admin: Nishank IceKnight1093 Suresh, Ashish Ashishgup Gupta
Head Admin: Alex Um_nik Danilyuk
Editorialist: Aryan Aggu_01000101 Agarwala
The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Since this contest contains problems from the Indian IOI Team Selection Tests, those students are requested to not participate.
Hope to see you participating. Good Luck!
3.5 hours for how many questions?
There are 6 in Div1, 7 in Div2 and Div3, and 8 in Div4.
Many of the later problems have several subtasks, so you are encouraged to read every problem.
why the ratings change is so wierd in this contest?
my rating was 2127 before the contest and i got 113 rank out of 275 participants,and the increament is 0.
maybe because of this system going live : https://codeforces.com/blog/entry/104690
You can check the drive linked to at the bottom of this post — drive
Applying the interpolation formula given in the post, you can check that your "Post-contest Display Rating" comes out to be 2127, which is just coincidentally your pre-contest rating as well.
Ig its july lunchtime not june's lunchtime.
Fixed, thanks for noticing that.
https://www.codechef.com/viewsolution/69250616 how is this solution wrong for 13 point Tree Retrieval
and https://www.codechef.com/viewsolution/69257276 this for 4 point Inversions Retrieval
I think you forgot to take the input where the judge tells you whether your answer for that test is right or wrong .
i feel i wasted 3.5 hrs of my life torturing myself
For 13-point Tree Retrieval, you should take input 1 or -1 after printing the edges. I had missed it too :XD
And for 4-point Inversions Retrieval, you missed to print the number of operations you are doing in the starting.
thanks, i think i need a break. But how did 4-point inversions retrieval pass 2 test
Great problems! Found Div 1 quite hard though, and with so many subtasks it felt almost like a long challenge xD
How to judge INVRET? Randomizing scheme?
Brief Solution for INVRET:
Notice that the number of inversions is (2*gap between the swapped elements -1). The gap can be found by xor-ing all the adjacent comparisons. There are 2 tricky cases to handle separately as well: 0 swaps and adjacent swap which basically requires you to engineer an if condition.
Compare all pairs of indices and add the comparisons.
Notice that we don't need to compare all pairs and comparing about half the pairs is actually enough. If we were earlier calculating -> for all i, for all j < i Then for larger values of i ( > n/2) we can compare for all i, for all j > i, and compute the thing for all j < i using that.
Copying jtnydv25 's message
We do merge sort
So if we have two sorted lists of the same size A and B.
For each A, B, first, arrange them in a line, and append an infinity value.
Initialize a pointer i=start of A, j=start of B,k = 0
To arrange in a line you can just keep appending Ai+0
Appending infinity value is done to avoid the pointers falling off
You need to do several optimizations such as using a different strategy for smaller n (say <= 6) (in the recursive merge sort) or ordering your operations in such a way that the linearization part becomes redundant.
This was genuinely one of the best problems I have ever seen. orz work
Congrats to kshitij_sodani who could solve it during the Indian IOI TST, and ritul_kr_singh who almost solved it too.
I got $$$924099$$$ queries. You can see the code here. Also with $$$N=7500$$$, I only use $$$999597$$$ queries.
In the solution, you have to calculate the number of inversions of a binary string. I believe the intended solution does this in $$$3n$$$ queries. However, I can do it in $$$2n + 8 \frac{n}{k}$$$ queries with additional $$$2 \cdot 2^k$$$ queries in the beginning. I used $$$k=12$$$ in the above solution. We split the binary string into chunks of $$$k$$$ bits. If we precomputed a lookup table for the number of inversions and their popcount, it is easy (albeit super tedious) to handle the contribution of appending a binary string of size $$$k$$$.
The problems seemed nice (even though I statpatted on subtasks)
Anyways, were all the problems used for IOI TST? And speaking of problems, can we find the previous years' problems anywhere?
The last 4 problems in div1 were used in the TSTs — the original versions had more subtasks. Most of last year's TST problems were used in the May, and June Lunchtimes of 2021.
You can find some of them here: https://github.com/T1duS/CompetitiveProgramming/tree/master/Olympiad/IOITC
Deleted
Yesterday during the contest, I submitted the solution for Tree Interval Queries (TREEQUER) which got partially accepted for 10 points. In the rank list under problem section points for that part has been given but it was not added to my total score and therefore my rank was also not updated. I don't know why it happened, can anyone clarify that? I would be thankful if something would be done to rectify that. Thanks in advance. Here's the link to My Solution
Thanks for reporting. It should be fixed now.
Thanks a lot for looking into this so quickly and rectifying it. Thanks a lot once again :)