### IceKnight1093's blog

By IceKnight1093, 2 months ago,

We invite you to participate in CodeChef’s July Lunchtime, this Sunday, 17th July, rated for all.

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:

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!

• +92

 » 2 months ago, # |   +8 3.5 hours for how many questions?
•  » » 2 months ago, # ^ |   +34 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.
•  » » » 2 months ago, # ^ |   +10 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.
•  » » » » 2 months ago, # ^ |   0 maybe because of this system going live : https://codeforces.com/blog/entry/104690
•  » » » » 2 months ago, # ^ |   0 You can check the drive linked to at the bottom of this post — driveApplying 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.
 » 2 months ago, # |   +13 Ig its july lunchtime not june's lunchtime.
•  » » 2 months ago, # ^ |   +5 Fixed, thanks for noticing that.
 » 2 months ago, # | ← Rev. 2 →   +8 https://www.codechef.com/viewsolution/69250616 how is this solution wrong for 13 point Tree Retrievaland https://www.codechef.com/viewsolution/69257276 this for 4 point Inversions Retrieval
•  » » 2 months ago, # ^ |   +8 I think you forgot to take the input where the judge tells you whether your answer for that test is right or wrong .
•  » » » 2 months ago, # ^ |   +31 i feel i wasted 3.5 hrs of my life torturing myself
•  » » 2 months ago, # ^ | ← Rev. 3 →   +13 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +8 thanks, i think i need a break. But how did 4-point inversions retrieval pass 2 test
 » 2 months ago, # |   +11 Great problems! Found Div 1 quite hard though, and with so many subtasks it felt almost like a long challenge xD
 » 2 months ago, # |   +18 How to judge INVRET? Randomizing scheme?
 » 2 months ago, # | ← Rev. 3 →   +5 Brief Solution for INVRET: Subtask 1Notice 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. Subtask 2Compare all pairs of indices and add the comparisons. Subtask 3Notice 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. Subtask 4,5Copying jtnydv25 's messageWe do merge sortSo 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 Repeat 2|A| times: sum += k(AiBj)+Ai(AiBj, k+=Ai>Bj To arrange in a line you can just keep appending Ai+0Appending infinity value is done to avoid the pointers falling off Subtask 6,7,8You 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.
•  » » 2 months ago, # ^ |   +16 This was genuinely one of the best problems I have ever seen. orz work
•  » » 2 months ago, # ^ | ← Rev. 2 →   +49 Congrats to kshitij_sodani who could solve it during the Indian IOI TST, and ritul_kr_singh who almost solved it too.
•  » » 2 months ago, # ^ | ← Rev. 6 →   +5 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$.
 » 2 months ago, # |   0 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?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +29 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.
•  » » 2 months ago, # ^ |   +7 You can find some of them here: https://github.com/T1duS/CompetitiveProgramming/tree/master/Olympiad/IOITC
 » 2 months ago, # | ← Rev. 2 →   +4 Deleted
 » 2 months ago, # |   +11 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
•  » » 2 months ago, # ^ |   0 Thanks for reporting. It should be fixed now.
•  » » » 2 months ago, # ^ |   0 Thanks a lot for looking into this so quickly and rectifying it. Thanks a lot once again :)